课程 · #10 / 11

平衡树

旋转让高度始终 ≈ log n，无论插入顺序如何

AVL tree · self-balancing rotations

size0

avl height0

naïve bst h.0

init

value

动手试试：按 insert 1..15 强行制造一个退化序列。朴素 BST 的高度一下蹿到 15；AVL 的高度却稳稳停在 4——因为每一次失衡都会触发一次旋转，并在画布上闪现出来。

为什么它重要

普通 BST 可能退化到 O(n)。平衡树通过在插入和删除后自动重新平衡，保证 O(log n)。AVL 树和红黑树是大多数语言标准库背后的主力。

核心思想

还记得 BST 在插入已排序数据时会变成一条链表吗？平衡树通过在操作后重新调整结构来防止这一点。

AVL 树：每次插入/删除后，检查是否有某个节点的左右子树高度相差超过 1。如果有，就旋转来修复它。

旋转是那个神奇的招式：

右旋：当左子树太高时
左旋：当右子树太高时
双旋：用于"之字形"情形

结果是：高度始终为 O(log n)，于是所有操作都被保证维持在 O(log n)。

红黑树用的是另一种诀窍：给节点染上红色或黑色，并用一套规则限制树最多能失衡到什么程度。它没有 AVL 那么严格地平衡，但平均下来旋转次数更少。

要点回顾

无论插入顺序如何，都保证 O(log n) 的操作
旋转是保持 BST 性质的 O(1) 操作
AVL：更严格的平衡（高度差 ≤ 1）
红黑：更宽松的平衡，旋转更少

不变式

这些树继承了 BST 不变式，并在其上加了一条平衡规则。正是这条平衡规则保证了 O(log n) 的高度。

AVL 不变式: 对每个节点，|height(left) − height(right)| ≤ 1。每次插入和删除后都通过旋转严格强制执行。; 推论：高度 h < 1.44 · log₂(n + 2)——离理论最小值不到 44%。
红黑不变式——四条必须同时成立: 1. 每个节点要么是红色，要么是黑色。; 2. 根是黑色的。（有时也表述为：叶子——那些 NULL 哨兵——也是黑色的。）; 3. 红色节点只能有黑色孩子。（任何一条从根到叶的路径上都不会连续出现两个红色。）; 4. 每条从根到 NULL 的路径都经过相同数量的黑色节点。这就是黑高；它是约束树高的那条结构性不变式。; 推论：高度 h ≤ 2 · log₂(n + 1)。比 AVL 宽松，但更易维护。

再深入一些

AVL 与红黑 —— 该选哪个

| 性质 | AVL | 红黑 | |---|---|---| | 最坏情况高度 | ≤ 1.44 log₂ n | ≤ 2 log₂ n | | 每次插入的旋转 | 至多 2 次 | 至多 2 次 | | 每次删除的旋转 | 至多 O(log n) | 至多 3 次 | | 查找速度 | 略快（更平衡） | 略慢 | | 插入/删除速度 | 较慢 | 较快 | | 每个节点的内存 | 1–2 位（平衡因子） | 1 位（颜色） | | 典型用途 | 数据库、读多写少 | 语言标准库 std::map、TreeMap、Linux 内核 rbtree.h |

经验法则： 如果你读远多于写，用 AVL。如果你的工作负载是混合的或写多，用红黑。C++ 的 std::map、Java 的 TreeMap 以及 Linux 内核的进程调度器都因此用红黑树。

B 树 —— 面向磁盘页的推广

B 树把 BST 朝一个方向推广：每个节点持有许多个键（比如 100 到 1000 个），而不只是一个。一个有 k 个键的节点有 k + 1 个孩子，孩子们的键区间与父节点的键交错排列（key₀ 左边 → child₀，key₀ 与 key₁ 之间 → child₁，……）。

为什么每个节点要塞这么多键？磁盘寻道。 在机械磁盘上，读 1 字节和读 16 KB 花的时间基本一样——代价在于磁头的移动，而不在于传输的字节数。数据库引擎把每个 B 树节点填到恰好一个磁盘页的大小（通常 4 KB 或 16 KB）。一次磁盘读取就一口气取来约 256–1024 个键，于是在数十亿行的数据库里导航也只需 3–4 次页读取。同样的逻辑适用于 SSD（其寻道代价由页对齐 I/O 主导）以及文件系统的 inode。

每个关系数据库索引、每个现代文件系统（ext4、NTFS、APFS、XFS），以及大多数键值存储（RocksDB、LevelDB）用的都是 B 树或其近亲 B+ 树（其中叶节点构成一条链表，以便快速范围扫描）。B 树正是 SELECT * WHERE id BETWEEN 1000 AND 2000 在十亿行表上能在亚毫秒内完成的原因。

现实世界的代价数字

对一棵有 n = 1,000,000 个键的平衡树：

查找：约 20 次比较（log₂ 1M ≈ 20）
内存：约 24 MB（假设每个节点 24 B——3 个指针 + 4 字节键）

与一个按键排序的数组对比：

查找：约 20 次比较（二分查找，同样是 log₂ n）
内存：约 4 MB（只有键，没有指针）
插入：O(n)——数组搬移

所以，如果你的数据集是只读的、又能装进内存，那么一个有序数组在速度（缓存局部性）和内存上都胜过平衡树。平衡树付出这份开销，是为了换取 O(log n) 的插入。

数学细节

AVL 平衡因子: BF(n) = height(n.left) - height(n.right); Must be in 1
时间复杂度（有保证）: Search: O(log n); Insert: O(log n); Delete: O(log n)
高度界: AVL: h < 1.44 log_2(n+2); Red-Black: h leq 2 log_2(n+1)

实现

旋转的概念

// Right rotation when left subtree too tall
//       y                x
//      / \              / \
//     x   C   --->     A   y
//    / \                  / \
//   A   B                B   C

fn rotate_right(y: Node) -> Node {
    let x = y.left.take();
    y.left = x.right;
    x.right = Some(y);
    x
}

何时使用

需要有保证的 O(log n) 性能
数据以已排序/近乎已排序的顺序到来
实现映射、集合、优先队列
数据库索引

练习

每一个自平衡树实现的配套检查：

二叉树是否高度平衡？ —— 简单 · 带哨兵提前退出的 O(n) 后序遍历；正是你在每次 AVL / 红黑旋转之后要断言的东西

→ 浏览全部练习题

⚖️ 平衡树