替罪羊树

同学问我替罪羊树和带插入的区间k小, 我说没有太大兴趣, 结果立了个flag...... 本文不加证明地介绍了替罪羊树, 这种简洁高效, 不用旋转的重量平衡树. link: - cls的集训队论文 <重量平衡树和后缀平衡树在信息学奥赛中的应用> - vfk的论文 <对无旋转操作的平衡树的一些探究> - 发明人的论文 Scapegoat Trees - neither_nor神犇对发明人论文的翻译

重量平衡树

每次操作影响的最大子树的大小是最坏, 或均摊, 或期望 的平衡树叫重量平衡树.

替罪羊树是不采用旋转机制的重量平衡树. 插入均摊 , 查询和删除 .

Treap是采用旋转机制的重量平衡树. 插入, 查询, 删除期望 . 插入的旋转次数是 的, 每次旋转重构子树, 期望复杂度 . 删除直接重构子树, 时间同样是期望 的.

两种平衡

如果一棵二叉树 的高度满足 , 则称 是 高度平衡的. 记

如果一个节点 满足 , 则称 是 大小平衡的. 如果 的所有节点都 大小平衡, 则称 大小平衡.

大小平衡是高度平衡的充分非必要条件. 从最深的节点往上爬, 连续使用大小平衡的定义, . 反之不然.

替罪羊树

替罪羊树的每个节点, 除了左右儿子的指针, 不用记录其他信息. 方便起见, 可以记录 .

查询

替罪羊树的查询和普通BST一样.

插入

先像普通BST一样插入. 维护 (无删除则省略). 如果深度 , 回溯的时候找到第一个非 大小平衡的节点 , 称 为替罪羊节点. 将以 为根的子树重建成1/2大小平衡的.

一定存在替罪羊节点, 因为非高度平衡可以推出非大小平衡.

重建操作可以在 的时间内完成. 简单地中序遍历一遍, 用 的空间即可. 也可以用 (栈) 空间的拍扁重建法.

删除

先像普通BST一样删除. 如果 , 重建整棵树, 置 为 .

性质

如果只有插入操作, 替罪羊树是 高度平衡的.

如果同时有插入,删除, 替罪羊树是非严格 高度平衡的, 即 .

可以根据需要来取. 通常取0.6~0.7.