平衡括号树表示

编码与合法性 ​

对有序根树做深度优先遍历公理库深度优先搜索Depth-first search · DFS沿未访问边尽可能深入后回溯的图遍历算法。：进入节点写 1（左括号），退出写 0（右括号），$n$ 个节点得到长度 $2n$ 的串。任意前缀中 1 的数量不少于 0，整串二者相等；定义 excess$(i)=ran{k}_1(i)-ran{k}_0(i)$。每个节点由其开括号位置代表，匹配右括号界定整棵子树区间。

导航操作 ​

findclose$(i)$ 找与开括号 $i$ 匹配的位置，findopen 反向；enclose 找包住当前括号对的最内层括号，对应父节点。节点深度由开括号前的 excess 给出，子树节点数为

$$\frac{\mathrm{findclose}(i)-i+1}{2}.$$

first-child、next-sibling 可由相邻括号和匹配操作恢复。用分块 excess 摘要与微表可在 $2n+o(n)$ 位内支持常数导航。

编码例子 ​

根有两个孩子，左孩子又有一个孩子，其括号串为 $((())())$。左孩子的匹配区间完整包住其孩子，右孩子紧跟左孩子的闭括号之后；父子和兄弟次序都可从嵌套恢复，无需存指针。

信息与边界 ​

有序根树数量是 Catalan 数 $C_n$，其对数为 $2n-O(\log n)$，说明 2n 位接近信息下界。但串本身不含节点标签或边权；无序树的等价类和下界也不同。根是否使用外层括号、位索引起点和 excess 是在位置前还是含当前位置，必须全页一致。

Excess 搜索原语 ​

findclose$(i)$ 可表述为寻找最小 $j>i$ 使 excess$(j+1)=excess(i)$；enclose 则寻找左侧最近一个 excess 低一层且其匹配区间包住 $i$ 的位置。Succinct 索引用块内微表、块级最小/最大 excess 与范围最值搜索组合这些操作。

第 $k$ 个孩子不能只跳 $k$ 个字符，因为前面孩子的整棵子树长度可变；应从 first-child 开始反复跳到 findclose 后一位，或建立 degree/select 辅助。导航时间保证取决于支持哪些括号原语。

导航原语如何落到 excess ​

设节点 $v$ 的开括号位置为 $p$、匹配闭括号为 $q$。子树节点数是 $(q-p+1)/2$；第一个孩子若存在就在 $p+1$，下一个兄弟则从 $q+1$ 开始。父节点可通过向左寻找最近一个 excess 比 $excess(p)$ 小 1 的开括号得到。

高效实现把这些动作统一成三类查询：

1. findclose(p)：向右找第一个 excess 回到进入前高度的位置；
2. enclose(p)：向左找包住 $p$ 的最近更低高度；
3. fwdsearch(p,d)：向右找 excess 相对当前位置变化为 $d$ 的最早位置。

位串合法性只是前缀 excess 非负且最终为零；它不自动提供 $O(1)$ 导航。要达到简洁树的接口界，还需 rank/select、块内 excess 最值与跨块搜索索引，并把这些辅助位计入 $o(n)$。

参考资料

• Guy Jacobson, Space-Efficient Static Trees and Graphs, FOCS, 1989.
• J. Ian Munro, Venkatesh Raman, Succinct Representation of Balanced Parentheses and Static Trees, SIAM J. Comput., 2001.