普通 BST 的问题不是查找规则，而是树形没有约束。平衡查找树保留"左小右大"，并在插入或删除破坏高度条件时做局部调整，以换取最坏 $O(\log n)$ 的查找路径。

学习目标

• 计算 AVL 结点的平衡因子，判断结点是否失衡；
• 根据 LL、RR、LR、RL 四种形态选择旋转；
• 说明 AVL 插入和删除修复的差异；
• 复述红黑树的五条性质，并由黑高推导高度上界；
• 比较 AVL 与红黑树在查询、更新和实现复杂度上的取舍。

旋转为何可行

旋转只改变少量父子链接，不改变关键字的中序次序。以右旋为例，设失衡结点为 y，它的左孩子为 x，x 的右子树为 T2：

旋转前后的中序序列都是 A, x, T2, y, C。因此，只要原子树满足 BST 次序，旋转后仍满足。

THM定理 · 旋转保持中序有序

右旋把 x 提升为子树根，y 成为 x 的右孩子，T2（介于 x 与 y 之间）移作 y 的左子树。整棵子树的中序遍历恒为 A, x, T2, y, C，与旋转前完全一致。左旋对称。因此旋转是"不改变关键字次序"的纯结构调整，可安全用于修复失衡。

IDEA直觉 · 为什么旋转能降低高度

右旋把较高一侧的子树根 x 提上来，把 y 压下去，相当于"把重心向更低的一侧挪"。这样左子树的高度减少 1，右子树高度增加 1，从而把两边高度差拉回允许范围。

AVL 树

AVL 树是任意结点左右子树高度差绝对值不超过 1 的 BST。定义结点 $v$ 的平衡因子为：

$$BF(v)=height(v.left)-height(v.right).$$

合法 AVL 结点的平衡因子只能是 $-1$、$0$ 或 $1$。插入或删除后若某结点出现 $|BF|=2$，就要在该结点附近旋转。

DEF定义 · AVL 树与平衡因子

一棵 AVL 树是一棵 BST，且对每个结点 $v$，满足 $|BF(v)|\le 1$，即 $height(v.left)-height(v.right)\in \{-1,0,1\}$。$|BF|=2$ 表示失衡，需要在 $v$ 附近旋转恢复。

四种失衡形态

从最低失衡结点向新增关键字方向观察，可以分为四类：

形态	路径	调整
LL	左孩子的左子树增高	对失衡结点右旋
RR	右孩子的右子树增高	对失衡结点左旋
LR	左孩子的右子树增高	先对左孩子左旋，再对失衡结点右旋
RL	右孩子的左子树增高	先对右孩子右旋，再对失衡结点左旋

"LL"和"RR"描述的是从失衡结点向下的两步方向，不是旋转方向。LL 用右旋，RR 用左旋。

LL：一次右旋

依次插入 30, 20, 10。结点 30 的左子树比右子树高 2，新值位于左孩子 20 的左侧，因此是 LL：

RR：一次左旋

依次插入 10, 20, 30，最低失衡结点是 10，新值位于右孩子的右侧。对 10 左旋后，20 成为新根。

LR 与 RL：先把折线拉直

依次插入 30, 10, 20 时，路径是左后右。先对 10 左旋，把它变成 LL，再对 30 右旋：

RL 完全对称：先右旋右孩子，再左旋失衡结点。

EX示例 · 四种形态各用一组三键演示

插入顺序	形态	调整	结果
3, 2, 1	LL	对 3 右旋	根 2，1,2,3 平衡
1, 2, 3	RR	对 1 左旋	根 2，1,2,3 平衡
3, 1, 2	LR	先左旋 1，再右旋 3	根 2，1,2,3 平衡
1, 3, 2	RL	先右旋 3，再左旋 1	根 2，1,2,3 平衡

三键序列每一种都触发一种旋转，旋转后树高都从 3 降到 2。这组"三键万能例"适合快速判断一种输入属于哪种失衡形态。

交互式演示

用四个"三键"预设亲手跑一遍 LL / RR / LR / RL：插入后每个结点旁会标注平衡因子，失衡结点被高亮，播放时自动执行对应旋转恢复平衡。也可以观察 30, 20, 10, 25, 28, 27 这组，看连续的插入如何依次触发不同形态的旋转。

对应到正文

把演示里的四种预设对应到上方表格：3,2,1→LL、1,2,3→RR、3,1,2→LR、1,3,2→RL。注意"LL 用右旋、RR 用左旋"，名字与旋转方向相反。

AVL 插入流程

1. 按普通 BST 规则插入新结点；
2. 从新结点向根回溯，更新沿途高度；
3. 找到最低的失衡结点；
4. 根据失衡结点、较高孩子和新增方向选择一次或两次旋转；
5. 更新旋转涉及结点的高度。

插入修复最低失衡结点后，该子树恢复到插入前的高度，因此更高祖先通常不再失衡。

PROP性质 · 插入只需一次旋转

一次插入只让某条根到叶路径上的高度可能变化。在最低失衡结点处旋转后，该子树的高度恢复到插入前，因此所有更高祖先的平衡因子不再需要调整。所以 AVL 插入最多触发一次旋转。

统一的旋转判断

实现时不必直接比较新关键字。可根据两个平衡因子判断：

BF(node) > 1  且 BF(node.left) >= 0  → LL
BF(node) > 1  且 BF(node.left) < 0   → LR
BF(node) < -1 且 BF(node.right) <= 0 → RR
BF(node) < -1 且 BF(node.right) > 0  → RL

这套规则也更容易扩展到删除后的修复。

AVL 删除

删除先按 BST 的三种情况完成，再从实际发生结构缩短的位置向根回溯。与插入不同，删除修复一次后子树高度仍可能继续降低，因此祖先可能接连失衡，最多要沿整条路径调整。

删除时还会出现"较高孩子的平衡因子为 0"的情况。例如某结点左侧过高，而左孩子 BF=0，仍应执行 LL 型右旋；旋转后高度变化要按实际子树重新计算，不能套用插入时"修一次即结束"的结论。

EX示例 · 为什么删除要"逐层回溯"

考虑一棵删除某个叶结点后，子树整体高度降低的 AVL。修复最低失衡结点时，该子树可能比原来的整体矮了 1 层，于是它的父结点也可能失衡。这样修复要一路向上传播，直到某个子树高度没变化或到达根。

反观插入：新结点让子树长高，但最低失衡结点旋转后子树高度恢复原样，所以不会向上传播。这就是"插入一次旋转、删除可能多次旋转"的根源。

AVL 的高度与复杂度

设高度为 $h$ 的 AVL 树最少结点数为 $N_h$。为了让结点最少，两棵子树高度应分别为 $h-1$ 和 $h-2$：

$$N_h=N_{h-1}+N_{h-2}+1.$$

这个递推式与斐波那契数列同阶，所以 AVL 高度为 $O(\log n)$。查找、插入、删除的最坏时间都为 $O(\log n)$；旋转本身只改常数条链接，单次为 $O(1)$。

O(·)复杂度 · AVL 树

• 查找、插入、删除：$O(\log n)$（最坏）；
• 旋转：$O(1)$ 每次；
• 空间：$O(n)$，每个结点额外存高度（或平衡因子）。

AVL 树因此提供最坏情况的 $O(\log n)$ 查找路径，而不是像普通 BST 那样只有平均保证。

红黑树

AVL 严格限制左右高度差。红黑树使用较宽松的颜色规则限制最长路径，使更新时通常需要更少旋转。

把所有空孩子视为黑色 NIL 叶结点。一棵红黑树满足：

1. 每个结点非红即黑；
2. 根结点是黑色；
3. 所有 NIL 叶结点是黑色；
4. 红结点的两个孩子都是黑色，不能出现连续红结点；
5. 从任一结点到其所有后代 NIL 叶结点的路径，都包含相同数量的黑结点。

从某结点到后代 NIL 路径上的黑结点数称为黑高。性质 4 保证最长路径至多在每两个黑结点之间插入一个红结点，因此最长路径不会超过最短路径的两倍。

DEF定义 · 黑高与红黑树

一个结点的黑高是从该结点到其所有后代 NIL 叶的路径上经过的黑结点数（不含该结点本身）。红黑树通过"所有路径黑高相同"（性质 5）限制树高，又通过"无连续红结点"（性质 4）限制最长与最短路径之比。

含 $n$ 个内部结点的红黑树高度满足：

$$h\le 2{\log }_2(n+1).$$

所以查找、插入、删除的最坏时间都是 $O(\log n)$。

THM定理 · 红黑树高度上界

性质 4 使最长路径上最多每两个黑结点夹一个红结点，故最长路径 ≤ $2\times$ 最短路径。又由性质 5 所有路径黑高相同为 $bh$，最短路径至少 $bh$ 个黑结点。一棵黑高为 $bh$ 的红黑树至少含 $2^{bh}-1$ 个内部结点，从而 $bh\le {\log }_2(n+1)$，所以 $h\le 2bh\le 2{\log }_2(n+1)$。

红黑树插入的修复思路

新结点按 BST 规则插入并染红。染红不会改变任一路径的黑高；唯一可能破坏的是"红结点不能有红孩子"。若父结点也是红色，观察叔叔结点：

• 叔叔为红色：把父和叔染黑、祖父染红，再从祖父继续向上检查；
• 叔叔为黑色，路径成折线：先旋转父结点，把折线变成直线；
• 叔叔为黑色，路径成直线：旋转祖父，并交换父与祖父的颜色。

最后把根染黑。修复可能多次变色，但插入最多做常数次结构旋转。

IDEA直觉 · 为什么新结点染红

插入新结点若染黑，会让经过它那条路径的黑高比别的路径多 1，立刻破坏性质 5，而且这个破坏很难局部修复。染红则只可能破坏性质 4（父也是红），而"连续红"是可以通过变色和旋转在局部消除的。因此染红把问题变成一个更可控的局部约束。

红黑树删除的修复思路

删除红结点不会改变黑高；删除有红孩子的黑结点时，可让红孩子顶替并染黑。困难发生在删除黑色叶位置：某些路径会少一个黑结点，可把这个缺额理解为"额外一重黑色"。

修复时根据兄弟颜色、兄弟孩子颜色决定变色和旋转，把黑色缺额向上移动或在局部消除。完整代码分支较多，但每一步都服务于两件事：恢复相同黑高，避免连续红结点。

不要用 AVL 的高度差判断红黑树

红黑树不要求任意结点左右子树高度差不超过 1。它只通过颜色和黑高限制整体最长路径，因此可能比同关键字集合的 AVL 更高。

AVL 与红黑树如何选择

维度	AVL	红黑树
平衡强度	严格，高度更低	较宽松，高度最多约为最短路径两倍
查找	通常比较次数更少	最坏仍为 $O(\log n)$
插入/删除	可能更频繁更新高度和旋转	通常以变色为主，旋转较少
结点额外信息	高度或平衡因子	1 位颜色信息
常见场景	查询明显多于更新	查询与更新都频繁的有序映射/集合

EX示例 · 一个具体的选型取舍

• 读取密集（如字典、符号表，插入少、查询多）：AVL 更矮，每次查找比较更少，适合。
• 读写都频繁（如 C++ std::map、Java TreeMap）：红黑树每次插入删除旋转更少、变色居多，总体更新成本更低，适合。

两者都保留 BST 的中序有序性，支持范围查询、前驱、后继和有序遍历。它们不是散列表的直接替代：散列表擅长精确匹配，却不自然支持顺序操作。

易错点

• AVL 的平衡因子是左右高度差，不是结点数之差。
• LL 失衡做右旋，RR 失衡做左旋；名称与旋转方向相反。
• AVL 插入修复最低失衡结点后通常结束，删除却可能继续向根修复。
• 红黑树的 NIL 空叶结点参与黑高计算，不能直接忽略。
• 红黑树只保证高度为 $O(\log n)$，不保证每个结点高度差不超过 1。

WARN易错点 · 把 AVL 平衡因子算成"结点数差"

平衡因子只比较高度（根到叶的最长路径），不是子树结点个数。两棵子树结点数可以相差很多，但只要高度差不超过 1，就仍是合法 AVL。反之，结点数相近但一侧特别深，也可能失衡。

小结

AVL 用精确高度约束获得更矮的树，红黑树用颜色和黑高换取更便宜的更新。两者都依赖旋转保持中序次序，只是触发条件和修复目标不同。掌握它们时，与其背旋转图，不如先找最低失衡位置，再检查路径形状或颜色冲突。

下一篇将把"一个结点一个关键字"的二叉搜索推广到一次装入多个关键字的B 树与 B+ 树。

练习

1. 依次向空 AVL 树插入 30, 20, 10, 25, 28, 27，标出每次失衡类型并画出调整结果。
2. 构造一个删除后需要向上连续两次修复的 AVL 例子，说明为什么插入时通常不会发生同样情况。
3. 证明右旋不改变子树的中序序列。
4. 一棵红黑树某条根到 NIL 路径的黑高为 4，它的内部结点路径最长可能有多少层？
5. 为什么新插入的红黑树结点通常先染红而不是染黑？分别说明对性质 4、5 的影响。