Appearance
平衡二叉树（AVL）
概念
平衡二叉树（AVL 树，由 Adelson-Velsky 与 Landis 提出）是一棵二叉排序树，且任一结点的左、右子树高度之差的绝对值不超过 1。
这个高度差叫平衡因子（BF, Balance Factor）：
一句话理解：AVL = 二叉排序树 + "每棵树都不许长歪"，用旋转在插入删除后把歪掉的地方拧回来，从而保证树高始终是对数级。
原理
为什么需要它
上一章已经看到：BST 的查找效率取决于树高 h，而树高取决于输入顺序。有序插入会退化成链表（h = n，查找 O(n)）。AVL 通过"每次插入/删除后立刻把失衡修好"，把树高锁在 O(log n)。
最小不平衡子树
插入一个新结点后，可能失衡的结点只可能在这条插入路径上。我们的做法是：
- 从插入点沿路径向上找，遇到的第一个 |BF| > 1 的结点，记为 A；
- 以 A 为根的这棵子树叫最小不平衡子树；
- 只需把以 A 为根的这棵子树"旋转"回平衡，整棵树就恢复平衡了。
记忆：插入时只需调整一次（四种旋转之一），因为调整后该子树高度恢复到插入前的高度，其所有祖先的平衡因子也随之恢复。 删除时则不同：调整后子树高度可能比删除前矮 1，失衡会向上传播，需要一路向上多次调整。这是插入与删除的关键区别。
四种失衡情形与旋转
失衡的根源是"插入方向"。定义三个结点：
- A：最小不平衡子树的根（|BF| = 2）；
- B：A 的孩子，位于"更高那一侧"；
- C：插入路径上 B 的孩子。
| 情形 | 条件 | 形象说法 | 旋法 | 结果 |
|---|---|---|---|---|
| LL | 插到 A 左子树的左侧 | 左边左边多了一个 | 对 A 右单旋 | B 上位，A 降为 B 的右孩子 |
| RR | 插到 A 右子树的右侧 | 右边右边多了一个 | 对 A 左单旋 | B 上位，A 降为 B 的左孩子 |
| LR | 插到 A 左子树的右侧 | 左边右边多了一个 | 先对 B 左旋，再对 A 右旋 | C 上位，B 与 A 分列左右 |
| RL | 插到 A 右子树的左侧 | 右边左边多了一个 | 先对 B 右旋，再对 A 左旋 | C 上位，A 与 B 分列左右 |
记忆口诀：是哪一侧多了，就往反方向转。LL 是左边多 → 右转（顺时针）；RR 是右边多 → 左转（逆时针）；LR/RL 是先"拧直"成 LL/RR，再做一次单旋。
右单旋（LL）的指针变化
A (BF=+2) B
/ / \
B --右单旋--> C A
/ \ /
C T2 T2- B 的右孩子 T2 转挂到 A 的左孩子（因为 T2 里的值都在 B 与 A 之间）；
- A 变成 B 的右孩子；B 顶替 A 原来的位置。
左单旋完全对称。
LR 双旋的指针变化
A A C
/ / / \
B --左旋B--> C --右旋A--> B A
\ / \ /
C B T T3先对 B 左旋（C 上位），把"折线"拉成"直线"（变成 LL 形），再对 A 右旋。
平衡二叉树的高度与最少结点数
设
| h | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 4 | 7 | 12 | 20 | 33 | 54 |
由此得到两个常考结论：
- 高度为 h 的 AVL 树，结点数至少为
- 反过来，n 个结点的 AVL 树，高度至多约
推论：AVL 的查找、插入、删除时间复杂度均为
示例
例：依次插入 16, 3, 7, 11, 9, 26, 18, 14, 15
画出每步调整后的 AVL 树，并求等概率成功 ASL。
完整推导过程：
第一步，插入 16、3：16 为根，3 为其左孩子，BF(16) = +1，平衡。
16
/
3第二步，插入 7：7 < 16 → 左；7 > 3 → 3 的右孩子。此时 BF(3) = −1，BF(16) = +2 → 最小不平衡子树根为 16。7 插在 16 的左子树的右侧 → LR 型：先对 3 左旋，再对 16 右旋 → 7 上位。
插入后（失衡） 左旋 3 右旋 16
16 16 7
/ / / \
3 --> 7 --> 3 16
\ /
7 3第三步，插入 11：11 > 7 → 16 的左孩子。全树 BF 均在 ±1 内，无需调整。
第四步，插入 9：9 → 7 的右 → 16 的左 → 11 的左。BF(16) = +2，BF(7) = −1（仍合法）→ 最小不平衡子树根为 16；9 在 16 左子树的左侧 → LL 型：对 16 右单旋，11 上位。
7 7
/ \ / \
3 16 --右旋16--> 3 11
/ / \
11 9 16
/
9第五步，插入 26：26 → 11 的右 → 16 的右。BF(16) = −1，BF(11) = −1，BF(7) = −2 → 最小不平衡子树根为 7；26 在 7 右子树的右侧 → RR 型：对 7 左单旋，11 上位成为整树的根。
7 11
/ \ / \
3 11 --左旋7--> 7 16
/ \ / \ \
9 16 3 9 26
\
26第六步，插入 18：18 → 11 的右 → 16 的左 → 26 的左。BF(16) = −2 → RL 型：先对 26 右旋，再对 16 左旋，18 上位。
16 16 18
\ \ / \
26 --右旋26--> 18 --左旋16-> 16 26
/ \
18 26第七步，插入 14：14 → 11 的右 → 18 的左 → 16 的左。检查 BF：16 为 +1，18 为 +1，11 为 −1，全部合法，无需调整。
第八步，插入 15：15 → 11 的右 → 18 的左 → 16 的左 → 14 的右。检查 BF：14 为 −1，16 为 +2 → 最小不平衡子树根为 16；15 在 16 左子树的右侧 → LR 型：先对 14 左旋，再对 16 右旋，15 上位。
最终 AVL 树：
11 第 1 层
/ \
7 18 第 2 层
/ \ / \
3 9 15 26 第 3 层
/ \
14 16 第 4 层成功 ASL（各结点比较次数 = 所在层数）：
对照：同样这 9 个关键字若按升序插入普通 BST，树高为 9，成功 ASL = (1+2+…+9)/9 = 5。AVL 把平均查找长度从 5 压到 2.78。
C 语言：AVL 插入与四种旋转
#include <stdio.h>
#include <stdlib.h>
typedef struct AVLNode {
int key;
int height; /* 结点高度：叶子为 1，空树（NULL）为 0 */
struct AVLNode *l, *r;
} AVLNode, *AVLTree;
static int h(AVLNode *t) { return t ? t->height : 0; }
static int bf(AVLNode *t) { return t ? h(t->l) - h(t->r) : 0; }
static int max2(int a, int b) { return a > b ? a : b; }
static void upd(AVLNode *t) { t->height = max2(h(t->l), h(t->r)) + 1; }
/* 右单旋（LL）：y 失衡，其左孩子 x 上位 */
AVLNode *rotR(AVLNode *y) {
AVLNode *x = y->l;
y->l = x->r; /* x 的右子树转挂到 y 的左边 */
x->r = y;
upd(y); upd(x); /* 先更新低的，再更新高的 */
return x;
}
/* 左单旋（RR）：与右单旋完全对称 */
AVLNode *rotL(AVLNode *x) {
AVLNode *y = x->r;
x->r = y->l;
y->l = x;
upd(x); upd(y);
return y;
}
AVLNode *insert(AVLTree t, int key) {
if (!t) {
AVLNode *s = (AVLNode *)malloc(sizeof(AVLNode));
s->key = key; s->height = 1; s->l = s->r = NULL;
return s;
}
if (key < t->key) t->l = insert(t->l, key);
else if (key > t->key) t->r = insert(t->r, key);
else return t; /* 不插入重复关键字 */
upd(t);
int b = bf(t);
if (b > 1) { /* 左边高了 */
if (key > t->l->key) t->l = rotL(t->l); /* LR：先左旋 */
return rotR(t); /* 再右旋 */
}
if (b < -1) { /* 右边高了 */
if (key < t->r->key) t->r = rotR(t->r); /* RL：先右旋 */
return rotL(t); /* 再左旋 */
}
return t;
}
void inOrder(AVLTree t) {
if (!t) return;
inOrder(t->l);
printf("%d(BF=%d) ", t->key, bf(t));
inOrder(t->r);
}
int main(void) {
AVLTree t = NULL;
int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
for (int i = 0; i < 9; i++) t = insert(t, a[i]);
inOrder(t); /* 3 7 9 11 14 15 16 18 26，且每个 BF 都在 ±1 内 */
printf("\nroot = %d, height = %d\n", t->key, t->height); /* root = 11, height = 4 */
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
Python 对照
class AVL:
def __init__(self): self.root = None
def _h(self, t): return t['h'] if t else 0
def _upd(self, t): t['h'] = max(self._h(t['l']), self._h(t['r'])) + 1
def _bf(self, t): return self._h(t['l']) - self._h(t['r']) if t else 0
def _rotR(self, y):
x = y['l']; y['l'] = x['r']; x['r'] = y
self._upd(y); self._upd(x); return x
def _rotL(self, x):
y = x['r']; x['r'] = y['l']; y['l'] = x
self._upd(x); self._upd(y); return y
def insert(self, k, t=None):
if t is None:
if self.root is None:
self.root = {'key': k, 'h': 1, 'l': None, 'r': None}
return self.root
return {'key': k, 'h': 1, 'l': None, 'r': None}
if k < t['key']: t['l'] = self.insert(k, t['l'])
elif k > t['key']: t['r'] = self.insert(k, t['r'])
else: return t
self._upd(t)
b = self._bf(t)
if b > 1:
if k > t['l']['key']: t['l'] = self._rotL(t['l'])
return self._rotR(t)
if b < -1:
if k < t['r']['key']: t['r'] = self._rotR(t['r'])
return self._rotL(t)
return t
def build(self, keys):
for k in keys: self.root = self.insert(k, self.root)
def inorder(self, t=None):
if t is None: t = self.root
return [] if not t else self.inorder(t['l']) + [t['key']] + self.inorder(t['r'])
def asl(self, t=None, d=1):
if t is None: t = self.root
if not t: return 0, 0
ln, lc = self.asl(t['l'], d + 1); rn, rc = self.asl(t['r'], d + 1)
return ln + rn + 1, lc + rc + d
tree = AVL()
tree.build([16, 3, 7, 11, 9, 26, 18, 14, 15])
print(tree.inorder()) # [3, 7, 9, 11, 14, 15, 16, 18, 26]
print('root', tree.root['key'], 'h', tree.root['h']) # root 11 h 4
n, tot = tree.asl()
print(n, tot, round(tot / n, 2)) # 9 25 2.78
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
考点
考点
1. 必背结论
- AVL 是二叉排序树的加强，中序序列仍递增。
- 平衡因子
- 插入时只调整一次（最小不平衡子树的一次旋转），删除时可能调整多次（失衡向上传播）。
- 四种旋转：LL→右单旋、RR→左单旋、LR→先左后右、RL→先右后左。旋转后中序序列不变，这是旋转合法性的保证。
- 查找 / 插入 / 删除均为
2. 手画树的套路
- 每插一个就自底向上检查一次 BF，遇到第一个 |BF| = 2 的结点停下，它就是最小不平衡子树的根。
- 判定类型看插入关键码落在哪：比 A 小还是大 → 决定左/右；比 B 小还是大 → 决定第二个字母。
- 旋转后别忘了更新高度，高度错了后面全错。
3. 易错点
- "平衡二叉树"不等于"最优二叉树"。后者指哈夫曼树，两者完全不是一回事，别看到"最优"就想到 AVL。
- 平衡因子定义是
- 空树高度为 0、叶子高度为 1（也有教材把空树记作 −1），计算 BF 时不要混用两套高度。
- LR/RL 双旋的中间结果是 LL/RR 形，先旋孩子、再旋根，顺序反了会得到一棵不合法的 BST。
- 删除结点后的调整，被删结点若用中序后继顶替，平衡检查要从那个后继的父结点开始向上，而不是从被删位置。
- 考题问"n 个结点的 AVL 树至多多高" → 用
小结
- AVL = BST + 平衡因子约束，把树高锁在 O(log n)，解决 BST 退化成链表的问题。
- 失衡调整的落点是最小不平衡子树：四种旋转覆盖所有情况，插入一次、删除多次。
- 高度分析靠递推
- 下一步：把"平衡"的思想用于编码，就是哈夫曼树与哈夫曼编码。
下一篇：哈夫曼树与哈夫曼编码
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。