Chapter 8: 平衡树

还记得如果我们将数据按顺序插入BST会出现什么问题吗？我们的结果会变成一个链表，所有操作退化为 $O(n)$。

本章我们引入平衡树——这些树会在插入或删除过程中自动调整结构，强制保持平衡，从而保证操作复杂度始终是 $O(\log n)$。

AVL 树

AVL 树是一种自平衡二叉搜索树，由 Adelson-Velsky 和 Landis 在 1962 年发明（AVL 就是他们名字的首字母）。它通过维护平衡因子来保证树的高度始终保持在 $O(\log n)$。

平衡因子

每个节点都有一个平衡因子 (Balance Factor)，定义为：

$$\text{BF}(node) = \text{Height}(\text{左子树}) - \text{Height}(\text{右子树})$$

AVL 树的核心约束是：每个节点的平衡因子只能是 -1, 0, 或 1。

不同的平衡因子能够代表当前树的状态：

• BF = -1 : 右子树比左子树高 1
• BF = 0 : 左右子树一样高
• BF = +1 : 左子树比右子树高 1
• BF = ±2 : 失衡！需要旋转修复

举个例子：

1
2
3
4
5
6
7

    10 (BF=1)          10 (BF=2) ← 失衡！
   /  \               /
  5    15            5
 /                  /
3                  3
                  /
                 1

如果插入或删除操作导致某个节点的平衡因子变成 -2 或 +2，就需要通过旋转来恢复平衡。

实现一个AVL树相比BST,我们需要额外存储当前节点的高度。这是我们需要存储的字段：

• key：当前节点的值
• left：指向左子节点的指针
• right：指向右子节点的指针
• height: 当前节点的高度。
• parent：与BST一样，这是一个指向父节点的可选指针。

1
2
3
4
5
6
7
8

struct AVLNode {
    int key;
    AVLNode* left;
    AVLNode* right;
    int height;
    AVLNode* parent; // 可选
}

由于AVL树存在实时平衡需求，因此只要存储了高度，我们就可以使用公式来计算平衡因子了。

AVL 树的高度与斐波那契数

那么知道了这些，AVL树在数学上有哪些特征？

一个关键问题是：高度为 h 的 AVL 树，最少需要多少个节点？

设 $N(h)$ 为高度为 $h$ 的 AVL 树的最少节点数。为了让节点数最少，我们要让树"尽可能不平衡但又刚好满足 AVL 条件"——也就是让两棵子树的高度差恰好为 1。

这样就得到递推公式：

$$N(h) = N(h-1) + N(h-2) + 1$$

• $N(h-1)$：较高的子树（高度 $h-1$）的最少节点数
• $N(h-2)$：较矮的子树（高度 $h-2$）的最少节点数
• $+1$：根节点自己

初始条件：$N(0) = 1$（只有根），$N(1) = 2$（根 + 一个子节点）

这个数列和斐波那契数列密切相关：$N(h) = F_{h+3} - 1$（其中 $F$ 是斐波那契数列）

由于斐波那契数列增长是指数级的（$F_n \approx \phi^n / \sqrt{5}$，$\phi \approx 1.618$），所以：

$$h = O(\log n)$$

这就证明了 AVL 树的高度一定是 $O(\log n)$，从而保证所有操作都是 $O(\log n)$！

使用刚才讲过的公式：

$$N(h) = N(h-1) + N(h-2) + 1$$

在基准情况时，$N(0) = 1$，因为一个节点的树高度为0。
$N(1) = 2$，包含一个根和两个子节点

你只需要继续往下推进就可以算出来第五层有多少节点了！

AVL 的旋转操作

当 AVL 树失衡时，我们需要通过旋转来恢复平衡。旋转的本质是在保持 BST 性质的前提下，重新组织节点的父子关系。

我们用右旋来解释一下什么叫旋转。
右旋的核心思想：把左子节点"提上来"当新的根。

1
2
3
4
5
6

右旋前：           右旋后：
    y                 x
   / \               / \
  x   C    →        A   y
 / \                   / \
A   B                 B   C

不难观察到这几点：

• x 原来是 y 的左子节点，现在 x 变成新的根
• x 的右子树 B 原来在 x 右边，现在要"让给" y 当左子树
• 最关键的 BST 性质仍然保持：A < x < B < y < C

如果左子树过高，我们就会在对应的子树来执行右旋。右旋的规则是：

1. 将失衡节点的左子节点提升为新的根
2. 让失衡节点变为它左子节点的右子节点
3. 让原本失衡节点的左子节点的右子树悬挂在失衡节点的左子树位置

如果还是很抽象就看看代码吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 右旋：把 y 的左孩子 x 提升为新根
TreeNode* rightRotate(TreeNode *y) {
    TreeNode *x = y->left;
    TreeNode *B = x->right;
    
    // 执行旋转
    x->right = y;
    y->left = B;
    
    // 更新高度（先更新 y，再更新 x）
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
    
    return x;  // x 是新的根
}

左旋与右旋是对称操作。最后的结果会把右子节点"提上来"。过程是：

1. 将失衡节点的右子节点提升为新的根
2. 将失衡节点变为它右子节点的左子节点
3. 让原本失衡节点的右子节点的左子树悬挂在失衡节点的右子树位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 左旋：把 x 的右孩子 y 提升为新根
TreeNode* leftRotate(TreeNode *x) {
    TreeNode *y = x->right;
    TreeNode *B = y->left;
    
    // 执行旋转
    y->left = x;
    x->right = B;
    
    // 更新高度
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;
    
    return y;  // y 是新的根
}

四种失衡类型与对应旋转

根据失衡的位置，一共有四种情况可以对号入座进行处理：

1. LL 型（左左）→ 右旋一次

失衡节点的左子树的左子树过高。

1
2
3
4
5

    z (BF=2)                y
   /                      /   \
  y          右旋 z      x     z
 /            →
x

2. RR 型（右右）→ 左旋一次

失衡节点的右子树的右子树过高。（LL 的镜像）

1
2
3
4
5

z (BF=-2)                  y
 \                       /   \
  y        左旋 z       z     x
   \         →
    x

3. LR 型（左右）→ 先左旋后右旋

失衡节点的左子树的右子树过高。这时单次旋转解决不了问题！

1
2
3
4
5

  z (BF=2)             z                  y
 /                    /                 /   \
x         先左旋 x   y       再右旋 z   x     z
 \          →       /          →
  y                x

4. RL 型（右左）→ 先右旋后左旋

失衡节点的右子树的左子树过高。（LR 的镜像）

1
2
3
4
5

z (BF=-2)          z                    y
 \                  \                 /   \
  x     先右旋 x     y    再左旋 z   z     x
 /        →          \       →
y                     x

这里有一些判断旋转类型的技巧：

1. 找到最近的失衡节点（从插入点往上找第一个 $|BF| = 2$ 的节点）
2. 从失衡节点出发，沿着较高的子树方向走两步
3. 两步的方向决定类型：LL、LR、RL、RR
4. 随后进行相对应的旋转即可。也就是：

• LL：单次右旋
• RR: 单次左旋
• LR：先左旋再右旋
• RL：先右旋在左旋

我不知道为啥我又重复了一遍。

那么我们怎么确定在每个节点的哪边是较高子树呢？还记得AVL树的每个节点额外存储了高度信息吗？你现在要做的就是访问左右子节点，抓取他们的高度值，然后通过左子节点高度减去右子节点高度计算当前节点的平衡因子。

如果BF是正数，则证明左边比右边高，你就应该在这个节点往左边走，反之亦然。

AVL 旋转可视化

下面的可视化可以帮助你直观理解四种旋转操作：

1. 插入 30：树只有根节点，平衡
2. 插入 20：20 < 30，插入为左子节点，平衡因子 = 1，仍然平衡
3. 插入 10：10 < 20，插入为 20 的左子节点
   • 此时 30 的平衡因子 = 2（左子树高度2，右子树高度0）
   • 失衡类型：从 30 出发，先走到 20（左），再走到 10（左）→ LL 型
   • 执行右旋：20 成为新的根，30 成为 20 的右子节点

最终结构：

1
2
3

  20
 /  \
10   30

AVL 树的性能

由于 AVL 树始终保持平衡，所有操作的时间复杂度都是 $O(\log n)$：

AVL 树的插入完整流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

TreeNode* insertAVL(TreeNode *node, int key) {
    // 1. 正常 BST 插入
    if (node == NULL) return createNode(key);
    
    if (key < node->data)
        node->left = insertAVL(node->left, key);
    else if (key > node->data)
        node->right = insertAVL(node->right, key);
    else
        return node;  // 不允许重复
    
    // 2. 更新高度
    node->height = 1 + max(height(node->left), height(node->right));
    
    // 3. 计算平衡因子
    int balance = getBalance(node);
    
    // 4. 根据失衡类型执行旋转
    // LL 型
    if (balance > 1 && key < node->left->data)
        return rightRotate(node);
    
    // RR 型
    if (balance < -1 && key > node->right->data)
        return leftRotate(node);
    
    // LR 型
    if (balance > 1 && key > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    
    // RL 型
    if (balance < -1 && key < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    
    return node;  // 无需旋转
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

TreeNode* deleteAVL(TreeNode *node, int key) {
    // 1. 正常 BST 删除
    if (node == NULL) return NULL;
    
    if (key < node->data)
        node->left = deleteAVL(node->left, key);
    else if (key > node->data)
        node->right = deleteAVL(node->right, key);
    else {
        // 找到要删除的节点
        if (node->left == NULL || node->right == NULL) {
            TreeNode *temp = node->left ? node->left : node->right;
            free(node);
            return temp;
        }
        // 有两个子节点，用后继替换
        TreeNode *succ = findMin(node->right);
        node->data = succ->data;
        node->right = deleteAVL(node->right, succ->data);
    }
    
    if (node == NULL) return NULL;
    
    // 2. 更新高度
    node->height = 1 + max(height(node->left), height(node->right));
    
    // 3. 检查平衡并旋转（与插入类似，但判断条件略有不同）
    int balance = getBalance(node);
    
    // LL
    if (balance > 1 && getBalance(node->left) >= 0)
        return rightRotate(node);
    // LR
    if (balance > 1 && getBalance(node->left) < 0) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    // RR
    if (balance < -1 && getBalance(node->right) <= 0)
        return leftRotate(node);
    // RL
    if (balance < -1 && getBalance(node->right) > 0) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    
    return node;
}

AVL 树 vs 普通 BST

考试要点总结

这些概念一定要记住！

常见考察范围：

1. 手动模拟插入序列：给一串数字，要求画出每一步的 AVL 树
2. 判断旋转类型：给出失衡的树，判断是 LL/RR/LR/RL 哪种
3. 计算平衡因子：给一棵树，计算每个节点的 BF
4. 证明高度界：为什么 AVL 树高度是 $O(\log n)$？（用斐波那契递推）
5. 比较 BST 和 AVL：什么时候选择用哪个？

解题技巧：每插入一个节点后，从插入点往上检查平衡因子。遇到 |BF| = 2 的节点就执行相应旋转。

这道题中，插入 5 后会触发一次旋转（在节点 25 处）。其他插入都保持平衡。

最终结构（供参考）：

1
2
3
4
5
6
7

         50
       /    \
     25      75
    /  \    /  \
  10   30  60   80
 /  \  /   /
5  15 27  55