LECTURE 1:AVL树&红黑树

AVL 树与红黑树 · 概念 / 旋转 / 插入修复 / 对比速查

阅读说明：流程图需要阅读器支持 Mermaid。本文已加入字体与行距样式；若阅读器禁用内嵌 CSS，仍可正常显示标题、加粗、表格和代码块，字体则由阅读器主题决定。

约定：不考虑重复键；树形图中未画出的空孩子均视为 NULL 或 NIL。AVL 的四种旋转案例和红黑树的五种修复案例均针对插入操作。

先记住这三句话

树的类型	核心记忆
BST	左子树全小，右子树全大。
AVL 树	每个节点的左右高度差不超过 1。
红黑树	根黑、NIL 黑、红不连红、各路黑高相同。

模块零：万物之基——二叉查找树（BST）

不管是 AVL 树还是红黑树，它们的原型全都是二叉查找树。

全局铁律：对于树中任何一个节点，其值必须严格大于左子树中的所有元素，并严格小于右子树中的所有元素。
高频易错点：该规则约束的是整个子树，而不只是直接相连的孩子。若根节点为 10，其右子树中就不能出现 8。

模块一：AVL 树——严格的高度平衡

1. 核心概念与失衡判定

概念	定义或判定方式
高度 `h`	空节点高度为 `−1`，叶子节点高度为 `0`
高度递推式	`h(v) = max(h(v.left), h(v.right)) + 1`
平衡因子 `BF`	`BF(v) = h(v.left) − h(v.right)`
合法状态	每个节点的 `BF ∈ {−1, 0, 1}`
插入后的失衡	`BF = 2` 或 `BF = −2`

术语约定：

Finder（失衡节点）：从新节点向根回溯时，遇到的第一个失衡节点。
Maker（新节点）：本次插入、引发失衡的节点。

2. 四种旋转方式速查

类型	插入位置（相对 Finder）	修复操作
LL	左孩子的左子树	右旋 Finder
RR	右孩子的右子树	左旋 Finder
LR	左孩子的右子树	先左旋左孩子，再右旋 Finder
RL	右孩子的左子树	先右旋右孩子，再左旋 Finder

记忆重点：单旋向反方向转；双旋先处理孩子，再处理失衡节点。

插入与删除别混用：插入在首个失衡节点处修复后，该子树高度恢复到插入前的高度。

删除可能需要继续向根修复，不能直接套用此结束条件。

3. LL 型：左左单旋

场景：在 Finder 左孩子的左子树中插入新节点，导致失衡。
例题：向空树依次插入 30, 20, 10。
操作：右旋 30，将 20 提升为该子树的根，30 成为其右孩子。

插入后：                      右旋 30 后：
 
      30  ← Finder，BF = 2           20
     /                             /  \
    20                            10  30
   /
  10  ← Maker

4. RR 型：右右单旋

场景：在 Finder 右孩子的右子树中插入新节点，导致失衡。
例题：向空树依次插入 10, 20, 30。
操作：左旋 10，将 20 提升为该子树的根，10 成为其左孩子。

插入后：                      左旋 10 后：
 
  10  ← Finder，BF = −2             20
    \                             /  \
     20                          10  30
       \
        30  ← Maker

5. LR 型：左右双旋

场景：在 Finder 左孩子的右子树中插入新节点，形成折角。
例题：向空树依次插入 30, 10, 20。

操作步骤：

局部左旋，先拉直：左旋 10，将 20 提升为 30 的左孩子，转化为 LL 型。
右旋 Finder，再调平：右旋 30，将 20 提升为该子树的根。

插入后：          左旋 10 后：       右旋 30 后：
 
      30                30                20
     /                 /                /  \
    10                20               10  30
      \              /
       20           10

6. RL 型：右左双旋

场景：在 Finder 右孩子的左子树中插入新节点，形成折角。
例题：向空树依次插入 10, 30, 20。

操作步骤：

局部右旋，先拉直：右旋 30，将 20 提升为 10 的右孩子，转化为 RR 型。
左旋 Finder，再调平：左旋 10，将 20 提升为该子树的根。

插入后：          右旋 30 后：       左旋 10 后：
 
  10                10                    20
    \                 \                  /  \
     30                20               10  30
    /                    \
   20                     30

模块二：红黑树——弹性的工程艺术

红黑树通过颜色约束保持对数级树高。它不像 AVL 树那样要求每个节点的左右子树高度差至多为 1。

1. 五大基本规则

每个节点非黑即红。
根节点必须是黑色。
所有外部叶子，即 NIL 空哨兵，都是黑色。
不能出现连续的红节点：红色节点的孩子必须是黑色。
黑高一致：从任意节点出发，到其所有后代 NIL 的路径上，黑色节点数量必须相同。

比喻记忆：黑节点像承重墙，红节点像隔断。由于红节点不能相连，最长路径至多是红黑交替，其长度不超过最短路径的两倍。比较路径时须采用一致的端点和计数方式。

2. 核心公式与概念

2.1 节点与黑高

内部节点：存储真实数据的节点，包含根节点，不包含 NIL。
黑高 bh(v)：从节点 v 出发到任意后代 NIL 的路径上，**不计 v、计入末端 NIL**的黑色节点数。规定 bh(NIL) = 0。
对数底数：本节的对数均以 2 为底。

2.2 高度上界

设内部节点总数为 N，根节点黑高为 bh。

推导步骤	关系式
给定黑高时，内部节点数量的下界	N ≥ 2ᵇʰ − 1
由节点数量约束黑高	bh ≤ log₂(N + 1)
红色节点不能连续，约束路径长度	h ≤ 2bh
合并得到高度上界	h ≤ 2log₂(N + 1)

给定黑高时，全黑的完美二叉树达到上述节点数量下界。

要记住的结论：树高 h ≤ 2log₂(N + 1)，最坏查找时间为 O(log N)。

上述推导可将 h 按根到最远 NIL 的边数计。若采用 AVL 部分“根到最远内部叶子的边数”的高度约定，非空树的高度少 1，同样满足最终上界。

3. 插入决策流程

初始动作：按 BST 规则插入新节点，并将其默认染成红色，以尽量保持黑高不变。

先看什么	怎么处理
当前节点是根	染黑，结束
父节点黑	无需调整，结束
父红、叔红	父叔黑、祖父红，向上检查
父红、叔黑，LL / RR	单旋 + 变色，结束
父红、叔黑，LR / RL	双旋 + 变色，结束

修复过程中使用以下记号：

记号	含义
`x`	当前修复节点，初始为新插入的节点
`p`	`x` 的父节点
`g`	`x` 的祖父节点
`u`	`x` 的叔节点，即 `p` 的兄弟；缺失时为黑色 `NIL`

发生向上修复时，x 会改为原来的祖父节点，不一定仍是最初插入的节点。LL、LR、RL、RR 均按当前的 g → p → x 关系判断。

4. 场景 1：向空树插入新节点

规则：新节点默认是红色；若它成为根节点，则必须染黑。
例题：向空树插入 10。

步骤：

创建 10(红)。
发现它是根节点，将其染成黑色。

调整结果：
 
       10(黑)
       /    \
     NIL    NIL

5. 场景 2：父节点是黑色

规则：没有产生连续红节点，也没有改变黑高，无需调整。
例题：在只有根节点 10(黑) 的树中插入 5。

步骤：

因为 5 < 10，将 5(红) 作为 10 的左孩子。
父节点 10 为黑色，直接结束。

调整结果：
 
       10(黑)
       /    \
     5(红)  NIL

6. 场景 3：父节点与叔节点都是红色

规则：父节点与叔节点染黑，祖父节点染红，然后以祖父节点为当前节点继续向上检查。
例题：已有根节点 30(黑)、左孩子 10(红)、右孩子 40(红)，插入 20。

插入后：
 
           30(黑，祖父)
          /           \
     10(红，父)     40(红，叔)
          \
         20(红，新)

步骤：

10 与 20 产生连红，叔节点 40 也是红色。
将父节点 10 和叔节点 40 染黑，将祖父节点 30 染红。
令当前节点为 30。因为它是根节点，重新将其染黑，结束。

调整结果：
 
           30(黑)
          /      \
       10(黑)    40(黑)
          \
         20(红)

重点：父叔都红 → 变色 → 向上检查。

局部顶端的祖父节点变红后，可能与更上层的红色父节点产生新的冲突。

7. 场景 4：叔节点为黑色，结构为 LL 或 RR

规则：对祖父节点进行单旋；原父节点染黑，原祖父节点染红。
例题：已有根节点 30(黑)、左孩子 20(红)、右孩子 NIL(黑)，插入 10。

插入后：
 
           30(黑，祖父)
          /           \
     20(红，父)     NIL(黑，叔)
      /
   10(红，新)

步骤：

20 与 10 产生连红，叔节点为黑色 NIL。
结构为 LL 型：右旋祖父节点 30，将 20 提升为该子树的根。
将 20 染黑，将 30 染红。

调整结果：
 
          20(黑)
         /      \
      10(红)    30(红)

RR 型为镜像操作：左旋祖父节点，原父节点染黑，原祖父节点染红。

终结特性：调整后的子树根为黑色，不会与更上层产生连红冲突；子树黑高保持不变，修复就地结束。

8. 场景 5：叔节点为黑色，结构为 LR 或 RL

规则：先旋转父节点，将折角拉直；再旋转祖父节点。最终将该子树的新根染黑，原祖父节点染红。
例题：已有根节点 30(黑)、左孩子 10(红)、右孩子 NIL(黑)，插入 20。

插入后：
 
           30(黑，祖父)
          /           \
     10(红，父)     NIL(黑，叔)
          \
         20(红，新)

步骤：

判定：10 与 20 连红，叔节点为黑色 NIL，结构为 LR 型。

拉直：左旋父节点 10，将 20 提升为 30 的左孩子。

        30(黑)
       /      \
    20(红)    NIL(黑)
    /
 10(红)

调平：右旋祖父节点 30，将 20 提升为该子树的根。
变色：将新子树根 20 染黑，将原祖父节点 30 染红，10 保持红色。
```
        20(黑)
       /      \
    10(红)    30(红)
```

RL 型为镜像操作：先右旋父节点，再左旋祖父节点，最后进行对应变色。

终结特性：调整后的子树根为黑色，黑高保持不变，修复就地结束。

在本例中，变黑的 20 恰好是最初插入的节点；若此前经历了场景 3 的向上修复，就应按当前修复节点判断，不能一概说“最初插入的节点变黑”。

模块三：两大平衡树横向速查表

对比维度	AVL 树	红黑树
平衡严格度	每个节点的左右子树高度差至多为 `1`	通过颜色与黑高约束平衡；最长根到 NIL 路径不超过最短路径的两倍
查找、插入、删除的最坏时间复杂度	`O(log N)`	`O(log N)`
单次插入最坏旋转次数	至多 `2` 次：单旋 `1` 次，双旋 `2` 次	至多 `2` 次：单旋 `1` 次，双旋 `2` 次
单次删除最坏旋转次数	`O(log N)` 次，可能一路修复到根	经典红黑树算法至多 `3` 次
平衡元数据	通常存高度或平衡因子；三个合法平衡因子状态理论上可用 `2 bit` 编码	颜色理论上只需 `1 bit`
常见适用场景	查询较多、重视较小树高的场景	增删较多的通用有序容器；例如 Linux 内核中的相关结构及 C++ `std::map` 的常见实现

先记住这三句话

模块零：万物之基——二叉查找树（BST）

模块一：AVL 树——严格的高度平衡

1. 核心概念与失衡判定

2. 四种旋转方式速查

3. LL 型：左左单旋

4. RR 型：右右单旋

5. LR 型：左右双旋

6. RL 型：右左双旋

模块二：红黑树——弹性的工程艺术

1. 五大基本规则

2. 核心公式与概念

2.1 节点与黑高

2.2 高度上界

3. 插入决策流程

4. 场景 1：向空树插入新节点

5. 场景 2：父节点是黑色

6. 场景 3：父节点与叔节点都是红色

7. 场景 4：叔节点为黑色，结构为 LL 或 RR

8. 场景 5：叔节点为黑色，结构为 LR 或 RL

模块三：两大平衡树横向速查表

评论 (0)