平衡括号树表示 | Codeboy's Blog

形式陈述

给定一棵含 $n$ 个节点的有序有根树，按孩子次序做深度优先遍历。第一次进入节点时写 1，离开节点时写 0，得到位串

B[0..2n)\in\{0,1\}^{2n}.

本页统一采用半开前缀约定：

\operatorname{rank}_b(i) =|\{j:0\le j<i,\ B[j]=b\}|, \qquad 0\le i\le 2n,

并定义

e(i)=\operatorname{rank}_1(i)-\operatorname{rank}_0(i).

位串是合法平衡括号串，当且仅当

e(i)\ge0\quad(0\le i\le2n), \qquad e(2n)=0.

也就是说，每个前缀中的开括号数不少于闭括号数，整串二者相等。原始 $2n$ 位只编码树形和孩子次序，不编码节点标签、边权或其他负载。

每个节点由其开括号位置 $p$ 表示。与它匹配的闭括号位置是

\operatorname{findclose}(p) =\min\{q>p:e(q+1)=e(p)\}.

记 $q=\operatorname{findclose}(p)$ 。区间 $B[p..q]$ 恰好编码以该节点为根的整棵子树，因此

\operatorname{depth}(p)=e(p), \qquad \operatorname{subtree\_size}(p)=\frac{q-p+1}{2}.

根节点的开括号位于 0，所以其深度为 $e(0)=0$ 。若 $p+1<q$ ，则 $p+1$ 是第一个孩子的开括号；若 $q+1$ 仍位于父节点的匹配区间内且 $B[q+1]=1$ ，则 $q+1$ 表示下一个兄弟。父节点由最内层包住 $[p,q]$ 的括号对给出，即 enclose(p)。

findopen、findclose、enclose 以及相对 excess 的前向或后向搜索，可以通过块内查表、块级最小值摘要和范围最值结构支持。经典结果在 $2n+o(n)$ 位内实现常数时间的核心括号操作，并由此构造常数时间的有序树导航接口。

直觉

一对匹配括号像一个闭合容器：节点的所有后代都写在它的开括号与闭括号之间。括号嵌套就是祖先关系；一个孩子的闭括号之后若立刻出现开括号，那个开括号就是它的下一个兄弟。显式树上的指针追踪因此可以改写成位串上的 matching 和高度搜索。

excess $e(i)$ 是扫描到位置 $i$ 之前仍未闭合的括号数，也就是 DFS 当前所在层数。进入节点使高度加一，离开节点使高度减一。寻找匹配闭括号，就是寻找高度第一次回到进入该节点前的值；寻找父节点，则是向左寻找最近一个把当前区间包住的、更低一层的开括号。

例子与边界

根有两个孩子，左孩子又有一个孩子时，括号串为

((())()) \qquad\text{或位串}\qquad 11100100.

按 0 起点编号，根为 $p=0$ 、匹配位置 $q=7$ ；左孩子为 $p=1$ 、 $q=4$ ；左孩子的孩子为 $p=2$ 、 $q=3$ ；右孩子为 $p=5$ 、 $q=6$ 。左孩子的深度为 $e(1)=1$ ，子树大小为

\frac{4-1+1}{2}=2.

这个例子也说明“下一个孩子”不能靠固定字符步长取得：左孩子占用的括号区间长度取决于其整棵子树，必须先跳到匹配闭括号之后。

含 $n\ge1$ 个节点的有序根树数量为 Catalan 数

C_{n-1}=\frac{1}{n}{2n-2\choose n-1},

所以表示任意此类树至少需要

\log_2 C_{n-1} =2n-\frac32\log_2 n+O(1)

位。原始括号串的 $2n$ 位已经接近信息论下界；额外的 $o(n)$ 位用于加速查询，而不是承载树形本身。

索引约定不能混用。有的文献把 rank(i) 定义为包含位置 $i$ ，有的把根深度写成 1，还有的给整棵树额外套一对虚拟括号。公式在各约定下都可成立，但 findclose 的目标高度、深度公式和子树区间端点会一起变化。本页全部公式都使用“半开前缀、根深度 0、无额外虚拟根”的约定。

推论与应用

若定义

\operatorname{fwdsearch}(i,d) = \min\{j\ge i:e(j)=e(i)+d\},

许多导航操作都可以归约为 matching、范围最小值和相对高度首次命中。实际实现会按机器字分块：块内模式用微表回答，跨块部分先用摘要跳过不可能包含答案的块，再在目标块内定位。

位串合法并不自动意味着查询是 $O(1)$ 。直接从 $p$ 向右扫描当然能找到匹配闭括号，却可能遍历整棵子树； $2n+o(n)$ 的简洁索引结论还需要把辅助表、块摘要和 word-RAM 假设一起计入。

平衡括号表示是简洁数据结构的基础部件，可用于有序树、XML 文档、后缀树拓扑和若干平面图表示。应用层若还需要节点标签或边值，通常另建与开括号次序对齐的数组；树形的 $2n$ 位界不能被误写成整个带数据对象只占 $2n$ 位。

参考资料

Guy Jacobson, “Space-Efficient Static Trees and Graphs,” FOCS, 1989, pp. 549–554.
J. Ian Munro and Venkatesh Raman, “Succinct Representation of Balanced Parentheses and Static Trees,” SIAM Journal on Computing 31(3), 2001, pp. 762–776.
R. Raman, V. Raman, and S. S. Rao, “Succinct Indexable Dictionaries with Applications to Encoding $k$ -ary Trees, Prefix Sums and Multisets,” ACM Transactions on Algorithms 3(4), 2007.