一、平衡二叉树（AVL）——让树不再“偏科”

说实话，二叉搜索树（BST）在理想情况下确实好用——查找、插入、删除都能做到 O(log n)。但问题来了：如果你按顺序插入 1、2、3、4、5……这棵树就变成了一条“斜线”，退化成了链表。查找效率直接掉到 O(n)。

我在做数据库索引模块的时候，就吃过这个亏。当时数据量不大，没在意插入顺序，结果某次压测发现查询越来越慢。一查树的高度，好家伙，都快赶上数据量了。嗯，从那以后，我对“平衡”这两个字就特别敏感。

AVL 树，就是来解决这个问题的。它由 Adelson-Velsky 和 Landis 在 1962 年提出，是最早的自平衡二叉搜索树。说白了，它就是在 BST 的基础上加了一条“硬约束”：任何节点的左右子树高度差不能超过 1。

1.1 平衡因子（Balance Factor）

AVL 树怎么判断自己“歪了”？靠一个叫平衡因子的东西。

平衡因子 = 左子树高度 - 右子树高度

取值范围：-1、0、1。一旦超出这个范围，就需要调整。

我习惯把平衡因子想象成“天平上的指针”。左重了就是正数，右重了就是负数。绝对值超过 1，天平就翻了。

举个例子：

        10 (bf = 1)
       /  \
      5    15 (bf = 0)
     / \
    3   7 (bf = 0)
   /
  2 (bf = 0)

节点 10 的平衡因子是 1（左子树高度 2，右子树高度 1），没问题。但如果再插入一个 1：

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

节点 10 的平衡因子变成了 2，左子树比右子树高了 2 层。这时候就需要旋转了。

小技巧：我写 AVL 树的时候，每个节点都会存一个 height 字段，而不是每次都递归计算。这样平衡因子的计算就是 O(1) 的，省心不少。

1.2 四种旋转调整

AVL 树的旋转，说白了就是“重新摆正”这棵树。一共四种情况，我一个个说。

1.2.1 LL 型（右旋）

LL 型，就是“左子树的左子树”插入了新节点，导致失衡。这种情况需要右旋。

我曾经在写一个内存分配器的红黑树替代方案时，第一次手写 AVL 旋转就栽在了 LL 型上。当时没搞清楚旋转后子树的归属，结果指针乱飞，调试了一下午。

看个例子：

    失衡节点 10
       /
      5
     /
    3

右旋后：

      5
     / \
    3   10

代码实现：

Node* rotateRight(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;

    // 旋转
    x->right = y;
    y->left = T2;

    // 更新高度
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x;  // 新的根
}

1.2.2 RR 型（左旋）

RR 型是 LL 型的镜像——右子树的右子树插入了新节点。需要左旋。

    失衡节点 10
       \
        15
          \
           20

左旋后：

      15
     /  \
    10   20

代码实现：

Node* rotateLeft(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

    y->left = x;
    x->right = T2;

    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    return y;
}

注意：旋转后一定要更新高度！我见过有人忘了更新高度，结果平衡因子算错，树越调越乱。更新顺序也有讲究——先更新子节点，再更新父节点。

1.2.3 LR 型（先左旋再右旋）

LR 型稍微复杂一点——左子树的右子树插入了新节点。不能直接右旋，需要先左旋左子树，再右旋失衡节点。

你想想看，如果直接右旋，左子树的右子树会跑到哪里去？结构会乱掉。

    失衡节点 10
       /
      5
       \
        7

第一步：左旋左子树（节点 5）

    10
   /
  7
 /
5

第二步：右旋失衡节点（节点 10）

    7
   / \
  5   10

代码实现：

Node* rotateLR(Node* z) {
    z->left = rotateLeft(z->left);
    return rotateRight(z);
}

1.2.4 RL 型（先右旋再左旋）

RL 型是 LR 型的镜像——右子树的左子树插入了新节点。需要先右旋右子树，再左旋失衡节点。

    失衡节点 10
       \
        15
       /
      12

第一步：右旋右子树（节点 15）

    10
      \
       12
         \
          15

第二步：左旋失衡节点（节点 10）

    12
   /  \
  10   15

代码实现：

Node* rotateRL(Node* z) {
    z->right = rotateRight(z->right);
    return rotateLeft(z);
}

1.3 四种旋转的快速判断

我总结了一个口诀，帮你快速判断该用哪种旋转：

失衡类型 平衡因子符号 操作
LL 失衡节点 bf = +2，左孩子 bf = +1 右旋
RR 失衡节点 bf = -2，右孩子 bf = -1 左旋
LR 失衡节点 bf = +2，左孩子 bf = -1 先左旋左孩子，再右旋
RL 失衡节点 bf = -2，右孩子 bf = +1 先右旋右孩子，再左旋

说白了，你只要记住：看失衡节点和它的孩子，符号相同就单旋，符号相反就双旋。

1.4 知识体系总览

下面这张图，把 AVL 树的核心逻辑串起来了。我建议你多看几遍，理解每个模块之间的关系。

AVL 树知识体系 AVL 树定义 平衡因子 = 左高 - 右高 失衡：|bf| > 1 平衡：|bf| ≤ 1 LL 型 → 右旋 RR 型 → 左旋 LR 型 → 左+右 RL 型 → 右+左

1.5 插入操作的整体流程

最后，我把 AVL 树插入的完整流程梳理一下。你写代码的时候，按这个步骤来，基本不会出错：

  1. 普通 BST 插入——先不管平衡，把节点放到正确位置。
  2. 更新高度——从插入节点向上回溯，更新每个祖先节点的高度。
  3. 检查平衡因子——计算每个祖先节点的平衡因子。
  4. 如果失衡——判断是 LL、RR、LR、RL 中的哪一种，执行对应的旋转。
  5. 返回新根——旋转后，原来的子树根可能变了，记得更新父节点的指针。

避坑指南：我曾经在递归插入后忘了把旋转返回的新根赋值给父节点的左/右指针。结果树的结构是对的，但父节点还指着旧根，整个树就断了。嗯，血的教训。

AVL 树虽然比普通 BST 多了一些旋转的开销，但换来的是稳定的 O(log n) 查找性能。在需要频繁查找、插入顺序不可控的场景下，AVL 树是一个非常靠谱的选择。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →