替罪羊树

Published: April 19, 2019 by Daltao

Categories:
algorithm 101

替罪羊树是一种二叉搜索平衡树，相较于Splay、Treap等平衡树，其功能没有它们的强大，不能支持快速的分裂和合并操作。但是替罪羊树实现简单，并且利用它的原理可以将诸如KD-Tree等树形结构优化为平衡树。

替罪羊树每个结点都需要维护一个size属性，表示以其为根的子树的大小。每个结点只有左右两个子结点left、right。如果存在以u为根的子树，其某个子结点的size属性超过 $\alpha \cdot u.size$ （这里的 $\alpha$ 是我们预先从区间 $[0.5,1]$ 之间选取的某个常量），那么我们就重构以 $u$ 为根的子树。重构的方式非常简单，先中序遍历整个子树，将结点按序加入一个列表中，之后根据列表中排好序的结点建立完美的二分搜索树（取中点为根，递归左右）。

很显然，重构仅可能发生在修改操作后，比如插入和删除操作。由于删除操作比较复杂，我们采用惰性的方式，找到要删除的结点并打上标记，等重构的时候删除。

一次修改可能会变更整个搜索路径上的所有子树大小，如果多个子树需要重构，选择最大的那颗。

很显然第 $i$ 层的结点的size属性不可能超过 $n\cdot \alpha^i$ ，因此树的高度的上界为 $\log_{\frac{1}{\alpha}}n$ 。由于查询不涉及修改，因此时间复杂度最多为树的高度。

下面我们用势能分析法来分析删除和插入操作的摊还代价。记替罪羊树的势能为所有结点的势能之和，而一个结点的势能为该结点自从上次作为根结点被重构后发生在其子树下的插入删除操作数目乘上系数 $\beta=\frac{2\alpha+0.5}{\alpha-0.5}$ 。

对于一次插入或删除操作，我们首先找到插入位置或删除结点，这个操作的实际复杂度为 $c_i=\log_{\frac{1}{\alpha}}n$ 。但是总共有 $O(\log_{\frac{1}{\alpha}}n)$ 株子树的势能增加 $\beta$ ，因此摊还的时间复杂度为

$c'_i=c_i+w_i-w_{i-1}=(1+\beta)\log_{\frac{1}{\alpha}}n$

而对于一次以 $u$ 为根的子树的重构，我们记上一次重构后子树的大小为 $t$ ，上一次重构到这次重构之间发生的修改次数为 $k$ ，那么必定满足不等式：

$\frac{1}{2}t+k\geq \alpha(t-k)\\ \Rightarrow k\ge\frac{\alpha-0.5}{1+\alpha}t$

即此次重构所释放的势能至少为

$\beta k\ge \frac{\alpha+1}{\alpha-0.5} \cdot \frac{\alpha-0.5}{1+\alpha}t+k=t+k$ 而重构的时间费用的上界为 $O(t+k)$ ，因此摊还费用为0。

由于初始时替罪羊树没有结点，因此势能为0，而势能必定为非负，因此摊还费用和必定是实际费用和的一个上界。每次插入和删除操作的摊还费用均为 $O((1+\beta)\log_{\frac{1}{\alpha}}n)$ ，考虑到 $\alpha$ 和 $\beta$ 均为常量，因此有可以认为是 $O(\log n)$ 。