Appearance
平衡二叉树（AVL）
为什么需要平衡二叉树
普通的二叉排序树（BST）在最坏情况下会退化为单链表——例如按递增序列 1, 2, 3, 4, 5 依次插入，树的高度等于结点数 n，查找效率从 O(log n) 退化为 O(n)。
AVL 树由 Adelson-Velsky 和 Landis 于 1962 年提出，它在 BST 的基础上增加了平衡约束：任意结点的左右子树高度差的绝对值不超过 1。通过在插入/删除后执行旋转操作，AVL 树始终保持平衡，从而将查找、插入、删除的时间复杂度稳定在 O(log n)。
408 考研中，AVL 树是树与二叉树章节的核心考点，尤其是四种旋转的判断与画图。
核心思想
AVL 树的核心特点：
- 平衡因子（Balance Factor）：BF(T) = 左子树高度 - 右子树高度，要求 |BF| ≤ 1
- 自平衡：每次插入或删除后，沿搜索路径向上检查平衡因子，一旦发现 |BF| > 1，立即通过旋转恢复平衡
- 四种旋转：LL（右单旋）、RR（左单旋）、LR（先左后右双旋）、RL（先右后左双旋）
AVL 树结点定义：
c
typedef struct AVLNode {
int data;
int height; // 当前结点的高度
struct AVLNode *lchild; // 左子树
struct AVLNode *rchild; // 右子树
} AVLNode, *AVLTree;最少结点数公式 ⭐：高度为 h 的 AVL 树至少包含的结点数满足递推关系：
N(h) = N(h-1) + N(h-2) + 1其中 N(0) = 0，N(1) = 1，N(2) = 2。该公式类似斐波那契数列，说明 n 个结点的 AVL 树高度为 O(log n)。
| h | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| N(h) | 1 | 2 | 4 | 7 | 12 | 20 | 33 |
交互可视化
通过下方的交互动画，你可以逐步观察平衡二叉树的执行过程：
操作详解
平衡因子
平衡因子定义为左子树高度减去右子树高度：
BF(T) = Height(T->lchild) - Height(T->rchild)AVL 树中每个结点的平衡因子只能是 -1、0、1 三个值之一。
c
int GetHeight(AVLNode *T) {
if (T == NULL) return 0;
return T->height;
}
int GetBF(AVLNode *T) {
return GetHeight(T->lchild) - GetHeight(T->rchild);
}当插入或删除导致某个结点的 |BF| = 2 时，就需要对该结点进行旋转调整。最小不平衡子树是指以距离插入点最近的、|BF| > 1 的结点为根的子树——旋转只需在最小不平衡子树上进行。
LL 旋转
触发条件：在结点 A 的左子树的左子树上插入新结点，导致 BF(A) = 2。
操作：对 A 进行右单旋——将 A 的左孩子 B 提升为新根，A 变为 B 的右孩子，B 的原右子树挂到 A 的左子树上。
A (BF=2) B
/ \ / \
B AR ──→ BL A
/ \ / \
BL BR BR ARc
// LL 右单旋
AVLNode* LL_Rotate(AVLNode *A) {
AVLNode *B = A->lchild;
A->lchild = B->rchild; // B 的右子树挂到 A 的左边
B->rchild = A; // A 成为 B 的右孩子
// 更新高度（先更新 A，再更新 B）
A->height = max(GetHeight(A->lchild), GetHeight(A->rchild)) + 1;
B->height = max(GetHeight(B->lchild), GetHeight(B->rchild)) + 1;
return B; // B 成为新根
}⭐ 记忆口诀：左左 → 右旋（在左孩子的左子树插入，对根做右旋）。
RR 旋转
触发条件：在结点 A 的右子树的右子树上插入新结点，导致 BF(A) = -2。
操作：对 A 进行左单旋——将 A 的右孩子 B 提升为新根，A 变为 B 的左孩子，B 的原左子树挂到 A 的右子树上。
A (BF=-2) B
/ \ / \
AL B ──→ A BR
/ \ / \
BL BR AL BLc
// RR 左单旋
AVLNode* RR_Rotate(AVLNode *A) {
AVLNode *B = A->rchild;
A->rchild = B->lchild; // B 的左子树挂到 A 的右边
B->lchild = A; // A 成为 B 的左孩子
A->height = max(GetHeight(A->lchild), GetHeight(A->rchild)) + 1;
B->height = max(GetHeight(B->lchild), GetHeight(B->rchild)) + 1;
return B;
}⭐ 记忆口诀：右右 → 左旋（在右孩子的右子树插入，对根做左旋）。RR 旋转与 LL 旋转完全对称。
LR 旋转
触发条件：在结点 A 的左子树的右子树上插入新结点，导致 BF(A) = 2 且 BF(B) = -1。
操作：先对 A 的左孩子 B 进行左旋（RR），再对 A 进行右旋（LL）。
A (BF=2) A C
/ \ / \ / \
B AR ──→ C AR ──→ B A
/ \ / \ / \ / \
BL C B CR BL CL CR AR
/ \ / \
CL CR BL CL
(先对B左旋) (再对A右旋)c
// LR 先左旋后右旋
AVLNode* LR_Rotate(AVLNode *A) {
A->lchild = RR_Rotate(A->lchild); // 先对左子树左旋
return LL_Rotate(A); // 再对根右旋
}⭐ 记忆口诀：左右 → 先左旋后右旋（在左孩子的右子树插入，先对左孩子左旋，再对根右旋）。
RL 旋转
触发条件：在结点 A 的右子树的左子树上插入新结点，导致 BF(A) = -2 且 BF(B) = 1。
操作：先对 A 的右孩子 B 进行右旋（LL），再对 A 进行左旋（RR）。
A (BF=-2) A C
/ \ / \ / \
AL B ──→ AL C ──→ A B
/ \ / \ / \ / \
C BR CL B AL CL CR BR
/ \ / \
CL CR CR BR
(先对B右旋) (再对A左旋)c
// RL 先右旋后左旋
AVLNode* RL_Rotate(AVLNode *A) {
A->rchild = LL_Rotate(A->rchild); // 先对右子树右旋
return RR_Rotate(A); // 再对根左旋
}⭐ 记忆口诀：右左 → 先右旋后左旋。RL 旋转与 LR 旋转完全对称。
插入操作
AVL 树的插入分两步：按 BST 规则插入 + 沿路径回溯调整平衡。
关键步骤：
- 按 BST 规则递归找到插入位置，插入新结点
- 回溯更新经过的每个结点的高度
- 计算平衡因子，若 |BF| > 1 则根据四种情况执行旋转
- 插入后至多只需对最小不平衡子树做一次旋转即可恢复整棵树的平衡 ⭐
旋转类型判断表 ⭐：
| BF(A) | 插入位置 | 旋转类型 |
|---|---|---|
| 2（左高） | A 的左子树的左子树 | LL（右单旋） |
| 2（左高） | A 的左子树的右子树 | LR（先左后右双旋） |
| -2（右高） | A 的右子树的右子树 | RR（左单旋） |
| -2（右高） | A 的右子树的左子树 | RL（先右后左双旋） |
c
AVLNode* Insert(AVLNode *T, int x) {
if (T == NULL) {
T = (AVLNode*)malloc(sizeof(AVLNode));
T->data = x;
T->height = 1;
T->lchild = T->rchild = NULL;
return T;
}
if (x < T->data)
T->lchild = Insert(T->lchild, x);
else if (x > T->data)
T->rchild = Insert(T->rchild, x);
else
return T; // 不插入重复值
// 更新高度
T->height = max(GetHeight(T->lchild), GetHeight(T->rchild)) + 1;
// 检查平衡并旋转
int bf = GetBF(T);
if (bf > 1 && x < T->lchild->data) return LL_Rotate(T); // LL
if (bf > 1 && x > T->lchild->data) return LR_Rotate(T); // LR
if (bf < -1 && x > T->rchild->data) return RR_Rotate(T); // RR
if (bf < -1 && x < T->rchild->data) return RL_Rotate(T); // RL
return T;
}删除操作
AVL 树的删除同样分两步：按 BST 规则删除 + 沿路径回溯调整平衡。
关键步骤：
- 按 BST 规则找到并删除目标结点（叶子直接删、单子树替代、双子树用中序前驱/后继替换）
- 从删除位置向上回溯，逐层更新高度并检查平衡
- 若 |BF| > 1，根据该结点较高子树的方向及其孩子的平衡因子判断旋转类型
与插入不同：删除后可能需要多次旋转（沿路径向上每层都可能不平衡），而插入至多一次旋转 ⭐。
c
AVLNode* Delete(AVLNode *T, int x) {
if (T == NULL) return NULL;
if (x < T->data)
T->lchild = Delete(T->lchild, x);
else if (x > T->data)
T->rchild = Delete(T->rchild, x);
else {
// 找到目标结点
if (T->lchild && T->rchild) {
// 用中序前驱替代
AVLNode *pre = T->lchild;
while (pre->rchild) pre = pre->rchild;
T->data = pre->data;
T->lchild = Delete(T->lchild, pre->data);
} else {
AVLNode *child = T->lchild ? T->lchild : T->rchild;
free(T);
return child;
}
}
// 更新高度
T->height = max(GetHeight(T->lchild), GetHeight(T->rchild)) + 1;
// 检查平衡并旋转
int bf = GetBF(T);
if (bf > 1 && GetBF(T->lchild) >= 0) return LL_Rotate(T);
if (bf > 1 && GetBF(T->lchild) < 0) return LR_Rotate(T);
if (bf < -1 && GetBF(T->rchild) <= 0) return RR_Rotate(T);
if (bf < -1 && GetBF(T->rchild) > 0) return RL_Rotate(T);
return T;
}复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 查找 | O(log n) | 树高始终保持 O(log n) |
| 插入 | O(log n) | 查找位置 O(log n) + 至多一次旋转 O(1) |
| 删除 | O(log n) | 查找位置 O(log n) + 可能多次旋转，每次 O(1) |
| 旋转 | O(1) | 单次旋转仅修改常数个指针 |
空间复杂度：O(n)，需要存储 n 个结点及其高度信息。
ASL（平均查找长度）：O(log n)。由于 AVL 树高度严格控制在 O(log n)，查找效率接近理想平衡树。
考研高频考点
- ⭐ 给定插入序列，画出 AVL 树并标注旋转类型（选择题/综合题高频）
- ⭐ 四种旋转的判断条件与操作过程（必须熟练掌握）
- ⭐ 插入至多一次旋转 vs 删除可能多次旋转（判断题/选择题常考）
- ⭐ 高度为 h 的 AVL 树最少结点数：N(h) = N(h-1) + N(h-2) + 1（填空题高频）
- ⭐ n 个结点的 AVL 树最大高度为 O(log n)（概念题）
- 平衡因子的定义与取值范围（-1, 0, 1）
- AVL 树 vs 红黑树的对比（了解即可，408 以 AVL 为主）