主题
树结构进阶：AVL、红黑树与多路平衡树
1. 为什么搜索树必须继续走向“平衡”
基础章里已经讲过，普通二叉搜索树虽然在理想状态下能把查找、插入、删除做到 O(log n)，但如果插入序列不理想，它会退化成链表。这意味着仅仅满足“左小右大”还不够，系统还必须额外维护“不要太歪”。
平衡树的核心使命就是：
在动态插入和删除不断发生的情况下，仍然把树高控制在对数级。
这个目标一旦达成，查找、插入、删除三类基础操作才能真正长期稳定地保持高效率。
2. 从 BST 到平衡树，增加了什么约束
普通 BST 的约束只有一条：
- 左子树键值小于根，右子树键值大于根。
平衡树则在此基础上再加约束。例如：
- AVL 树要求左右子树高度差不能超过
1。 - 红黑树要求满足若干颜色与黑高性质，从而间接限制树高。
- B 树家族要求一个节点可容纳多个关键字，并且所有叶子在同一层。
这说明“高性能动态有序结构”不是天然存在的，而是靠额外不变量换出来的。
3. AVL 树：严格平衡的代表
AVL 树是最早被提出的自平衡二叉搜索树。它对每个节点都维护一个平衡因子：
text
balanceFactor = height(left) - height(right)AVL 要求任意节点的平衡因子只能是 -1、0、1。
3.1 AVL 为什么查找性能优秀
因为它的平衡约束严格，树高被压得更低，所以查找路径通常更短。它的代价是插入和删除时需要更频繁地维护高度并做旋转。
3.2 四种失衡类型
AVL 插入或删除后，某个祖先节点可能失衡。经典分为四类：
- LL：左孩子的左子树过高。
- RR：右孩子的右子树过高。
- LR：左孩子的右子树过高。
- RL：右孩子的左子树过高。
4. 旋转不是“技巧”，而是局部重构
旋转的本质是：
在不破坏 BST 中序有序性的前提下，局部调整父子关系，降低树高。
4.1 单右旋
右旋后：
4.2 Go 里的基础旋转实现
go
package avl
type Node struct {
Key int
Height int
Left *Node
Right *Node
}
func height(n *Node) int {
if n == nil {
return 0
}
return n.Height
}
func updateHeight(n *Node) {
lh, rh := height(n.Left), height(n.Right)
if lh > rh {
n.Height = lh + 1
} else {
n.Height = rh + 1
}
}
func rotateRight(y *Node) *Node {
x := y.Left
t2 := x.Right
x.Right = y
y.Left = t2
updateHeight(y)
updateHeight(x)
return x
}
func rotateLeft(x *Node) *Node {
y := x.Right
t2 := y.Left
y.Left = x
x.Right = t2
updateHeight(x)
updateHeight(y)
return y
}4.3 AVL 插入核心逻辑
go
func balanceFactor(n *Node) int {
if n == nil {
return 0
}
return height(n.Left) - height(n.Right)
}
func Insert(root *Node, key int) *Node {
if root == nil {
return &Node{Key: key, Height: 1}
}
if key < root.Key {
root.Left = Insert(root.Left, key)
} else if key > root.Key {
root.Right = Insert(root.Right, key)
} else {
return root
}
updateHeight(root)
bf := balanceFactor(root)
if bf > 1 && key < root.Left.Key {
return rotateRight(root)
}
if bf < -1 && key > root.Right.Key {
return rotateLeft(root)
}
if bf > 1 && key > root.Left.Key {
root.Left = rotateLeft(root.Left)
return rotateRight(root)
}
if bf < -1 && key < root.Right.Key {
root.Right = rotateRight(root.Right)
return rotateLeft(root)
}
return root
}这段代码体现了 AVL 的代价模型：
每次插入不仅要像 BST 一样找位置，还要回溯更新高度并在必要时旋转修复。
5. 红黑树：放松平衡，换更低维护成本
红黑树也是自平衡 BST，但它不追求 AVL 那样严格的高度平衡，而是通过颜色规则保证“不会太歪”。
红黑树经典性质：
- 每个节点非红即黑。
- 根节点是黑色。
- 所有空叶子视为黑色。
- 红节点不能有红孩子。
- 从任一节点到其所有后代空叶子的路径上，黑节点数相同。
这些性质共同推出一个结论：
红黑树的最长路径不会超过最短路径的两倍，因此高度仍然是 O(log n)。
6. 红黑树为什么广泛用于工程
与 AVL 相比，红黑树的平衡没那么严格，因此：
- 查找路径可能略长一点。
- 但插入和删除时的旋转次数通常更少。
- 对大量动态更新更友好。
这就是为什么很多语言标准库、内核和中间件更偏爱红黑树而不是 AVL。
7. 红黑树插入修复的思路
新插入节点通常先染成红色，避免直接破坏黑高。若出现“红节点的父节点也是红色”，才需要修复。修复核心围绕三类情况展开：
- 叔叔节点为红：变色并向上继续修复。
- 叔叔节点为黑，且形成折线：先旋成直线。
- 叔叔节点为黑，且形成直线：旋转并重新着色。
7.1 红黑树节点结构
go
package rbtree
type Color bool
const (
Red Color = true
Black Color = false
)
type Node struct {
Key int
Color Color
Left *Node
Right *Node
Parent *Node
}7.2 为什么这里只给出结构和修复思路
红黑树完整实现，尤其是删除修复，代码和边界条件都明显比 AVL 更重。教学上更重要的是先把“为什么能平衡”“为什么修复围绕颜色和旋转进行”讲透，而不是先背一长串分支。
如果后面继续扩展，这一页完全可以再单拆出“红黑树插入修复推演”和“红黑树删除修复推演”。
8. AVL 与红黑树的比较
| 维度 | AVL | 红黑树 |
|---|---|---|
| 平衡程度 | 更严格 | 更宽松 |
| 查找性能 | 通常更优 | 略逊但仍为 O(log n) |
| 插删维护 | 更频繁旋转 | 通常旋转更少 |
| 工程采用 | 较多见于特定索引场景 | 标准库、内核中更常见 |
不要简单说“谁更高级”。本质上是：
- AVL 更偏向读性能和严格高度控制。
- 红黑树更偏向动态更新时的整体工程平衡。
9. 多路平衡树：为什么数据库不爱普通二叉树
当数据规模大到需要频繁访问磁盘或 SSD 页面时，二叉树分支太少，树高容易上升，随机 I/O 次数变多。这就是 B 树和 B+ 树的重要性。
多路平衡树的核心思想是：
- 一个节点放多个关键字。
- 一个节点拥有多个孩子。
- 尽量让树更矮，减少外存访问层数。
9.1 B 树与 B+ 树的差别
- B 树的内部节点和叶子节点都可存记录。
- B+ 树通常把完整记录都放叶子层，内部节点主要存索引键。
- B+ 树叶子层往往串成链，更适合范围扫描。
这也是数据库索引广泛采用 B+ 树的原因：
既能做单点查找，也能做顺序范围遍历。
10. 树结构进阶的主线回顾
这页最核心的不是代码量，而是三条思路：
- BST 高效的前提是树高不能失控。
- AVL 与红黑树都用“旋转 + 额外不变量”维护对数级高度。
- 当存储层进入外存时代，多路平衡树会比普通二叉树更自然。
11. 学完这一页后应该会回答的问题
- AVL 为什么需要区分 LL、RR、LR、RL？
- 旋转为什么不会破坏 BST 的中序有序性？
- 红黑树为什么虽然“不那么平”，却仍然能保证
O(log n)高度？ - 为什么数据库索引常用 B+ 树而不是 AVL 或普通 BST？
把这些问题讲清楚，树结构这一块才算真正跨过了“基础理解”进入“体系理解”。