主题
树结构进阶：AVL、红黑树与多路平衡树
1. 为什么搜索树必须继续走向“平衡”
基础章里已经讲过，普通二叉搜索树虽然在理想状态下能把查找、插入、删除做到 O(log n)，但如果插入序列不理想，它会退化成链表。这意味着仅仅满足“左小右大”还不够，系统还必须额外维护“不要太歪”。
平衡树的核心使命就是：
在动态插入和删除不断发生的情况下，仍然把树高控制在对数级。
这个目标一旦达成，查找、插入、删除三类基础操作才能真正长期稳定地保持高效率。
2. 从 BST 到平衡树，增加了什么约束
普通 BST 的约束只有一条：
- 左子树键值小于根，右子树键值大于根。
平衡树则在此基础上再加约束。例如：
- AVL 树要求左右子树高度差不能超过
1。 - 红黑树要求满足若干颜色与黑高性质，从而间接限制树高。
- B 树家族要求一个节点可容纳多个关键字，并且所有叶子在同一层。
这说明“高性能动态有序结构”不是天然存在的，而是靠额外不变量换出来的。