替罪羊树(Scapegoat Tree) - riteme.site

[riteme]

https://riteme.github.io/blog/2016-4-6/scapegoat.html

[minghu6]

我是很不理解AVL难以实现或者代码又臭又长的说法，在实现过程中，AVL增删时重平衡的代码非常少而且易于理解，特别是比起红黑树来！

红黑树（RB、LLRB）不仅代码冗长，还情况复杂，不好理解（特别是删除时的重平衡，粗数了一下，代码行数RB是AVL的小3倍，LLRB也有1.5倍，而且LLRB比RB更不好理解），关于它俩的评价应该掉个个儿。

[minghu6]

另外插入操作时要多一个步骤是复位被惰性删除的节点

[minghu6]

插入的时候就如果找所有替罪羊节点，如果向上全部重构会导致插入开销太大，耗时的感觉几乎是二次的; 但如果只找第一个替罪羊节点，有时候个别随机输入会导致查询接近原始构造的二叉树！ （测试alpha：0.6, 0.7，0.8,表现差别不大）

我看有的实现把检查平衡的函数换成完全二叉树的测试，插入的时候也是只找第一个替罪羊节点，

fn is_unbalanced(&self, alpha: f32) -> bool {
    // max(size(self.left), size(self.right)) > alpha as usize * self.size
    size(self.left).abs_diff(size(self.right)) > 1
}

这样测试下来感觉不错，插入和查询的性能表现都贴近其他自平衡二叉树

[FATE-512]

"slice提取区间Splay乱搞"，我问你：我都写Splay了，还写什么替罪羊树。