适用人群：数据结构初学者、期末备考、面试刷题零基础同学

核心优势：无晦涩公式、全程图文拆解、每个操作单独讲解、C++代码全覆盖+逐段注释、重点标注，看完彻底掌握AVL树

一、前置知识：为什么需要AVL树？（BST的致命缺陷）

1.1 二叉搜索树（BST）核心规则

普通二叉搜索树必须满足三个条件：

• 任意节点的左子树所有节点值 < 当前节点值

• 任意节点的右子树所有节点值 > 当前节点值

• 左右子树也必须是合法的二叉搜索树

1.2 BST 最大痛点：退化成链表

如果我们插入有序数据（1,2,3,4,5,6），普通BST会彻底失衡，变成一条斜链：

此时树的查询、插入、删除时间复杂度，从理想的 O(logn) 暴跌为 O(n)，完全失去树形结构的高效优势。

AVL树的诞生目的：在保留BST左小右大特性的前提下，强制树保持平衡，杜绝斜链问题，保证操作效率永久稳定在 O(logn)。

二、AVL树核心基础概念

2.1 AVL树完整定义

AVL树是最早的自平衡二叉搜索树，同时满足两个核心条件：

1. 是合法的二叉搜索树（左小右大）

2. 任意节点的左右子树高度差绝对值不超过 1

2.2 节点高度（必懂基础）

行业统一约定规则：

• 空节点（nullptr）高度 = 0

• 叶子节点（无左右孩子）高度 = 1

• 普通节点高度公式：max(左子树高度, 右子树高度) + 1

2.3 平衡因子（AVL树的灵魂）

计算公式：平衡因子 = 左子树高度 - 右子树高度

AVL树铁律：所有节点平衡因子只能是 -1、0、1

• BF = 1：左子树偏高

• BF = 0：左右子树等高（最平衡）

• BF = -1：右子树偏高

只要 |BF| > 1（等于2或-2），树判定为失衡，必须通过旋转操作修复平衡。

三、四大失衡场景 + 逐一手绘图解

所有AVL树失衡，只会出现 LL、RR、LR、RL 四种情况，对应固定旋转方案，无例外！

旋转核心原则：不破坏BST左小右大规则，仅调整节点位置，修复高度平衡。

3.1 LL 左左失衡（单次右旋）

触发条件：在「根节点左子树的左子树」插入节点，导致根节点BF=2

失衡结构：

修复方案：右旋操作

操作步骤：

1. 将左孩子Y提升为新根节点

2. 把Y原本的右子树，挂载到Z的左孩子位置

3. 原根Z变为Y的右子树

4. 更新所有受影响节点的高度

平衡后结构：

3.2 RR 右右失衡（单次左旋）

触发条件：在「根节点右子树的右子树」插入节点，导致根节点BF=-2

失衡结构：

修复方案：左旋操作

操作步骤：

1. 将右孩子Y提升为新根节点

2. 把Y原本的左子树，挂载到Z的右孩子位置

3. 原根Z变为Y的左子树

4. 更新节点高度

平衡后结构：

3.3 LR 左右失衡（先左旋、后右旋）

触发条件：在「根节点左子树的右子树」插入节点，交叉型失衡，根节点BF=2

失衡结构：

修复方案：两次旋转

1. 第一步：对左子树Y做左旋，将结构转为LL型失衡

2. 第二步：对根节点Z做右旋，彻底修复平衡

最终平衡结构：

3.4 RL 右左失衡（先右旋、后左旋）

触发条件：在「根节点右子树的左子树」插入节点，交叉型失衡，根节点BF=-2

失衡结构：

修复方案：两次旋转

1. 第一步：对右子树Y做右旋，将结构转为RR型失衡

2. 第二步：对根节点Z做左旋，修复平衡

最终平衡结构：

3.5 旋转速记口诀（必背）

• LL 左左失衡 → 单次右旋

• RR 右右失衡 →单次左旋

• LR 左右失衡 → 先左后右双旋

• RL 右左失衡 → 先右后左双旋

四、C++ 完整AVL树实现

代码包含：节点定义、高度计算、平衡因子、四大旋转、节点插入、节点删除、中序遍历，兼容所有C++编译器，无报错、可直接编译运行。

#include <iostream>
#include <algorithm>
using namespace std;

// AVL树节点结构定义
struct Node
{
    int val;         // 节点存储数值
    Node* left;      // 左孩子指针
    Node* right;     // 右孩子指针
    int height;      // 节点高度

    // 构造函数：新建节点默认高度为1（叶子节点）
    Node(int v) : val(v), left(nullptr), right(nullptr), height(1) {}
};

// 获取节点高度（空节点高度为0）
int getHeight(Node* node)
{
    if (node == nullptr)
        return 0;
    return node->height;
}

// 计算节点平衡因子
int getBalance(Node* node)
{
    if (node == nullptr)
        return 0;
    return getHeight(node->left) - getHeight(node->right);
}

// 左旋操作：解决RR型失衡
Node* leftRotate(Node* root)
{
    Node* newRoot = root->right;
    Node* temp = newRoot->left;

    // 执行左旋
    newRoot->left = root;
    root->right = temp;

    // 更新高度：先子节点、后父节点
    root->height = 1 + max(getHeight(root->left), getHeight(root->right));
    newRoot->height = 1 + max(getHeight(newRoot->left), getHeight(newRoot->right));

    return newRoot;
}

// 右旋操作：解决LL型失衡
Node* rightRotate(Node* root)
{
    Node* newRoot = root->left;
    Node* temp = newRoot->right;

    // 执行右旋
    newRoot->right = root;
    root->left = temp;

    // 更新高度
    root->height = 1 + max(getHeight(root->left), getHeight(root->right));
    newRoot->height = 1 + max(getHeight(newRoot->left), getHeight(newRoot->right));

    return newRoot;
}

// AVL树插入节点（自动平衡）
Node* insert(Node* root, int val)
{
    // 递归终止：创建新节点
    if (root == nullptr)
        return new Node(val);

    // 1. 标准BST插入逻辑
    if (val < root->val)
        root->left = insert(root->left, val);
    else if (val > root->val)
        root->right = insert(root->right, val);
    else
        return root; // 不允许重复节点

    // 2. 更新当前节点高度
    root->height = 1 + max(getHeight(root->left), getHeight(root->right));

    // 3. 判断失衡并修复
    int balance = getBalance(root);

    // LL失衡
    if (balance > 1 && val < root->left->val)
        return rightRotate(root);

    // RR失衡
    if (balance < -1 && val > root->right->val)
        return leftRotate(root);

    // LR失衡
    if (balance > 1 && val > root->left->val)
    {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    // RL失衡
    if (balance < -1 && val < root->right->val)
    {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    return root;
}

// 辅助函数：寻找子树最小节点（删除专用）
Node* minValueNode(Node* node)
{
    Node* cur = node;
    while (cur->left != nullptr)
        cur = cur->left;
    return cur;
}

// AVL树删除节点（删除后自动平衡）
Node* deleteNode(Node* root, int val)
{
    if (root == nullptr)
        return root;

    // 1. 标准BST删除查找
    if (val < root->val)
        root->left = deleteNode(root->left, val);
    else if (val > root->val)
        root->right = deleteNode(root->right, val);
    else
    {
        // 情况1：单个子节点或叶子节点
        if (root->left == nullptr || root->right == nullptr)
        {
            Node* temp = root->left ? root->left : root->right;
            if (temp == nullptr)
            {
                temp = root;
                root = nullptr;
            }
            else
                *root = *temp;
            delete temp;
        }
        // 情况2：存在左右两个子节点
        else
        {
            Node* temp = minValueNode(root->right);
            root->val = temp->val;
            root->right = deleteNode(root->right, temp->val);
        }
    }

    if (root == nullptr)
        return root;

    // 2. 更新高度
    root->height = 1 + max(getHeight(root->left), getHeight(root->right));

    // 3. 修复删除后的失衡
    int balance = getBalance(root);

    if (balance > 1 && getBalance(root->left) >= 0)
        return rightRotate(root);
    if (balance > 1 && getBalance(root->left) < 0)
    {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    if (balance < -1 && getBalance(root->right) <= 0)
        return leftRotate(root);
    if (balance < -1 && getBalance(root->right) > 0)
    {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    return root;
}

// 中序遍历：验证AVL树（结果一定升序）
void inOrder(Node* root)
{
    if (root == nullptr)
        return;
    inOrder(root->left);
    cout << root->val << " ";
    inOrder(root->right);
}

// 主函数测试
int main()
{
    Node* root = nullptr;

    // 批量插入测试数据
    int arr[] = {10, 20, 30, 40, 50, 25};
    int n = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < n; i++)
        root = insert(root, arr[i]);

    cout << "插入数据后AVL树中序遍历：";
    inOrder(root);
    cout << endl;

    // 测试删除节点
    root = deleteNode(root, 30);
    cout << "删除30后AVL树中序遍历：";
    inOrder(root);
    cout << endl;

    return 0;
}

五、代码运行结果

插入数据后AVL树中序遍历：10 20 25 30 40 50 删除30后AVL树中序遍历：10 20 25 40 50 

结果为严格升序，证明BST特性完好，且全程无失衡，平衡修复生效！

六、初学者核心重点&易错点总结

6.1 核心考点

• AVL树是高度平衡的BST，高度差≤1，效率稳定O(logn)

• 平衡因子合法值：-1、0、1，超差必旋转

• 四种失衡对应固定旋转方式，无其他情况

6.2 高频易错点

• 旋转操作后必须更新节点高度（90%新手出错点）

• 高度更新顺序：先下层子节点，后上层父节点

• 删除节点比插入更容易失衡，必须全覆盖四种平衡判断

• AVL树中序遍历一定是升序，可用于验证代码正确性