植树节刚过，大班植树活动也在今天结束了qwq…于是再来种几棵树玩玩吧 话说平衡树敲起来是真的爽
平衡树总结Ⅰ：概况
概述
二叉树大家肯定都很熟悉，它常见的操作有插入、删除、查找第k大、查询名次、查询前驱后继等等。但是普通的二叉搜索树在绝大多数情况（非随机数据）的表现非常糟糕，其深度没有“保障”，最坏情况下深度是
O
(
N
)
O(N)
O(N) 的，那么每次操作也是
O
(
N
)
O(N)
O(N) 的。这显然是不ok的。
平衡树是二叉树的改进，它能通过某种方式控制深度，实现自平衡，使得其深度总是维持在
O
(
log
N
)
O(\log N)
O(logN) 左右（替罪羊树稍有些不同）因此能在
O
(
log
N
)
O(\log N)
O(logN) 内甚至更快地进行插入、删除、查找第k大、查询名次、查询前驱后继等操作。
类别
常见的平衡树有 AVLTree、Splay、Treap、B(+)Tree、RBTree、SBTree、替罪羊树：
AVLTree：追求极致完美，任何两子树的高度差
≤
1
\le 1
≤1，增删时调整，树高总是严格保持在
O
(
log
N
)
O(\log N)
O(logN)Splay：通过巧妙设计的四种旋转来调整树高，增删查都伴随调整，使树高保持在
O
(
log
N
)
O(\log N)
O(logN)Treap：通过随机权值强行模拟随机数据插入的二叉树，增删时调整，使树高期望保持在
O
(
log
N
)
O(\log N)
O(logN)B(+)Tree：和其他平衡树不同，它是多叉树，并且利用索引实现高效的查找。其树高能保持在常数更小的
O
(
log
N
)
O(\log N)
O(logN)RBTree：emm…及其复杂精密的平衡树，增删时调整，有一套复杂的规则使树高保持在常数较小的
O
(
log
N
)
O(\log N)
O(logN)SBTree：通过子树size域的差距表现来进行旋转维护，增时调整，使树高保持在
O
(
log
N
)
O(\log N)
O(logN)替罪羊树：暴力美学，必要时直接拍平子树，然后从中间给拎起来重建二叉树，树高可“均摊”地保持在
O
(
log
N
)
O(\log N)
O(logN)
后文链接
【平衡树总结 Ⅱ】【SBT】Size Balanced Tree | E【平衡树总结 Ⅲ】【FHQ Treap】非旋Treap |【CGWR】| E