替罪羊树

不一定是最快的/最短的平衡树，但是可以说是最容易理解的平衡树。——xkcdjerry

概念

各平衡树力求避免的情况均为形成类似链的结构，因为那样会导致复杂度从 O(\log n) 变为 O(n) 。其它平衡树多通过旋转来维护平衡的性质，而替罪羊的思路则为通过对不满足要求的子树进行强行重构来维持树高一定。

实现

每次插入/删除后，替罪羊树均会检查每棵子树是否满足 {size}_{rson},{size}_{lson} \leqslant \alpha size_{tot} ，如果不满足，则重构整颗子树使其变为完美二叉树（即 |size_{lson}-size{rson}| \leqslant 1 且其左右儿子均为完美二叉树）。
其它操作均同普通的二叉搜索树。

显然，重构操作可以通过中序遍历获得有序序列然后递归构建来在 O(size) 的时间内完成。

各个函数的实现 OI-wiki 的对应页面已给出，此处不再赘述。虽然 OI-wiki 给的代码就是个嘴子，建议 struct + malloc/内存池

复杂度

证明一下替罪羊树的时空复杂度正确：
由于每个点只需要维护自己的值及个数，左右儿子，树的大小等数量确定的信息，且只有 n 个点，所以空间为 O(n) 。

主要操作的时间复杂度：

  • 查找：由于每经过一个节点，子树大小最大为节点大小乘 \alpha ，所以复杂度为 O(\log_{1/\alpha} n)=O(\log n) 。（排名/按排名寻找同理）

  • 插入：如果不触发重构，复杂度同查找，为 O(\log n) ，而将一棵大小为 x 的完美二叉树插入到触发重构需要大约 \cfrac{x}{2(1-\alpha)}-x=\cfrac{2\alpha-1}{2-2\alpha}x 次插入，单次重构花费的代价为 O(x) ，均摊到每一次上的重构代价为 O(\cfrac{x}{\frac{2\alpha-1}{2-2\alpha}x})=O(\cfrac{2-2\alpha}{2\alpha-1})=O(1) ，即插入的均摊代价为 O(\log n) 。

  • 删除：类比插入，区别为触发需要的删除次数为 x-\cfrac{x}{2\alpha}=\cfrac{2\alpha-1}{2\alpha}x ，均摊重构代价为 O( \cfrac{x}{\frac{2\alpha-1}{2\alpha}x})=O(\cfrac{2\alpha}{2\alpha-1})=O(1) ，均摊代价依然为 O(\log n) 。

所以替罪羊各操作的复杂度均为 O(\log n) 。

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：AFOI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论