【水文】全局平衡二叉树的几个补充

· · 算法·理论

最近看到 OI 界有 top tree、仙人掌、广义串并联图等高级的东西，大开眼界。也看到全局平衡二叉树成为了常见/用数据结构之一。其发明时的需求还比较简单，现在进行几个简单的没什么大用处的补充。毕竟这是个静态的数据结构，只处理路径问题的话斜二倍增真是独具一格。

本文很水。先水一下为什么全局平衡二叉树的构造一定要用加权的二叉树。

卡线段树维护的树链剖分

考虑一棵左偏的二叉树。左儿子是长度为 2^k 的链、右儿子的左儿子是长度 2^{k-1} 的链，以此类推到 2^{\lceil\log(k)\rceil}。考虑最右边的叶子到最左边链的有关询问需要经过所有的重链，如果以朴素的线段树来维护，总的时间复杂度会达到\Theta(k^2)=\Theta(\log^2(n))。

全局平衡二叉树的几个补充

剖分方式的修改

对树上每个结点 x 定义重量 s(x) = 1 + \mathrm{sum\_of\_max\_2}\{s(c) | c\textrm{ is a child of }x\} = 1 + s(c_1) + s(c_2),\textrm{ s.t. each of }c_1, c_2\textrm{ is NULL or a child of }x,\ s(c_1) >= s(c_2)。边界条件为 s(\mathrm{NULL}) = 0。令 x 到 c_1 的边为重边、c_1 为重儿子，重链建树用的结点权重为 w(x) = 1 + s(c_2)。

这样修改后对于结点儿子较多的树更加友好，总深度更浅更平衡。二叉树的 s 退化为子树大小，与原全局平衡二叉树相同。

一个不够好的剖分方案

\mathit{dist}(x)=max\{\mathit{dist}(c_1), 1 + \mathit{dist}(c_2)\}

这里 c_1 代表令 \mathit{dist} 最大的 x 的儿子， c_2 次大，没有则为 \mathrm{NULL}。叶子结点的 \mathit{dist} 是 0。

最多 \log(n) 层链是保证了，但可惜轻节点下面的子树太重的话总体深度最差还是 \log^2(n)。还得用重量加权降低总深度，似乎可以证明总深度被 \log(s(x))+\mathit{dist}(x) bound 住，总体还是 \log(n)。

所以刚才那个改版的重量定义已经很好了，还是在说明全局平衡二叉树的魔改空间有限。

子树操作

子树操作涉及到用某个数据结构维护轻儿子森林，不能使用上文简化的重量作为剖分和加权的依据。需要使用原版的轻儿子森林总结点数（是否 +1 看需求）作为权重。

如果子树操作足够简单，用上文简化的重量作为剖分方式或许可行。例如整体染色之类的，不需要用数据结构维护轻儿子森林。但是当你思考这个子树操作全局平衡二叉树是不是做不了的时候，肯定不属于这个情况了。

子树无序的情况

若干篇提到全局平衡二叉树的文章也提到了子树操作。例如树分治小记中提到

如果将同一个点上挂着的轻儿子,同样使用加权二叉树维护,似乎就能够做到子树操作

可以选最重子树 W 做轻儿子序列的根，其余两边大致均分，可保证树深 \log(n)。因为左右两片森林的总权重差小于根部，即 L<=W+R, i.e. 2L<=L+W+R。R 同理。

森林跟轻节点列表类似，也可以用这样的方法作为顶端结构来维护，唯一差别是森林中可能有一颗“重树”，但不需要特殊处理。

子树有序的情况

如果将同一个点上挂着的轻儿子,同样使用加权二叉树维护,似乎就能够做到子树操作

这就能保证深度在 \log(n) 内了。如果子树之间有顺序规定，应该按照这种方法来处理某个重结点下面挂着的轻结点组成的森林。

轻节点要根据所规定的顺序分列重结点的左右，在重链建树过程中，一些轻结点最终挂在重链构建的树中的位置其实是它父亲的某个子孙。

子树有顺序规定时的建树方式最终的样子有些非对称：

考虑重链建树之后树上的每个重结点，如果一个重结点在最左分枝上，它将会挂上这些附加结构：“祖先先序轻森林所建平衡树结构”、“左侧轻儿子森林所建平衡树结构”（可以考虑不设此结构，将其合并到重链所建树的左儿子的“祖先先序轻森林所建平衡树结构”中）、“右侧轻儿子森林所建平衡树结构”；

其余重结点只有一个附加的“右轻儿子森林所建平衡树结构”。或许应当把重链建树之后的最左分枝看作“中轴线”了。

既然“祖先先序轻森林所建平衡树结构”是从右子树抽出来重建的一个结构，其实有多种构建方式。如果树的顺序设置之中，根结点先于子树，即是先序设置，还需要考虑“祖先先序”之中的每个祖先重结点。因此我不太喜欢刚才写的这个名字，不如改为“祖先先序树”。每个先序的祖先重结点也有多种方式加入到“祖先先序树“之中。例如加一个特殊标记到最左轻儿子上（如有）。

但我不喜欢这些不同重结点的儿子轻森林变成同一层进行建树的方法。按照原本没考虑子树顺序的建立重链平衡树的方法，右子树深度的性质已经是对数级别了，因此“祖先先序树”应当存在一种镜像建树的方法，既保证深度的对数级别，又能保持结构的优美。

因此，这个结构可以仍然是以重结点组成的链，每个重结点下方挂着一些左轻儿子来建树，只不过这条链不再具有重链的意义了，只保留“先序祖先”的意义。尽管重结点似乎被用了两份，也不需要担心树的 \log(n) 深度被破坏，并且“祖先先序树”上对应到重链所建树右子树的重结点可以互相设置指针，用于可能的访问计算、合并更新与标记。

重链建树的权重计算可以不作修改，因为按原算法所得的“祖先先序轻森林所建平衡树结构”本身是从右子树中抽出来的一个部分结构，\log(n) 的深度界依然有效。也可以作如下优化，可以考虑三个因素：若以某重结点为根，左子树总权重、右子树总权重（不含左轻儿子森林总权重）、“祖先先序轻森林所建平衡树结构”总权重，可以选取左子树总权重为这三个因素之中最大值的重结点之中最深的那一个为根。尽管是考虑三个因素，由于右子树总权重可以退化成一条链，即非常小，深度的界仍然是以2为底的 \log(n)。