第21章平衡二叉树(AVL)

课程目录第21章平衡二叉树(AVL)

21. 平衡二叉树（AVL）：从失衡到自愈的艺术

说实话，AVL树是我当年学数据结构时，第一个让我觉得「哇，原来代码还能这么玩」的东西。它不像普通二叉搜索树那样随性，而是带着一种强迫症般的自律——每个节点都要保持左右子树高度差不超过1。嗯，今天我们就来聊聊这个有「洁癖」的树结构。

21.1 AVL树的定义与平衡因子

AVL树，全称是Adelson-Velsky和Landis树（两位苏联数学家）。它本质上还是一棵二叉搜索树，但多了一个硬性条件：任意节点的左右子树高度差不超过1。

这个高度差，我们叫它平衡因子（Balance Factor, BF）。计算公式很简单：

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

平衡因子的取值范围只有三个：-1、0、1。一旦某个节点的平衡因子变成2或-2，就说明这棵树「失衡」了，需要立刻调整。

  核心要点： AVL树本质上就是一棵「时刻保持平衡」的二叉搜索树。平衡因子的绝对值不超过1，是它的生命线。

我在项目中遇到过这样一个场景：用普通二叉搜索树存储用户ID，结果插入顺序恰好是递增的，树直接退化成链表，查询时间复杂度从O(log n)变成了O(n)。那次之后，但凡涉及频繁插入且需要稳定查询性能的场景，我首选AVL树。

21.2 四种旋转：LL、RR、LR、RL

当插入或删除导致某个节点失衡时，我们需要通过旋转来恢复平衡。旋转操作有四种基本形态，但别被名字吓到——说白了就是「把某个节点拎起来，再重新挂好」。

我们先看一个直观的示意图：

四种旋转的命名规则，其实看的是「失衡节点」和「插入位置」的关系：

旋转类型	失衡节点BF	子节点BF	操作
LL（左左）	+2	+1	右旋
RR（右右）	-2	-1	左旋
LR（左右）	+2	-1	先左旋，后右旋
RL（右左）	-2	+1	先右旋，后左旋

我的记忆技巧： LL和RR是「单旋」，LR和RL是「双旋」。名字里第一个字母是失衡节点的方向，第二个字母是插入节点的方向。比如LR，就是左子树的右子树上插入了新节点。

21.3 插入后的平衡调整

AVL树的插入，分三步走：

普通插入：按照二叉搜索树的规则插入新节点
更新高度：从插入节点向上回溯，更新每个祖先节点的高度
检查平衡：如果某个节点的平衡因子变成±2，执行对应的旋转

来看一个完整的插入示例代码：

// AVL树节点定义
typedef struct AVLNode {
    int key;
    int height;
    struct AVLNode *left;
    struct AVLNode *right;
} AVLNode;

// 获取节点高度
int getHeight(AVLNode *node) {
    return node ? node->height : 0;
}

// 计算平衡因子
int getBalance(AVLNode *node) {
    return node ? getHeight(node->left) - getHeight(node->right) : 0;
}

// 右旋（LL情况）
AVLNode* rightRotate(AVLNode *y) {
    AVLNode *x = y->left;
    AVLNode *T2 = x->right;
    
    x->right = y;
    y->left = T2;
    
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    
    return x;
}

// 左旋（RR情况）
AVLNode* leftRotate(AVLNode *x) {
    AVLNode *y = x->right;
    AVLNode *T2 = y->left;
    
    y->left = x;
    x->right = T2;
    
    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    
    return y;
}

// AVL树插入
AVLNode* insert(AVLNode *node, int key) {
    // 1. 普通BST插入
    if (node == NULL) {
        AVLNode *newNode = (AVLNode*)malloc(sizeof(AVLNode));
        newNode->key = key;
        newNode->height = 1;
        newNode->left = newNode->right = NULL;
        return newNode;
    }
    
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else
        return node;  // 重复键，不插入
    
    // 2. 更新高度
    node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
    
    // 3. 检查平衡
    int balance = getBalance(node);
    
    // LL情况
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);
    
    // RR情况
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);
    
    // LR情况
    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    
    // RL情况
    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    
    return node;
}

我曾经踩过的坑： 写旋转代码时，最容易犯的错误是忘记更新旋转后节点的高度。你想想看，高度不对，平衡因子就算错了，后面的旋转全乱套。所以我的习惯是：每次旋转完，立刻更新涉及的两个节点的高度，顺序不能错——先更新子节点，再更新父节点。

21.4 AVL树的删除简介

AVL树的删除，比插入要复杂一些。为什么？因为删除后，失衡可能发生在多个祖先节点上，需要一路回溯检查。

基本流程是这样的：

先按BST的规则删除节点（分三种情况：叶子节点、单子节点、双子节点）
从删除节点的父节点开始，向上回溯，更新每个节点的高度
检查每个节点的平衡因子，如果失衡就旋转

删除和插入最大的区别在于：插入最多只需要一次旋转就能恢复平衡，但删除可能需要多次旋转。因为删除可能让整条路径上的多个节点都失衡。

我个人习惯把删除操作封装成一个递归函数，在递归回溯的过程中做平衡检查。这样代码结构清晰，也不容易漏掉某个节点。

另外，删除时如果遇到双子节点的情况，我建议用「前驱节点」来替换，而不是后继节点。这只是个人偏好，两种方式都可以。

AVL树的删除代码实现，核心逻辑和插入类似，只是多了查找前驱/后继节点的步骤。这里我就不贴完整代码了，你理解了旋转和平衡检查的原理，删除就是多了一层节点查找的逻辑。

AVL树的核心思想，说白了就是「用旋转换平衡」。每次插入或删除后，通过最多O(log n)次旋转，保证树的高度始终是O(log n)。这种「自愈」能力，让它在需要频繁插入删除、同时又要求稳定查询性能的场景下，表现得非常可靠。

嗯，AVL树的内容就到这里。记住四个字：失衡必旋，旋后必衡。

📚 课程目录

21. 平衡二叉树（AVL）：从失衡到自愈的艺术

21.1 AVL树的定义与平衡因子

21.2 四种旋转：LL、RR、LR、RL

21.3 插入后的平衡调整

21.4 AVL树的删除简介