简洁数据结构

空间基准 ​

若规模 (n) 的对象族为 (\mathcal C_n)，空间公理库空间复杂度Space complexity计算在输入长度函数下使用的工作存储单元数量。的信息论下界是 (\lceil\log_2|\mathcal C_n|\rceil) bits。Compact 通常指常数倍该下界，succinct 指下界加低阶冗余；Encoding 只需解码整体，indexing 则要求不完全解压就回答查询。

(n) 节点有序树的数量是 Catalan 量级，约需 (2n) bits；普通指针表示却需 (\Theta(n\log n)) bits。平衡括号加 rank/select 可接近 (2n+o(n)) bits 并直接导航。一个压缩文件若每次查询都要完整解压，并不是简洁索引。

查询不变量 ​

把 DFS 进入节点记为左括号、退出记为右括号，任意前缀中左括号数不小于右括号数，末尾两者总数相等。父子、兄弟和子树导航可归约为括号匹配、excess 与 rank/select；正确性来自嵌套不变量，不是从压缩率直接推出。

模型边界 ​

$O(n)$ bits 不一定 succinct，必须相对下界。共享查表是否计空间、字长 $w=\mathrm{\Theta }(\log n)$ 与查询时间都要声明。动态更新常需更多冗余，不能把静态常数查询直接搬入动态版。

Compact、succinct 与 compressed 也不同：压缩结构可按实例熵使用更少空间，succinct 以对象族最坏信息下界为基准；self-index 还要求不保存原文也能定位内容。三者可能重叠，但不是同义标签。

有序树的括号编码全过程 ​

DFS 进入节点输出 (，离开输出 )。根带两个叶的树编码为 (()())；扫描任意前缀时 excess=左括号数减右括号数非负，末尾归零。节点的开括号位置代表节点，匹配右括号界定其整个子树区间。

父节点可由前一个 excess 更小的位置恢复，第一个孩子是紧随开括号的下一开括号，下一兄弟在匹配右括号之后。支持这些操作需要 rank/select、find-close 与 excess 搜索索引；主体 2n bits 之外的辅助结构必须合计 $o(n)$ 才保持 succinct。

信息下界的核对 ​

$n$ 节点有序树数为 Catalan $C_n$，Stirling 近似给 ${\log }_2{C}_n=2n-\mathrm{\Theta }(\log n)$。因此 2n 括号主项距最优仅低阶。若换成无序树或带标签树，对象族大小改变，下界也改变，不能继续以 2n 宣称 succinct。

查询时间与全局表 ​

Word-RAM 常数操作假设 $w=\mathrm{\Theta }(\log n)$。微块表若对所有实例共享，表大小可为 $o(n)$；若每个实例重复存一份仍要计入。导航返回节点序号还是括号位置也需接口转换。

与压缩、自索引、动态结构对照 ​

Entropy-compressed 结构按具体数据分布/零阶熵缩小，succinct 按对象族最坏下界；self-index 还能从索引恢复原对象。动态插入括号会移动后缀位置并修改 excess，静态常数查询不自动支持更新，通常要付对数时间或更多冗余。

参考资料

• Guy Jacobson, Space-efficient Static Trees and Graphs, PhD thesis, 1989.
• Raman, Raman, Rao, “Succinct Indexable Dictionaries,” TALG, 2007.