简洁有序树 | Codeboy's Blog

表示对象与空间目标

简洁有序树表示一棵有根、有序、无节点标签的树。若树有 (n) 个节点，深度优先遍历在进入节点时写左括号，离开时写右括号，便得到长度 (2n) 的平衡括号串。孩子顺序体现在各子树出现的先后，因此编码不需要另存指针。

仅保存括号串还不够支持快速导航。标准结果是在 word-RAM 上增加 (o(n)) bit 的分层索引，以总计 [ 2n+o(n)\ \text{bit} ] 支持常数时间的常用树操作；字长通常假设为 (w=\Omega(\log n))，使一个位置或计数能够放进一个机器字。

括号原语如何变成树操作

令左括号记为 (+1)，右括号记为 (-1)，前缀和称为 excess。一个节点由其左括号位置 (i) 代表。导航依赖下列原语：

(\operatorname{findclose}(i)) 找到与位置 (i) 的左括号匹配的右括号；
(\operatorname{findopen}(j)) 从右括号 (j) 找回匹配的左括号；
(\operatorname{enclose}(i)) 找到包住整段 (i\ldots\operatorname{findclose}(i)) 的最内层括号对；
excess 的 rank/select 与区间最小值索引负责按深度寻找括号。

于是非根节点的 parent 是 (\operatorname{enclose}(i))。若 (i+1) 是左括号，它就是 first-child；否则节点为叶。令 (j=\operatorname{findclose}(i)+1)，当 (j) 仍处在父节点的括号内部且为左括号时，(j) 就是 next-sibling。previous-sibling 可先看 (i-1)：若那里是右括号，就取 (\operatorname{findopen}(i-1))。

节点深度等于读到其左括号后 excess 减一。子树恰好占据从 (i) 到 (\operatorname{findclose}(i)) 的完整括号段，因此 [ \operatorname{subtree_size}(i) =\frac{\operatorname{findclose}(i)-i+1}{2}. ] degree、按序第 (k) 个孩子、某深度的祖先等接口还要借助更完整的 excess 搜索结构；不能因为 parent 很容易归约，就默认所有导航都由裸括号串在常数时间完成。

一棵四节点树的完整恢复

设根 (r) 的孩子依次为 (a,b)，而 (a) 有唯一孩子 (c)。遍历依次进入 (r,a,c)，离开 (c,a)，再进入并离开 (b)，最后离开 (r)，得到 [ ((())()). ] 左括号位置 (1,2,3,6) 分别代表 (r,a,c,b)。位置 3 的匹配右括号是 4，包围它的最内层括号从位置 2 开始，所以 (c) 的父节点是 (a)。位置 2 的匹配括号在 5，故 (a) 的子树大小为 ((5-2+1)/2=2)。

从 (a) 找下一个兄弟时，跳到 (\operatorname{findclose}(2)+1=6)，正好落在 (b) 的左括号。相反，从 (c) 跳到位置 5 得到右括号，说明 (c) 没有兄弟。这个判断同时利用了匹配位置和父括号边界，不能只检查后一位是否为左括号。

为什么两位每节点已接近下界

含 (n) 个节点的有根有序树数量是 Catalan 数 [ C_{n-1}=\frac{1}{n}\binom{2n-2}{n-1}. ] 任何能区分所有树形的编码都至少需要 [ \log_2 C_{n-1}=2n-\Theta(\log n) ] bit。BP 的 (2n) bit 主体只比信息论下界多低阶量；导航索引若控制在 (o(n)) bit，总空间仍是简洁的。这里的下界针对有序树，不能直接拿来描述孩子无序时的同构类数量。

索引为何只需低阶空间

实现通常把括号串分成小块与超块。块内的 excess 变化可由预计算表回答，超块保存累计 rank、局部极值和跨块匹配摘要；少数跨度很大的匹配再由稀疏结构处理。块长按 (\Theta(\log n)) 的一小部分选择时，表由所有短比特模式共享，不会为每个节点复制常数个机器字。

这个构造解释了 (o(n)) 的来源，也揭示一个常见误读：括号本体是 (2n) bit，但常数时间查询依赖额外索引。若实现用两个普通 64 位指针保存每个节点，即使逻辑仍用 BP 描述，也已经不满足上述空间保证。

表示选择与失效边界

DFUDS 也能以 (2n+o(n)) bit 表示有序树，但它按节点度数写一串左括号再写右括号，某些 child/degree 归约更自然，位置含义与 BP 不可混用。无序树需要消除孩子排列造成的重复计数，编码下界和规范化方法都不同。

节点标签、边权和应用数据不包含在 (2n+o(n)) 的树形空间里，必须另行计数。静态索引也不支持在括号串中任意插入一对括号；动态树需要动态简洁位向量或动态括号结构，并为重平衡与更新支付额外时间。

参考资料

Guy Jacobson, Space-Efficient Static Trees and Graphs, FOCS, 1989.
J. Ian Munro and Venkatesh Raman, Succinct Representation of Balanced Parentheses and Static Trees, SIAM Journal on Computing, 2001.
Gonzalo Navarro, Compact Data Structures: A Practical Approach, Cambridge University Press, 2016.

表示对象与空间目标 ​

括号原语如何变成树操作 ​

一棵四节点树的完整恢复 ​

为什么两位每节点已接近下界 ​

索引为何只需低阶空间 ​