平衡树（进阶）
复习
- 二叉搜索树：左子树都小、右子树都大，理想
O(log n) - 删除节点与树的退化：插入顺序不好会退化成链表
- 树：用父子关系表示层次
本章为进阶内容，零基础读者可以跳过，不影响后续阅读。
TL;DR
- 平衡树通过旋转，让树始终保持矮而匀称
- 高度维持在
O(log n)，各种操作才不会退化 - AVL 树、红黑树是常见实现
- 代价是插入删除时要额外维护平衡
正文
上一章留下一个隐患：二叉搜索树可能长歪，退化成链表，性能从 O(log n) 掉到 O(n)。
问题出在“高度”。查找的代价，本质上取决于树有多高。只要能让树始终保持 O(log n) 的高度，操作就不会退化。 这类主动维持高度的树，叫平衡树（balanced tree）。
歪了就转一转
平衡树的核心手段，是旋转（rotation）。
当某个节点的左右两边高度差得太多时，通过一次局部的旋转，把树“扳正”一点：本来偏向一边的长链，被重新调整成更匀称的形状。旋转只改动少数几个指针，代价很小，却能显著降低高度。
于是，平衡树在每次插入或删除之后，都会检查是否失衡，必要时旋转修正，使整棵树始终维持在较矮的状态。
常见实现
有两种常见的平衡策略：
- AVL 树：严格要求左右高度差不超过 1，比较“严格平衡”
- 红黑树：不追求绝对平衡，允许一定偏差，但调整代价更小，工程上用得很广
可以把它们理解成两种“保持身材”的方式：一种要求极致匀称，另一种允许稍微歪一点、但维护起来更省事。严格换来更好的高度，宽松换来更少的调整。 又是取舍。
用维护成本换稳定
平衡树的收益很明确：无论插入顺序如何，查找、插入、删除都稳定在 O(log n)。 再也不用担心被“坏运气”退化成链表。
代价则是：每次修改都要花额外功夫检查并旋转，实现也比普通 BST 复杂得多。所以，若数据基本不会频繁变动，普通 BST 也许就够了；而面对不可预测的频繁增删，平衡树才真正物有所值。
到这里，我们有了能有序、能快速查找的树。接下来换一种目标：不追求全部有序，只追求“随时能拿到最大或最小的那个”。这就是下一章的堆。
思考题 1
平衡树为什么能保证操作不退化成
O(n)？
思考题 2
平衡树为了保持平衡，付出了什么代价？
小结
知识点
- 平衡树通过旋转维持较矮的高度
- 高度稳定在
O(log n)，操作才不会退化 - AVL 树严格平衡，红黑树更宽松
- 代价是插入删除时的额外调整
参考资料
- Wikipedia(zh)：平衡二叉搜索树：通过旋转保持平衡的搜索树
- Wikipedia(zh)：红黑树：工程中广泛使用的平衡树
思考题答案（仅供参考）
思考题 1
因为它会在插入删除后主动检查并旋转，使树的高度始终维持在 O(log n)。查找、插入、删除的代价都取决于高度，高度不退化，操作自然也不会退化成 O(n)。
思考题 2
每次插入或删除都要额外检查是否失衡并进行旋转，实现更复杂，操作时也多花一些计算。这是用额外维护成本，换取任何情况下都稳定的对数级性能。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪