Appearance
408
数据结构
平衡二叉树（AVL 树）
定位信息
| 项目 | 内容 |
|---|---|
| 章节 | 第六章 查找 · 6.4 |
| 知识单元编号 | DS-06-04 |
| 核心概念 | 平衡因子、LL/RR/LR/RL 旋转、平衡树的插入与调整 |
| 前置知识 | 二叉搜索树（BST）、二叉树递归结构 |
| 考试权重 | ★★★★（高频重点，综合题常考旋转操作） |
知识点讲解
一、AVL 树的定义
AVL 树（Adelson-Velsky and Landis Tree）是一种自平衡的二叉搜索树，满足：
- 首先是一棵二叉搜索树（左 < 根 < 右）；
- 任意结点的平衡因子（Balance Factor）= 左子树高度 - 右子树高度，取值只能是 -1、0、1。
平衡因子： BF(node) = height(left) - height(right)。当 |BF| ≥ 2 时，该结点失衡，需要旋转调整。
高度与结点数关系： 高度为 h 的 AVL 树，最少结点数 N(h) = N(h-1) + N(h-2) + 1（类似斐波那契），其中 N(0)=0, N(1)=1, N(2)=2。
二、四种旋转操作（核心考点）
当插入或删除导致某个结点的 |BF| = 2 时，需要进行旋转调整。根据失衡结点和其孩子的 BF 符号，分为四种情况：
| 失衡类型 | 条件 | 旋转方式 | 说明 |
|---|---|---|---|
| LL 型 | BF = 2，左孩子 BF ≥ 0 | 右旋（单旋） | 在左子树的左子树插入 |
| RR 型 | BF = -2，右孩子 BF ≤ 0 | 左旋（单旋） | 在右子树的右子树插入 |
| LR 型 | BF = 2，左孩子 BF < 0 | 先左旋再右旋（双旋） | 在左子树的右子树插入 |
| RL 型 | BF = -2，右孩子 BF > 0 | 先右旋再左旋（双旋） | 在右子树的左子树插入 |
右旋操作（LL 型）示意：
失衡结点 A 结点 B
/ \ / \
B C → D A
/ \ / \
D E E C将 A 向右旋转，B 成为新的子树根。
左旋操作（RR 型）示意：
失衡结点 A 结点 B
/ \ / \
C B → A D
/ \ / \
E D C E将 A 向左旋转，B 成为新的子树根。
LR 型（先左旋再右旋）：
A A E
/ \ / \ / \
B C → E C → B A
/ \ / \ / \ / \
D E B G D F G C
/ \ / \
F G D F先对 B 做左旋，再对 A 做右旋。
RL 型（先右旋再左旋）： 与 LR 对称。
三、AVL 树插入操作伪代码（C 风格）
c
// AVL 树结点定义
typedef struct AVLNode {
KeyType key;
int height; // 以该结点为根的子树高度
struct AVLNode *lchild;
struct AVLNode *rchild;
} AVLNode, *AVLTree;
// 获取结点高度
int GetHeight(AVLNode* T) {
if (T == NULL) return 0;
return T->height;
}
// 获取平衡因子
int GetBF(AVLNode* T) {
if (T == NULL) return 0;
return GetHeight(T->lchild) - GetHeight(T->rchild);
}
// 更新结点高度
void UpdateHeight(AVLNode* T) {
T->height = max(GetHeight(T->lchild), GetHeight(T->rchild)) + 1;
}
// 右旋（LL 型调整）
AVLNode* RightRotate(AVLNode* A) {
AVLNode* B = A->lchild; // B 是 A 的左孩子
A->lchild = B->rchild; // B 的右子树变为 A 的左子树
B->rchild = A; // A 成为 B 的右孩子
UpdateHeight(A); // 先更新 A（因为 A 变成子结点了）
UpdateHeight(B); // 再更新 B
return B; // B 成为新的子树根
}
// 左旋（RR 型调整）
AVLNode* LeftRotate(AVLNode* A) {
AVLNode* B = A->rchild; // B 是 A 的右孩子
A->rchild = B->lchild; // B 的左子树变为 A 的右子树
B->lchild = A; // A 成为 B 的左孩子
UpdateHeight(A);
UpdateHeight(B);
return B;
}
// AVL 树插入（含自动平衡）
AVLTree AVL_Insert(AVLTree T, KeyType key) {
if (T == NULL) { // 找到插入位置
T = (AVLNode*)malloc(sizeof(AVLNode));
T->key = key;
T->height = 1;
T->lchild = T->rchild = NULL;
return T;
}
if (key < T->key) {
T->lchild = AVL_Insert(T->lchild, key); // 插入左子树
} else if (key > T->key) {
T->rchild = AVL_Insert(T->rchild, key); // 插入右子树
} else {
return T; // 关键字已存在
}
UpdateHeight(T); // 更新当前结点高度
int bf = GetBF(T); // 计算平衡因子
// LL 型：左子树过高，且插入在左孩子的左侧
if (bf == 2 && GetBF(T->lchild) >= 0)
return RightRotate(T);
// RR 型：右子树过高，且插入在右孩子的右侧
if (bf == -2 && GetBF(T->rchild) <= 0)
return LeftRotate(T);
// LR 型：左子树过高，且插入在左孩子的右侧
if (bf == 2 && GetBF(T->lchild) < 0) {
T->lchild = LeftRotate(T->lchild); // 先对左孩子左旋
return RightRotate(T); // 再对当前结点右旋
}
// RL 型：右子树过高，且插入在右孩子的左侧
if (bf == -2 && GetBF(T->rchild) > 0) {
T->rchild = RightRotate(T->rchild); // 先对右孩子右旋
return LeftRotate(T); // 再对当前结点左旋
}
return T; // 平衡，无需调整
}四、AVL 树 vs BST 对比表
| 对比维度 | BST | AVL 树 |
|---|---|---|
| 平衡性 | 不保证 | 严格平衡（ |
| 树高 | 最坏 O(n) | O(log n) |
| 查找 | O(n) 最坏 | O(log n) |
| 插入 | O(n) 最坏 | O(log n) |
| 删除 | O(n) 最坏 | O(log n) |
| 旋转操作 | 无 | 最多 2 次旋转（插入）/ O(log n) 次（删除） |
| 适用场景 | 数据随机分布 | 需要稳定 O(log n) 性能 |
记忆辅助
- "LL 右旋，RR 左旋，LR 先左后右，RL 先右后左" — 四种旋转的口诀。
- "失衡看 BF，|BF|=2 就要旋转" — 平衡因子绝对值等于 2 时必须调整。
- "插入最多旋两次，删除可能旋一路" — AVL 插入最多做一次单旋或一次双旋；删除可能需要从删除点旋转到根。
- "高度更新顺序：先子后父" — 旋转后先更新下层结点高度，再更新上层。
例题精解
例题 1：AVL 树插入与旋转
依次插入 {3, 2, 1}，画出每步插入后的 AVL 树，指出旋转类型。
解题四步法：
① 审题： 按序列插入构造 AVL 树，识别旋转操作。
② 分析： 每步插入后检查平衡因子，判断是否需要旋转。
③ 过程：
- 插入 3： 根结点，无需调整。
3 (BF=0)- 插入 2： 2 < 3，插入 3 的左子。3 的 BF = 1，平衡。
3 (BF=1)
/
2- 插入 1： 1 < 3 → 1 < 2，插入 2 的左子。
- 插入后，结点 3 的 BF = 2，失衡！
- 失衡结点 3，左孩子 2 的 BF = 1 ≥ 0 → LL 型
- 对结点 3 做右旋：
失衡状态： 右旋后：
3 (BF=2) 2
/ / \
2 (BF=1) 1 3
/
1④ 结论： 插入 1 后触发 LL 型失衡，对结点 3 做一次右旋，最终 AVL 树高度为 2。
例题 2：AVL 树 LR 型双旋
在 AVL 树中插入序列 {10, 5, 15, 3, 8} 后，再插入 7，说明旋转过程。
解题四步法：
① 审题： 先构造含 5 个结点的 AVL 树，再插入 7 观察调整。
② 分析： 插入前 5 个结点后树应平衡，插入 7 后需检查失衡情况。
③ 过程：
前 5 个结点插入后的 AVL 树：
10 (BF=1)
/ \
5 15 (BF=0)
/ \
3 8各结点 BF 均在 [-1, 1] 范围内，平衡。
插入 7： 7 < 10 → 7 > 5 → 7 < 8，插入 8 的左子。
10 (BF=2) ← 失衡！
/ \
5 15
/ \
3 8 (BF=-1)
/
7- 失衡结点：10，BF = 2
- 左孩子 5，BF = 0 ≥ 0？这里需要仔细看：实际上 5 的 BF = 0...
让我重新检查：插入 7 后，8 的左子树高度 = 1，右子树高度 = 0，所以 8 的 BF = 1。5 的左子树高度 = 1（结点 3），右子树高度 = 2（结点 8→7），所以 5 的 BF = -1。
- 失衡结点 10，BF = 2，左孩子 5 的 BF = -1 < 0 → LR 型！
- 步骤 1： 对结点 5 做左旋：
10 10
/ \ / \
8 15 → 8 15
/ \ / \
5 (原8的右子) 5 (原8的右子，此处为NULL)
/ /
3 3等等，让我更准确地描述：
对 5 做左旋：5 的右孩子 8 提升，5 成为 8 的左孩子，8 的左子树（结点 7）变为 5 的右子树。
10 10
/ \ / \
8 15 → 8 15
/ \ / \
5 7 5 7
/ /
3 3 (这里7原来是8的左子，现在变成5的右子)不对，左旋 5 时：8 成为 5 的父，7 变成 5 的右子。
10 10
/ \ / \
8 15 → 8 15
/ \ / \
5 7 5 7
/ /
3 3这样看 8 的 BF 还是不平衡。让我用标准表述：
LR 型旋转（对 5 先左旋，再对 10 右旋）：
先对 5 左旋： 8 提升，5 降为 8 左孩子，7（原 8 左子）变为 5 的右子。
10 10
/ \ / \
8 15 → 8 15
/ \ / \
7 . 5 . (7 变为 5 的右子)
/ /
5 3
3再对 10 右旋： 8 提升为根，10 降为 8 右孩子。
8
/ \
5 10
/ \ \
3 7 15④ 结论： 插入 7 触发 LR 型失衡（结点 10 的 BF=2，左孩子 5 的 BF<0），通过先左旋 5、再右旋 10 完成调整。最终树平衡，各结点 BF 均在 [-1,1] 内。
考情分析
| 维度 | 说明 |
|---|---|
| 考频 | 高频，每年选择题/综合题必考或常考 |
| 题型 | 选择题（判断旋转类型）、综合题（完整的插入/调整过程） |
| 命题趋势 | 考查 LR/RL 双旋的判断与操作过程；结点数与高度关系 |
| 常见陷阱 | LR 和 RL 的旋转顺序搞混；平衡因子的正负号方向 |
易错点
- LR 型是"先左旋再右旋"，RL 型是"先右旋再左旋"。 旋转对象分别是失衡结点的左孩子和右孩子，不是失衡结点本身。
- 平衡因子 = 左子树高度 - 右子树高度。 BF = 2 说明左子树过高（LL 或 LR），BF = -2 说明右子树过高（RR 或 RL）。
- AVL 插入最多只需一次旋转（单旋或双旋），但删除可能需要 O(log n) 次旋转。 这是因为删除可能导致上层结点失衡，需要递归调整。
- 高度为 h 的 AVL 树最少结点数 N(h) ≈ φ^h（φ为黄金比例），满足 N(h) = N(h-1) + N(h-2) + 1。 这是判断 AVL 树高度范围的重要公式。
来源标注
| 来源 | 说明 |
|---|---|
| 王道考研 | 2026 版数据结构讲义 · 第六章 查找 |
| 天勤考研 | 数据结构高分笔记 · 查找部分 |
| 严蔚敏 | 《数据结构（C 语言版）》第 9 章 |
| 教材参考 | 《数据结构》（第 5 版）李春葆 · 查找章节 |