（来自算法导论十七章摊还分析思考题 \(\bold{17-3}\)，「摊还加权平衡树」）
想当年替罪羊树可能是我第一个学习的平衡树。。。但是很少有人说明它均摊 \(O(\lg n)\) 的效率是从何而来，正巧在看算导的时候有这样一个题，遂开写。
这玩意是一种 Weighted Balance Tree，靠重构来维护一个均摊较好的性能。
具体地说，选一个在 \(\frac{1}{2}\leq\alpha< 1\) 之间的一个常数 \(\alpha\) 作为平衡因子。如果一个节点 \(u\) 的左右子树的大小都不大于 \(\alpha\operatorname{size}(u)\)，那么我们认为 \(u\) 是 \(\alpha\) 平衡的，若所有节点都是 \(\alpha\) 平衡的那么这棵树就是 \(\alpha\) 平衡的。
首先说明如果 \(T\) 对于 \(\alpha\ (\frac{1}{2}\leq\alpha<1)\) 是平衡的，那么这棵树的树高是 \(O(\lg n)\)。对于一个点 \(u\) 从根开始向下走，每向下走一步那么以它为根的子树大小至多乘上 \(\alpha\)，叶子的大小为 \(1\)，即 \(n\alpha^{h}=1\)，得到 \(h=\log_{\alpha}\frac{1}{n}=\log_{\frac{1}{\alpha}}n=O(\lg n)\)。
如此我们就知道了一棵平衡的替罪羊树它的查询效率是 \(O(\lg n)\) 的，接下来我们着重分析它是如何在插入操作中维护平衡。
对于节点 \(u\in T\) 及它的左右儿子 \(u_l,u_r\) 定义
\[\Delta(u)=|\operatorname{size}(u_l)-\operatorname{size}(u_r)| \]定义势能函数
\[\Phi(T)=\frac{\sum_{u\in T,\Delta(u)\geq 2}\Delta(u)}{2\alpha-1} \]首先证一个引理是对于 \(\alpha=\frac{1}{2}\) 平衡的 \(T\) 的势能为 \(0\)。若势能大于 \(0\) 则存在 \(u\in T\) 有 \(|\operatorname{size}(u_l)-\operatorname{size}(u_r)|\geq 2\)，不妨设是 \(\operatorname{size}(u_l)-\operatorname{size}(u_r)\geq 2\)，由于它是 \(\frac{1}{2}\) 平衡的，故有 \(\operatorname{size}(u_l)\leq\frac{\operatorname{size}(u)}{2}=\frac{\operatorname{size}(u_l)+\operatorname{size}(u_r)+1}{2}\) 即 \(\operatorname{size}(u_l)\leq\operatorname{size}(u_r)+1\)，带到最初的式子中有 \(\operatorname{size}(u_r)+1-\operatorname{size}(u_r)\geq 2\) 即 \(1\geq 2\) 导出矛盾。
重构操作在 \(O(\operatorname{size}(u))\) 的时间下将 \(\operatorname{subtree}(u)\) 重构为 \(\frac{1}{2}\) 平衡的，这可以直接像类似线段树建树的分治方法做到。下面我们将证明重构操作是均摊 \(O(1)\) 的。
重构操作的均摊代价为
\[\begin{aligned} \hat{c}&=O(\operatorname{size}(u))+\Delta\Phi(T)\\ &=O(\operatorname{size}(u))+\Delta\Phi(\operatorname{subtree}(u))\\ &=O(\operatorname{size}(u))+0-\frac{\sum_{v\in\operatorname{subtree(u)},\Delta(v)\geq 2}\Delta(v)}{2\alpha-1}\\ \end{aligned}\]我们考察 \(u\) 的情况，它是 \(\alpha\) 不平衡的，不妨设 \(\operatorname{size}(u_r)>\operatorname{size}(u_l)\)，则有
\[\begin{aligned} \Delta(u)&=\operatorname{size}(u_r)-\operatorname{size}(u_l)\\ &\geq \alpha\operatorname{size}(u)+1-(1-\alpha)\operatorname{size}(u)+1\\ &=(2\alpha-1)\operatorname{size}(u)+2\\ \end{aligned}\]它是大于 \(2\) 的，故我们想用它来支付掉均摊代价
\[\begin{aligned} \hat{c}&\leq O(\operatorname{size}(u))-\frac{\Delta(u)}{2\alpha-1}\\ &\leq O(\operatorname{size}(u))-\frac{(2\alpha-1)\operatorname{size}(u)}{2\alpha-1}\\ &=O(1)\\ \end{aligned}\]最终得到重构的均摊代价是 \(O(1)\) 的。
接下来考虑分析插入，维护 \(\alpha\) 平衡的情况下，其实际代价是树高 \(h=O(\lg n)\)，插入一个点会使一条链上的 \(\Delta\) 均增或减 \(1\)，而这个增量也不会超过树高 \(h\)。
\[\begin{aligned} \hat{c}&=h+\Delta\Phi(T)\\ &\leq h+\frac{h}{2\alpha-1}\\ &=(1+\frac{1}{2\alpha-1})h\\ &=O(\lg n) \end{aligned}\]综上我们这样维护替罪羊树：如普通二叉搜索树的方式一样插入查询，插入完成时检查是否存在点不满足 \(\alpha\) 平衡，若存在则找到深度最低的不平衡点再将以其为根的子树进行重构，这样可以保证在插入和查询的时候整棵树是 \(\alpha\) 平衡的。根据上面的分析，所有的操作都将在 \(O(\lg n)\) 的均摊效率下运行。
标签：frac,替罪羊,operatorname,Delta,alpha,aligned,效率,size From： https://www.cnblogs.com/yukari1735/p/17133794.html