CC++ & Algorithm

AVL树：严格平衡的“天平”树

较难2
语言版本：C++
概述：AVL树通过记录每个节点的高度，在插入或删除后检查平衡因子并旋转，使整棵树始终保持左右子树高度差不超过1。

AVL树：严格平衡的“天平”树——让二叉搜索树永远不倒

你有没有遇到过这样的情况：排队买东西时，本来队伍整整齐齐，但有人不断插队，结果队伍越来越歪，最后找一个人要绕好远？在计算机里，二叉搜索树也会遇到类似的问题——如果插入的数据是“有序”的（比如从小到大），树就会长成一条“斜线”，查找起来和数组差不多慢（O(n)）。AVL树就是来解决这个问题的：它像一台自动调节的“天平”，保证树在任何时候左右两边的高度差不超过1，这样查找、插入、删除都能稳定快速（O(log n)）。

AVL树是最早发明的自平衡二叉搜索树，名字来自两位发明者Adelson-Velsky和Landis。每个节点会记录自己的高度（从当前节点到最远叶子节点的距离）。当你插入或删除节点后，AVL树会从受影响的节点开始，一路往上检查，如果发现某个节点的左右子树高度差（称为平衡因子）超过了1（即2或-2），就立刻用旋转操作来“扶正”它。旋转动作就像用手轻轻一推，让歪掉的子树重新平衡。

平衡因子：天平上的“差距”

每个节点的平衡因子 = 左子树高度 - 右子树高度。

  • 如果平衡因子为0，说明左右一样高，很平衡。
  • 如果为1或-1，还在允许范围内（可以接受）。
  • 如果为2或-2，说明天平倾斜了，需要旋转。

生活中的例子：你和同桌各有一摞书。你的书堆高度是5本，同桌的书堆高度是3本，你们的“平衡因子”就是5-3=2。这已经超过1了，老师会让你们互相传递几本书，让两堆高度差不超过1。AVL树的旋转就是这样的“传递”过程。

四种旋转：就像掰手腕

旋转是AVL树的核心操作，一共分为四种情况，名字很好记：LL、RR、LR、RL。每个名字代表“失衡的方向”和“旋转的方法”。

1. LL（左左）——右旋

场景：某个节点的左子树太高，并且左子树的左子树也高（重心偏左偏）。
动作：将当前节点向右旋转，就像把左边的大个子同学“提”到上面来。
代码：rotateRight(y)，其中y是失衡节点。

2. RR（右右）——左旋

场景：某个节点的右子树太高，并且右子树的右子树也高（重心偏右偏）。
动作：将当前节点向左旋转。
代码：rotateLeft(x)。

3. LR（左右）——先左旋再右旋

场景：某个节点的左子树太高，但左子树的右子树高（重心先左后右）。
动作：先对左子节点左旋（变成LL情况），再对当前节点右旋。

4. RL（右左）——先右旋再左旋

场景：某个节点的右子树太高，但右子树的左子树高（重心先右后左）。
动作：先对右子节点右旋（变成RR情况），再对当前节点左旋。

记忆技巧：LL和RR是“单旋转”，只有一次；LR和RL是“双旋转”，需要两次。名字的第一个字母代表“失衡的方向”中较深的那一侧，第二个字母代表该侧的子树的偏向。

插入操作：一步一步保证平衡

插入一个节点后，AVL树会：

  1. 递归插入：像普通二叉搜索树一样，找到合适的位置插入新节点。
  2. 更新高度：从新节点开始，沿着递归路径往回走，更新每个节点的高度（高度 = 1 + max(左子树高, 右子树高)）。
  3. 检查平衡因子：对每个经过的节点计算平衡因子，如果绝对值>1，就根据情况旋转。
  4. 返回新根：旋转后返回新的子树根节点，使得上层能正确连接。

注意：插入时如果遇到相等的值，通常约定不插入重复值（直接返回原节点），或者你也可以选择插入到左子树或右子树，但需要保持一致。

代码实现：带中文注释的完整版

下面是一个完整的AVL树插入和遍历的C++程序。每一行变量定义都加了中文注释，方便理解。

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;         // 节点值
    int height;      // 节点高度（从当前到最远叶子）
    Node* left;      // 左孩子指针
    Node* right;     // 右孩子指针
    Node(int v) : val(v), height(1), left(nullptr), right(nullptr) {}
};

// 获取节点高度（空节点高度为0）
int getHeight(Node* p) {
    return p ? p->height : 0;
}

// 获取平衡因子：左高 - 右高
int getBalance(Node* p) {
    return p ? getHeight(p->left) - getHeight(p->right) : 0;
}

// 更新节点高度
void updateHeight(Node* p) {
    p->height = 1 + max(getHeight(p->left), getHeight(p->right));
}

// 右旋（处理LL失衡）
Node* rotateRight(Node* y) {
    Node* x = y->left;      // x是y的左孩子，将来成为新根
    Node* T2 = x->right;    // T2是x的右子树，要转移到y的左子树
    x->right = y;           // x的右孩子变成y
    y->left = T2;           // y的左孩子变成T2
    updateHeight(y);        // 先更新y，因为y现在在下面
    updateHeight(x);        // 再更新x，x是新的根
    return x;               // 返回新根
}

// 左旋（处理RR失衡）
Node* rotateLeft(Node* x) {
    Node* y = x->right;     // y是x的右孩子，将来成为新根
    Node* T2 = y->left;     // T2是y的左子树，要转移到x的右子树
    y->left = x;            // y的左孩子变成x
    x->right = T2;          // x的右孩子变成T2
    updateHeight(x);        // 先更新x
    updateHeight(y);        // 再更新y
    return y;               // 返回新根
}

// 插入节点（递归）
Node* insert(Node* node, int key) {
    // 空节点直接创建新节点
    if (!node) return new Node(key);

    // 标准BST插入：小于往左，大于往右，等于不重复
    if (key < node->val)
        node->left = insert(node->left, key);
    else if (key > node->val)
        node->right = insert(node->right, key);
    else
        return node;   // 值已存在，直接返回

    // 更新当前节点高度
    updateHeight(node);
    int balance = getBalance(node);   // 计算平衡因子

    // LL情况：左左，平衡因子>1且key小于左孩子值
    if (balance > 1 && key < node->left->val)
        return rotateRight(node);

    // RR情况：右右，平衡因子<-1且key大于右孩子值
    if (balance < -1 && key > node->right->val)
        return rotateLeft(node);

    // LR情况：左右，平衡因子>1且key大于左孩子值
    if (balance > 1 && key > node->left->val) {
        node->left = rotateLeft(node->left);   // 先左旋左孩子
        return rotateRight(node);              // 再右旋当前节点
    }

    // RL情况：右左，平衡因子<-1且key小于右孩子值
    if (balance < -1 && key < node->right->val) {
        node->right = rotateRight(node->right); // 先右旋右孩子
        return rotateLeft(node);                // 再左旋当前节点
    }

    // 不需要旋转，直接返回当前节点
    return node;
}

// 中序遍历（输出有序序列）
void inorder(Node* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

int main() {
    Node* root = nullptr;
    // 依次插入 3,2,1,4,5,6,7
    for (int x : {3, 2, 1, 4, 5, 6, 7}) {
        root = insert(root, x);
    }
    inorder(root);   // 输出有序序列
    cout << endl;
    return 0;
}

运行结果：中序遍历会输出 1 2 3 4 5 6 7，说明所有数据按升序排列。虽然插入顺序是无序的，但AVL树始终保持了二叉搜索树的性质。

常见错误（新手容易踩的坑）

❌ 忘记更新高度

旋转后只更新了节点的左/右指针，但忘记调用updateHeight。这会导致后续平衡因子计算错误，树可能再次失衡。

❌ 平衡因子符号搞反

有些资料用“右子树高度 - 左子树高度”，如果混淆了符号，旋转条件就会对应错误。建议始终统一用“左高 - 右高”，然后LL对应>1，RR对应<-1。

❌ 旋转方向写反

比如LR情况应该是先左旋左孩子再右旋当前节点，如果写成先右旋再左旋，就会变成RL。可以这样记忆：失衡节点的左孩子先右旋？不，LR的“L”表示失衡节点的左子树重，“R”表示左孩子的右子树重，所以第一步要对左孩子做左旋（因为左孩子的右子树重，左旋能把它转到右边）？实际上要分清：LR失衡是左孩子的右子树太高，所以先对左孩子左旋（减小它的右子树高度），再对当前节点右旋。容易记混时，建议画一棵树模拟一下。

❌ 插入重复值处理不当

如果不处理重复值，直接插入到左子树或右子树都行，但必须保持一致。上面代码让重复值直接返回，这样不会增加节点，但树的高度可能不变。

相关指引

AVL树是平衡树家族中的“严格派”，要求左右子树高度差不超过1。但有时为了插入和删除更快，人们也会用条件宽松一些的平衡树，比如：

  • 红黑树：不严格保持高度差，但保证最长路径不超过最短路径的两倍。C++ STL的map和set就是用红黑树实现的。
  • Treap：结合二叉搜索树和堆的随机化平衡树，用随机优先级决定旋转，代码更短。
  • Splay树：通过“伸展”操作把访问过的节点移到根，适用于有局部性的场景。

如果你对平衡树感兴趣，可以先掌握AVL树，因为它逻辑清晰，能帮你理解旋转的本质。之后学习红黑树或其他变种就会容易很多。另外，AVL树也常用于需要快速插入和删除且对查询性能要求很高的场景，比如数据库索引、内存数据库等。

小练习：试着在上面的代码中添加删除操作（需要处理四种旋转，还要处理有两个孩子的节点）。或者用你的零花钱数目（比如第1天1元，第2天2元……）模拟插入，看看AVL树如何平衡。

例题精讲

1单选题

在AVL树中，若某个节点的平衡因子为2，其左孩子平衡因子为1，则插入新节点后应进行哪种旋转？

ALL单旋转
BLR双旋转
CRL双旋转
DRR单旋转
2判断题

在AVL树中插入一个节点后，最多只需要进行一次旋转即可使树重新平衡。

3填空题
实现AVL树插入时，检测到当前节点平衡因子大于1且新节点键值小于左孩子键值，应执行右旋。补全代码：
if (balance > 1 && key < node->left->key) {
    ___;
}