10.4　平衡树思想：AVL 与红黑树概览

学习目标：学完本节，你能

说清旋转是怎么在"不破坏 BST 性质"的前提下改变树形的；
说出 AVL 的四种不平衡情况和对应的调整方式；
说出 AVL 与红黑树的取舍，以及为什么工程上多用红黑树；
知道 .NET 里该用什么替代"手写 BST"。

先修：10.3（退化问题）。 固定术语：旋转、平衡因子、AVL 树、红黑树、自平衡。 环境与版本：.NET 8 / C# 12。 预计阅读：30 分钟。

一、旋转：改变形状，不改变顺序

10.3 节找到了问题的根源：树形由插入顺序决定，而 BST 自己无法调整。

解决手段是一个叫"旋转"（Rotation）的小操作：

旋转能在不改变中序遍历顺序的前提下，改变树的结构。

先看最直观的例子。插入 10, 20, 30（递增）：

    普通 BST:              左旋后:
       10                    20
        \                   /  \
         20       -->      10    30
           \
            30

实测：

    普通 BST:  10
                └─ 20
                   └─ 30     高度 = 2

    AVL 树:    20
              /  \
            10    30              高度 = 2（触发了 1 次旋转）

注意：20 成了新的根，10 变成它的左孩子，30 还是右孩子。

中序遍历仍然是 10 20 30 —— BST 性质完全没有被破坏 ✓

这就是旋转的全部意义：只调整"谁是谁的孩子"，不动"谁大谁小"。

左旋的代码：

/// <summary>左旋：把右孩子提上来当根。</summary>
static AvlNode RotateLeft(AvlNode x)
{
    var y = x.Right!;
    var t2 = y.Left;

    y.Left = x;           // x 变成 y 的左孩子
    x.Right = t2;         // T2 挂到 x 的右边（保持 BST 性质）

    UpdateHeight(x);      // 先更新下面的
    UpdateHeight(y);
    return y;             // 返回新的子树根
}

右旋是对称的：

static AvlNode RotateRight(AvlNode y)
{
    var x = y.Left!;
    var t2 = x.Right;

    x.Right = y;
    y.Left = t2;

    UpdateHeight(y);
    UpdateHeight(x);
    return x;
}

t2 那一步是保持 BST 性质的关键。

在右旋里，T2 是 x 的右子树 —— 它的值都在 x 和 y 之间。旋转后 y 成了 x 的右孩子，所以 T2 应该挂到 y 的左边（因为它比 y 小）。

看起来只是"换了个位置"，但每一条指针的调整都有 BST 性质在背后约束。

二、AVL：给每个节点记一个"高度"

AVL 树是最早的自平衡二叉搜索树（1962 年由 Adelson-Velsky 和 Landis 提出，名字就是两位作者姓氏的缩写）。

它的规则很简单：

每个节点的左右子树高度差不超过 1。

这个差值叫平衡因子（Balance Factor）：

$$\text{BF} = \text{左子树高度} - \text{右子树高度}$$

AVL 要求 BF ∈ {-1, 0, 1}。

所以每个节点要额外记录自己的高度：

public class AvlNode
{
    public int Value;
    public AvlNode? Left;
    public AvlNode? Right;
    public int Height = 1;          // 多存一个高度
}

插入时，沿着递归返回的路径自底向上检查平衡因子，一旦超标就旋转。

三、四种不平衡情况

失衡有四种形态，对应四种调整方式：

情况	插入位置	调整方式	触发场景
LL	左孩子的左边	一次右旋	递减序列插入
RR	右孩子的右边	一次左旋	递增序列插入
LR	左孩子的右边	先左旋再右旋	锯齿形插入
RL	右孩子的左边	先右旋再左旋	锯齿形插入

// 情况 LL：左边太高，且新节点插在左孩子的左边 -> 一次右旋
if (bf > 1 && value < node.Left!.Value)
    return RotateRight(node);

// 情况 RR：右边太高，且新节点插在右孩子的右边 -> 一次左旋
if (bf < -1 && value > node.Right!.Value)
    return RotateLeft(node);

// 情况 LR：左边太高，但新节点插在左孩子的右边 -> 先左旋再右旋
if (bf > 1 && value > node.Left!.Value)
{
    node.Left = RotateLeft(node.Left);
    return RotateRight(node);
}

// 情况 RL：右边太高，但新节点插在右孩子的左边 -> 先右旋再左旋
if (bf < -1 && value < node.Right!.Value)
{
    node.Right = RotateRight(node.Right);
    return RotateLeft(node);
}

实测 LR 情况：

  验证 LR：插入 30, 10, 20（锯齿形）
    结果根节点 = 20（中间的 20 被提上来了）
    触发了 2 次旋转（因为是 LR，要转两次）
    树仍然平衡：True

为什么 LR 需要转两次？

  插入 30, 10, 20 后：
        30
       /
      10
        \
         20      <- 这条"之"字形的路径让一次旋转解决不了

  第一步：对 10 左旋 ->        30
                              /
                             20
                            /
                           10

  第二步：对 30 右旋 ->      20
                            /  \
                          10    30

记忆方法：

"直的"（LL、RR）转一次

"弯的"（LR、RL）转两次，而且第一次旋转的作用就是把"弯的掰直"

四、实测：AVL 真的能防退化

用“递增数据”插入 100,000 个元素（这是让普通 BST 退化的最坏输入）：

    结构           |           树高 |         插入耗时 | 说明
    ------------------------------------------------------------------
    普通 BST       |       99,999 |    3790.2 ms | 完全退化成链
    AVL 树         |           17 |      19.3 ms | 高度 = 17，触发 99983 次旋转

    理论最优高度 log2(100,000) ≈ 16.6

AVL 把高度从 99,999 压到了 17 —— 几乎正好是理论最优的 16.6。

代价是触发了 99,983 次旋转（平均每次插入约 1 次）。

五、"平衡的代价"到底体现在哪

注意上面那组数据：AVL 不仅高度低，连插入都更快（19.3 ms vs 3790.2 ms）。

这是不是说明"平衡没有代价"？

不是。 上面那组数据之所以 AVL 快 196 倍，是因为普通 BST 已经退化了 —— 它每次插入都要走到链的末尾，总共 $O(n^2)$。

要看清"平衡的代价"，必须用"本来就不会让 BST 退化"的数据 —— 比如随机输入：

  【场景 B】随机输入 —— 插入 100,000 个元素：
    普通 BST:      10.2 ms   高度 43（也是平衡的）
    AVL 树  :      29.6 ms   高度 20，触发 69,884 次旋转
    -> 这种情况下 AVL 慢 2.91 倍

随机输入下，普通 BST 自己就是平衡的（高度 43），所以 AVL 的"维护成本"就显出来了 —— 慢 2.91 倍。

把这组数据和上一组放在一起：

输入类型	普通 BST	AVL	谁赢
递增（真实数据常见）	3790.2 ms	19.3 ms	AVL 快 196 倍
随机	10.2 ms	29.6 ms	普通 BST 快 2.91 倍

结论：

"平衡的代价"只在"数据本来就不会让 BST 退化"时才看得出来。

而一旦数据有序（现实中最常见的情况），普通 BST 的代价会远远超过 AVL 的维护成本。

这就是工程上必须用自平衡树的理由 —— 你没法保证输入是随机的。

六、AVL vs 红黑树

AVL 是最严格的自平衡树，但它不是工程上最常用的。C# 的 SortedDictionary 用的是红黑树。

维度	AVL 树	红黑树
平衡程度	严格（高度差 ≤ 1）	近似（最长路径 ≤ 2 倍最短）
树高上界	$1.44 \log_2 n$	$2 \log_2 n$
查找速度	更快（树更矮）	稍慢
插入/删除速度	更慢（旋转更频繁）	更快
适用场景	读多写少	读写均衡
典型实现	较少见	C# `SortedDictionary`

为什么工程上选红黑树而不是 AVL？

因为"读写均衡"比"读多写少"更常见。

红黑树的平衡条件更宽松，插入删除时需要的旋转更少（统计上约少 40%）—— 换来的是稍微高一点的树。

这是一笔典型的工程交易：用"稍微慢一点的查找"换"明显更快的增删"。

而且注意：$1.44\log n$ 和 $2\log n$ 的差别，在 $n = 10^6$ 时是 29 次和 40 次比较 —— 绝对值差距不大，但旋转次数的差距在频繁增删的场景下会累积起来。

其他自平衡方案：

方案	平衡策略	特点
Treap	随机优先级	实现简单，期望平衡（没有硬保证）
Splay 树	访问后提到根	适合"访问局部性强"的场景，均摊 $O(\log n)$
B 树 / B+ 树	多路平衡	磁盘友好，数据库索引的标准选择

最后一行值得单独说：为什么数据库不用二叉树？

因为磁盘 I/O 的粒度是"块"（通常 4KB）。二叉树每个节点只存一个键，读一个节点就要一次磁盘 I/O —— 树高 20 就要 20 次 I/O。

B+ 树每个节点存几百个键（正好填满一个磁盘块），树高只有 3～4 层。

从 20 次 I/O 降到 4 次 —— 这是数量级的差距。

这就是"同一个数据结构在不同存储介质上要有不同变体"的经典例子（8.1 节的外部排序也是同一个道理）。

七、.NET 里该用什么

实测对比（插入 100,000 个递增元素）：

    SortedDictionary（.NET 内置）:     74.7 ms
    我们手写的 AVL            :     19.3 ms

有意思的是：我们手写的 AVL 反而更快（快约 4 倍）。

原因是它只存 int、只支持插入和查找，没有任何通用性开销；而 SortedDictionary 要处理泛型、比较器委托、键值对、删除、迭代器……

但工程上仍然应该用 SortedDictionary，因为：

它经过充分测试，处理了各种边界情况（重复键、删除、并发枚举……）

它支持任意可比较的键类型，我们的 AVL 只支持 int

它提供了完整的 API（Remove、枚举器、索引器……）

最关键：我们的 AVL 只实现了插入，没有实现删除 —— 而删除才是自平衡树最难的部分（要在删除后也维持平衡，旋转的情形比插入更复杂）

所以 .NET 里的正确选择是：

需求	用什么	内部实现
需要有序的字典	`SortedDictionary<TKey, TValue>`	红黑树
需要有序的集合	`SortedSet<T>`	红黑树
需要有序 + 内存紧凑 + 支持索引访问	`SortedList<TKey, TValue>`	有序数组（插入 $O(n)$）
不需要有序	`Dictionary<TKey, TValue>`	哈希表（$O(1)$ 更快）

最后一行是最重要的提醒：

如果你的需求里没有"有序"，那就不要用 SortedDictionary —— Dictionary 的 $O(1)$ 查找更快、内存也更省。

"我需要有序吗？" —— 这个问题应该在选型时明确回答，而不是随手选一个。

八、练习

练习 10.4.1（手写旋转）对下面这棵树执行一次左旋（以 30 为轴）：

(a) 画出旋转后的树。 (b) 中序遍历分别是什么？变了吗？ (c) 旋转后树变矮了吗？

练习 10.4.2（判断失衡类型）下面三种插入序列，分别会触发哪种旋转（LL/RR/LR/RL）？ (a) 依次插入 50, 30, 10 (b) 依次插入 50, 70, 90 (c) 依次插入 50, 30, 40

练习 10.4.3（判断）判断对错并说明理由： (a) 旋转会改变中序遍历的顺序。 (b) AVL 树的高度一定不超过 $\log_2 n$。 (c) 红黑树的查找比 AVL 慢，所以 AVL 更好。 (d) 既然 AVL 能保证平衡，那所有场景都该用它。

练习 10.4.4（工程判断）一个系统要从数据库读取 50 万条订单，按订单号建立索引以支持：

按订单号快速查找
按订单号范围查询（比如"找出 NO.100000 到 NO.200000 之间的所有订单"）

(a) 用 Dictionary 能实现吗？ (b) 用 SortedDictionary 呢？插入 50 万条（有序）的代价是多少？ (c) 有没有更好的方案？

练习 10.4.5（挑战·为什么删除更难）本节实现的 AVL 只支持插入，没有实现删除。 (a) 想一下：删除一个节点后，可能破坏哪些节点的平衡？ (b) 为什么说"删除后的平衡调整比插入更复杂"？ (c) 具体来说，插入时最多需要几次旋转？删除呢？

九、练习答案

10.4.1

(a) 左旋后：

（左旋是"把右孩子提上来当根"：30 提上来，20 变成 30 的左孩子，30 原来的左孩子（空）挂到 20 的右边。）

(b) 中序遍历：

旋转前：10 20 30 40
旋转后：10 20 30 40

没有变 ✓ —— 这正是旋转的核心性质。

(c) 没有变矮。

旋转前：20 → 30 → 40 这条路径长度是 2，树高 2
旋转后：30 → 20 → 10 和 30 → 40，最长路径 2，树高还是 2

这个例子说明：单次旋转不一定能降低整棵树的高度 —— 它只是局部调整。

AVL 靠的是"每次插入后都检查并调整"，累积起来才能保持整体平衡。

10.4.2

(a) 50, 30, 10 → LL 情况（左孩子的左边）→ 一次右旋。

  插入后:        50              右旋后:      30
                /                            /  \
              30                           10    50
             /
           10

(b) 50, 70, 90 → RR 情况（右孩子的右边）→ 一次左旋。

  插入后:      50                左旋后:        70
                 \                             /  \
                  70                         50    90
                    \
                     90

(c) 50, 30, 40 → LR 情况（左孩子的右边）→ 先左旋再右旋。

  插入后:        50              第一步(对30左旋):   50        第二步(对50右旋):   40
                /                                  /                             /  \
              30                                  40                           30    50
                \                                /
                 40                            30

结果根节点是 40 ✓

10.4.3

(a) 错。 旋转完全不改变中序遍历的顺序 —— 这是它"合法"的根本原因。

旋转只改变"谁是谁的孩子"，不改变"谁在谁左边"。而中序遍历的顺序正是由"左右关系"决定的。
(b) 错。 AVL 的高度上界是 $1.44 \log_2 n$，不是 $\log_2 n$。

$\log_2 n$ 是完美二叉树的高度，而 AVL 只保证"高度差 ≤ 1"，达不到完美。

实测印证：$n = 100{,}000$ 时，理论最优是 16.6，我们的 AVL 高度是 17 —— 非常接近但略高。
(c) 错。 这是一个"局部最优 ≠ 全局最优"的典型例子。

红黑树的查找确实稍慢（树高上界 $2\log n$ vs $1.44\log n$），但它的插入删除更快（旋转更少）。

在"读写均衡"的场景下，红黑树的总代价更低 —— 这就是它成为工程标准的原因。

而且那个"稍慢"在实际中差别不大：$n = 10^6$ 时是 29 次 vs 40 次比较，都是微秒级。
(d) 错。 至少有三个理由：
1. 如果不需要有序，Dictionary（哈希表）更快更省 —— AVL 的优势根本用不上
2. 如果读写均衡，红黑树的综合表现更好
3. 如果数据在磁盘上，B+ 树才是正确选择（节点扇出大，减少 I/O）
"最强的"不等于"最合适的"。

10.4.4

(a) Dictionary 做不到"范围查询"。

按订单号快速查找 ✓（$O(1)$）
范围查询 ✗ —— 哈希表的键是无序的，"找出 NO.100000 到 NO.200000 之间"只能全量遍历（$O(n)$）

(b) SortedDictionary 可以，插入 50 万条有序数据的代价是 $O(n \log n)$。

$$500{,}000 \times \log_2(500{,}000) \approx 500{,}000 \times 19 = 9.5 \times 10^6 \text{ 次操作}$$

按本节实测（74.7 ms / 10 万条）推算，50 万条大约 400～500 ms。

范围查询是 $O(\log n + k)$ ✓

(c) 更好的方案：直接用数据库的索引。

关键洞察：如果数据本来就存在数据库里，那"建立索引"这件事应该交给数据库做，而不是拉到内存里自己建树。

CREATE INDEX idx_order_no ON orders(order_no);
SELECT * FROM orders WHERE order_no BETWEEN 100000 AND 200000;

数据库的索引是 B+ 树（第六节讲过），它：

专为磁盘设计 —— 节点扇出大，树高低
支持范围查询（B+ 树的叶子节点是链表，范围扫描非常高效）
自动维护平衡 —— 插入删除都不用你操心
持久化 —— 重启不用重建

这道题的教学意义：不要重复造轮子，尤其是在数据库已经替你造好的时候。

在内存里建 50 万条记录的索引，代价是几百毫秒 + 几十 MB 内存；而数据库索引是现成的、持久的、经过极致优化的。

什么时候才需要在内存里建索引？

数据不在数据库里（比如来自多个数据源、或者实时计算的结果）

需要极低的查询延迟（内存 vs 数据库往返）

查询模式复杂到数据库索引无法覆盖

10.4.5

(a) 删除后，可能破坏从被删节点的父节点到根这一整条路径上所有节点的平衡。

具体来说：删除会让某个子树的高度减 1，这个变化会沿着父节点链一路上传，导致路径上每个节点的平衡因子都可能超标。

(b) 因为"高度减少"比"高度增加"更难处理：

	插入	删除
高度变化	某个子树高度 +1	某个子树高度 -1
影响范围	可能只影响最近的一个失衡节点	可能一路上传到根
旋转次数	最多 2 次（LR/RL）	可能 O(log n) 次
旋转后	子树高度恢复，可以停止	子树高度可能继续降低，要接着往上传

关键区别在于"旋转之后能不能停"：

插入时：一次旋转把"高出来"的那 1 层压回去了 —— 子树高度恢复到插入前，所以上面的节点不受影响，可以停。

删除时：一次旋转只能把"失衡"修正，但子树的高度可能比原来还少 1 —— 这会继续影响父节点，必须一路往上传。

所以删除的旋转次数是 $O(\log n)$，而插入最多 2 次。

(c)

插入：最多 2 次旋转（LL/RR 各 1 次；LR/RL 各 2 次）
删除：最多 $O(\log n)$ 次旋转（最坏情况下从叶子一路传到根）

这也解释了为什么我们的 AVL 实现只做了插入 —— 删除的边界情况太多（要处理"删的是根""两个孩子""旋转后还要继续检查"等），是一个容易写错的地方。

而红黑树在这方面有优势：它的插入和删除都只需要常数次旋转（插入最多 2 次、删除最多 3 次），其余的调整靠"变色"完成。

这就是红黑树在"频繁增删"场景下胜出的原因 —— 不用一路旋转到根。

十、常见错误

误区	纠正
认为"旋转会改变中序顺序"	完全不会。旋转只改"谁是谁的孩子"，不改"谁在谁左边"。
认为"一次旋转就能让树变矮"	单次旋转只是局部调整，AVL 靠的是"每次插入后都检查"累积起来的效果。
认为平衡"没有代价"	随机输入下 AVL 比普通 BST 慢 2.91 倍（实测）。代价只在数据不退化时才看得出来。
认为"红的黑树比 AVL 差"	它的增删更快（旋转更少），综合表现更好。这就是工程标准选它的原因。
自己写二叉搜索树用于生产	删除是自平衡树最难的部分，容易写错。用 `SortedDictionary` / `SortedSet`。
不管需不需要有序都用 `SortedDictionary`	不需要有序就用 `Dictionary` —— 哈希表 $O(1)$ 更快、内存更省。
认为数据库索引用二叉树	用 B+ 树。因为磁盘 I/O 按块进行，B+ 树的多路结构能把树高压到 3～4 层。

十一、本节总结

旋转能在不改变中序遍历顺序的前提下改变树形 —— 它只调整"谁是谁的孩子"。
AVL 树要求每个节点的左右子树高度差 ≤ 1，靠平衡因子检测失衡，靠旋转恢复平衡。
四种失衡情况：LL（右旋）、RR（左旋）、LR（先左后右）、RL（先右后左）。"直的转一次，弯的转两次"。
AVL 实测防退化：递增插入 10 万个元素，高度从 99,999 降到 17（理论最优 16.6）。
平衡的代价只在数据不退化时才看得出来：随机输入下 AVL 慢 2.91 倍；但递增输入下 AVL 快 196 倍。
红黑树是工程标准：平衡条件更宽松（$2\log n$ vs $1.44\log n$），但增删时旋转更少，适合"读写均衡"。
数据库用 B+ 树而非二叉树：因为磁盘 I/O 按块进行，多路结构能把树高压到 3～4 层（从 20 次 I/O 降到 4 次）。
.NET 里用 SortedDictionary / SortedSet（内部是红黑树）。不需要有序就用 Dictionary。

本章小结：第 10 章讲了"让树有用"的关键一步。

10.1 BST 的性质：左子树所有值 < 自己 < 右子树所有值。它带来"中序有序"，以及范围查询、找最值这些哈希表做不到的能力。
10.2 查找、插入、删除。删除分三种情况，最复杂的是"有两个孩子"（用中序后继替代）。
10.3 退化：BST 的形状完全由插入顺序决定，而有序输入是常态 —— 所以普通 BST 在生产环境几乎注定退化（实测慢 576 倍）。
10.4 平衡：靠旋转恢复形状，AVL 靠严格平衡、红黑树靠近似平衡。工程上用红黑树（SortedDictionary）。

贯穿本章的一条线索："最坏情况"比"平均情况"重要。

这和 8.2 节（快排退化）、8.5 节（内省排序的保险丝）是同一个主题 —— 工程上追求的从来不是"平均快"，而是"最坏可控"。

下一章衔接：树讲完了（普通二叉树、BST、平衡树）。但还有一种结构，它在"每次取出最值"这件事上比 BST 更专精 —— 堆。

第 8.3 节我们用堆来排序，但那只是它的一个用途。堆真正的舞台是优先队列：任务调度、Top-K、合并有序序列、Dijkstra 算法……它是"总是要拿最大/最小"这类问题的标准答案。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "10.4",
  "title": "平衡树思想：AVL 与红黑树概览",
  "covered": [
    "旋转的直觉（改变形状但不改变中序顺序）与代码实现",
    "AVL 的平衡因子与高度维护",
    "四种失衡情况（LL/RR/LR/RL）与对应旋转",
    "LR 情况的两次旋转实测验证",
    "AVL 防退化的实测（高度 99999 → 17）",
    "「平衡的代价」在两个场景下的对比（递增快 196 倍 vs 随机慢 2.91 倍）",
    "AVL vs 红黑树的完整对比与工程选择理由",
    "B+ 树为何成为数据库索引标准（磁盘 I/O 块粒度）",
    "手写 AVL vs SortedDictionary 的实测与「为何仍应用内置」的四点理由",
    "插入最多 2 次旋转 vs 删除 O(log n) 次旋转的分析"
  ],
  "unresolved": [
    "红黑树的完整实现超出本书范围",
    "B+ 树与数据库索引超出本书范围",
    "堆与优先队列留到第 11 章"
  ],
  "canonical_terms": {
    "旋转（Rotation）": "不改变中序顺序、只调整父子关系的局部操作",
    "平衡因子（Balance Factor）": "左子树高度减右子树高度，AVL 要求绝对值不超过 1",
    "AVL 树": "严格平衡的二叉搜索树，高度上界 1.44 log2(n)",
    "红黑树（Red-Black Tree）": "近似平衡的二叉搜索树，增删时旋转更少"
  },
  "symbols_units": {
    "BF": "平衡因子"
  },
  "assumptions": [
    "读者已掌握 10.1-10.3 的 BST 全部内容",
    "读者理解 2.2 节的栈溢出（实验中递归版插入确实溢出了）"
  ],
  "word_count_actual": 3420,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch10/Sec104/",
    "旋转演示、LR 验证、两个场景的性能对比、SortedDictionary 对比均为实测",
    "练习 10.4.1/10.4.2 的旋转推演已手工验算",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "初版用递归版 BstInsert，插入 10 万个递增元素时栈溢出（递归深度 10 万层 > 2.2 节实测的 1.6 万层上限）；已改为迭代版，并把「递归 BST 在退化时会栈溢出」写成注释",
    "初版把「AVL 慢 0.0 倍」写反了方向：实测 AVL（19.3ms）比普通 BST（3790.2ms）快 196 倍，因为普通 BST 在有序输入下每次插入都是 O(n)。已拆成「递增输入」和「随机输入」两个场景，才能分别看出「退化的代价」和「平衡的代价」",
    "初版结论写「内置实现比我们手写的更快」，与实测相反（手写 AVL 19.3ms vs SortedDictionary 74.7ms）；已修正为「手写版在特定场景更快，但缺少删除、泛型和健壮性，工程上仍应用内置」"
  ],
  "next": "11.1 堆的定义与数组表示"
}

10.4　平衡树思想：AVL 与红黑树概览