CC++ & Algorithm

AVL树与旋转操作简介

极难2
语言版本：通用
概述：用叠积木保持稳定的例子引入AVL树，讲解平衡因子、左旋和右旋，以及插入后的四种失衡情况（LL、RR、LR、RL）的调整方法，并给出简化实现代码。

让二叉树保持平衡——AVL树与旋转操作

1 从叠积木说起

你玩过叠积木吗？如果每块积木都正正地叠在下面一块的中心，那么积木塔很稳定。但如果有一块积木偏左太多，塔就会摇晃甚至倒塌。为了保持塔的稳定，我们需要随时调整积木的位置，让它们尽可能左右平衡。

AVL树就像是“自平衡”的积木塔。它在每次插入或删除后，检查每个节点的“倾斜程度”（称为平衡因子），如果某个节点倾斜得太厉害（左右子树高度差超过1），就通过“旋转”操作来扶正它，使整棵树始终保持平衡。AVL树的名字来自它的发明者Adelson-Velsky和Landis。

为什么要这么麻烦？因为普通的二叉搜索树（BST）在最坏情况下会退化成一条直线（比如依次插入1,2,3,4,...），查找和插入的时间就变成了O(n)，和链表一样慢。AVL树通过保持平衡，让树的高度始终接近log₂n，这样所有操作的时间都缩短到O(log n)，就像在有序的字典里翻找一样快。

2 数据结构原理

2.1 平衡因子——怎么判断积木歪了？

AVL树为每个节点定义了一个平衡因子：

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

平衡因子的取值可以是 -1、0 或 1。如果某个节点的平衡因子的绝对值大于1，就说明以该节点为根的子树不平衡，需要进行旋转调整。

生活例子：想象一架天平，左边盘子高度减去右边盘子高度，如果差是2，说明左边太重了（左高右低），需要扶正。

练习题：一个节点左子树高度为3，右子树高度为1，平衡因子是多少？答：2，需要右旋。

2.2 旋转操作——怎么扶正积木？

旋转是改变树结构但保持BST性质的操作。AVL树中有四种旋转情况，分别对应四种失衡类型。

左旋（Left Rotation）：当右子树太重时（平衡因子=-2），需要对节点进行左旋。例如在节点A上左旋：将A的右孩子B提升为根，A变成B的左孩子，B原来的左孩子变成A的右孩子。

左旋示意图

右旋（Right Rotation）：当左子树太重时（平衡因子=2），对节点进行右旋。对称。

左右双旋（Left-Right Rotation）：当左孩子的右子树太重时，先对左孩子左旋，再对当前节点右旋。

右左双旋（Right-Left Rotation）：当右孩子的左子树太重时，先对右孩子右旋，再对当前节点左旋。

记忆口诀：LL（左左）就右旋，RR（右右）就左旋，LR（左右）先左后右，RL（右左）先右后左。

2.3 ASCII示意——用图看清旋转

LL型（左左）：插入节点在左孩子的左子树上，导致A的左子树高度增加。此时对A右旋即可。

        A (bf=2)             B
       / \                  / \
      B   T3    右旋        C   A
     / \       ----->     /   / \
    C   T2               T0   T2 T3
   /
  T0

RR型（右右）：插入节点在右孩子的右子树上，左旋。示意图对称。

LR型（左右）：插入节点在左孩子的右子树上。先左旋左孩子，再右旋当前节点。

      A (bf=2)            A                  C
     / \                / \                / \
    B   T3  左旋B     C   T3   右旋A      B   A
   / \      ----->   / \        ----->   /   / \
  T0  C             B   T2              T0  T2 T3
     / \           / \
    T1  T2        T0 T1

RL型（右左）：插入节点在右孩子的左子树上。先右旋右孩子，再左旋当前节点。对称。

2.4 插入后的调整过程

  1. 按照BST规则插入新节点（比父节点小往左，大往右）。
  2. 沿着插入路径向上回溯，更新每个节点的高度，并计算平衡因子。
  3. 如果遇到某个节点平衡因子绝对值>1，则根据其孩子节点的平衡因子的符号确定旋转类型，执行相应旋转。
  4. 旋转后，子树高度恢复，上层节点也可能需要继续检查，但通常旋转后局部平衡即可。

小提示：回溯是从插入点一路向上到根，因为插入只可能影响路径上节点的平衡。每次旋转后，子树高度会变回平衡状态，所以不需要继续向上检查（但代码中为了安全，通常会继续检查，不过多旋转一次也无妨）。

3 新手最容易犯的错误

  1. 混淆旋转方向：先判断LL还是RR，再决定左旋还是右旋。记住：左子树高就右旋，右子树高就左旋。
  2. 双旋时忘记更新孩子指针：在LR和RL中，第一次旋转后必须把新子树的根赋回给父节点的left或right，否则会丢失。
  3. 高度更新顺序错误：在旋转函数中，必须先更新原根（变成孩子的子树）的高度，再更新新根的高度，因为新根的高度依赖子树的高度。
  4. 忘记处理相等值：AVL树通常不允许重复值（或其他处理方式），如果插入相同值，直接返回原节点即可，否则会导致无限递归。
  5. 平衡因子计算错误：节点为null时，高度为0，平衡因子为0。代码中要小心空指针。

4 C++简化实现

为了教学目的，我们实现一个简化版的AVL树，只实现插入和左旋、右旋。完整AVL代码较长，这里展示核心部分。

#include <iostream>
#include <algorithm> // for max
using namespace std;

struct AVLNode {
    int val;                // 节点存储的值
    AVLNode* left;          // 左孩子指针
    AVLNode* right;         // 右孩子指针
    int height;             // 以该节点为根的子树高度
    AVLNode(int x) : val(x), left(nullptr), right(nullptr), height(1) {}
};

int getHeight(AVLNode* n) {
    return n ? n->height : 0; // 空节点高度为0
}

int getBalance(AVLNode* n) {
    return n ? getHeight(n->left) - getHeight(n->right) : 0;
}

// 更新节点的高度（基于左右孩子的高度）
void updateHeight(AVLNode* n) {
    if (n) 
        n->height = 1 + max(getHeight(n->left), getHeight(n->right));
}

// 右旋（以y为轴，y的左孩子x成为新根）
AVLNode* rightRotate(AVLNode* y) {
    AVLNode* x = y->left;          // x是y的左孩子
    AVLNode* T2 = x->right;        // T2是x的右子树

    // 旋转
    x->right = y;                  // 将y变为x的右孩子
    y->left = T2;                  // 将T2接到y的左孩子

    // 更新高度（先更新y，再更新x，因为y变成了x的子树）
    updateHeight(y);
    updateHeight(x);
    return x; // 新根
}

// 左旋（对称）
AVLNode* leftRotate(AVLNode* x) {
    AVLNode* y = x->right;
    AVLNode* T2 = y->left;

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

    updateHeight(x);
    updateHeight(y);
    return y;
}

// 插入节点（递归实现）
AVLNode* insert(AVLNode* node, int val) {
    // 1. 标准BST插入
    if (node == nullptr) return new AVLNode(val);
    if (val < node->val)
        node->left = insert(node->left, val);
    else if (val > node->val)
        node->right = insert(node->right, val);
    else // 相等值不插入
        return node;

    // 2. 更新当前节点高度
    updateHeight(node);

    // 3. 获取平衡因子，检查是否失衡
    int balance = getBalance(node);

    // 如果失衡，有四种情况

    // LL型：左子树的左子树插入
    if (balance > 1 && val < node->left->val)
        return rightRotate(node);

    // RR型：右子树的右子树插入
    if (balance < -1 && val > node->right->val)
        return leftRotate(node);

    // LR型：左子树的右子树插入，先左旋左孩子，再右旋当前节点
    if (balance > 1 && val > node->left->val) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // RL型：右子树的左子树插入，先右旋右孩子，再左旋当前节点
    if (balance < -1 && val < node->right->val) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node; // 未失衡则直接返回
}

// 中序遍历（用于验证顺序）
void inorder(AVLNode* root) {
    if (root == nullptr) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

int main() {
    AVLNode* root = nullptr;
    // 插入顺序数据，测试AVL是否会退化
    for (int i = 1; i <= 10; ++i) {
        root = insert(root, i);
    }
    cout << "中序遍历: ";
    inorder(root);
    cout << endl;
    cout << "树的高度: " << getHeight(root) << endl; // 应该接近log2(10)≈4
    // 实际运行结果：高度可能是4
    return 0;
}

说明：

  • 每个节点除了值和左右指针，还有height字段，表示以该节点为根的子树高度。
  • getBalance计算平衡因子。
  • rightRotate和leftRotate执行旋转并更新高度。
  • insert递归插入后，回溯检查平衡因子，并根据四种情况进行相应旋转。
  • 注意在LR和RL情况下，需要两次旋转，并且每次旋转后要更新子树的根指针。

5 Python简化实现

class AVLNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1  # 新节点初始高度为1

def get_height(node):
    return node.height if node else 0

def get_balance(node):
    return get_height(node.left) - get_height(node.right) if node else 0

def update_height(node):
    if node:
        node.height = 1 + max(get_height(node.left), get_height(node.right))

def right_rotate(y):
    """右旋"""
    x = y.left
    T2 = x.right

    x.right = y
    y.left = T2

    update_height(y)
    update_height(x)
    return x

def left_rotate(x):
    """左旋"""
    y = x.right
    T2 = y.left

    y.left = x
    x.right = T2

    update_height(x)
    update_height(y)
    return y

def insert(node, val):
    if node is None:
        return AVLNode(val)
    if val < node.val:
        node.left = insert(node.left, val)
    elif val > node.val:
        node.right = insert(node.right, val)
    else:
        return node

    update_height(node)
    balance = get_balance(node)

    # LL
    if balance > 1 and val < node.left.val:
        return right_rotate(node)
    # RR
    if balance < -1 and val > node.right.val:
        return left_rotate(node)
    # LR
    if balance > 1 and val > node.left.val:
        node.left = left_rotate(node.left)
        return right_rotate(node)
    # RL
    if balance < -1 and val < node.right.val:
        node.right = right_rotate(node.right)
        return left_rotate(node)

    return node

def inorder(node):
    if node:
        inorder(node.left)
        print(node.val, end=" ")
        inorder(node.right)

# 测试
root = None
for i in range(1, 11):
    root = insert(root, i)
print("中序遍历:", end=" ")
inorder(root)
print()
print("树的高度:", get_height(root))  # 应为4左右

6 AVL树的性能

  • 查找、插入、删除的时间复杂度都是O(log n)，因为树的高度被严格控制在O(log n)。
  • 代价是每个节点需要额外存储高度（或平衡因子），并且每次插入/删除后可能进行多次旋转旋转（最多O(log n)次）。
  • AVL树适合查找多、插入删除少的场景，因为它对平衡要求严格。

对比生活：AVL树就像严格管理的书架，书必须按大小排列整齐，每层高度差不超过1；而红黑树则宽松一些，允许某些层稍微不齐，但保证最长路径不超过最短路径的两倍。

7 总结要点

  • AVL树通过平衡因子监控每个节点的平衡状态。
  • 当平衡因子绝对值>1时，根据失衡类型（LL、RR、LR、RL）执行相应旋转。
  • 旋转是常数时间操作，能够局部调整子树。
  • 插入后从插入点向上回溯，检查并修复。
  • AVL树保证了严格平衡，但旋转操作相对较多。后来出现的红黑树放松了平衡条件，减少了旋转次数，适用于插入删除频繁的场景。

现在你已经了解了AVL树的基本原理和旋转，下一篇文章将介绍Treap（树堆），它用随机化方法达到平衡，实现更简单。

相关知识点指引

如果你对树形数据结构感兴趣，可以继续学习：

  • 二叉搜索树（BST）：AVL树的基础，理解插入、查找、删除的规则。
  • 红黑树：C++ STL中std::map和std::set的实现，比AVL树平衡条件更宽松，性能更好。
  • B树与B+树：数据库索引常用，多路平衡树，适合磁盘存储。
  • Treap（树堆）：用随机优先级保持平衡，实现简单，性能也不错。
  • Splay树：通过伸展操作将最近访问的节点移到根，适合缓存场景。

动手尝试：在纸上画出插入序列[3,2,1,4,5,6,7]的AVL树构建过程，每一步计算平衡因子并执行旋转，你会彻底掌握AVL树！

例题精讲

1单选题

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

A左旋
B右旋
C左右双旋
D右左双旋
2判断题

AVL树的任何旋转操作都不会改变树的中序遍历顺序。

3填空题
以下为AVL树右旋函数的部分代码，请在最后一行填空：
struct Node* rightRotate(struct Node* y) {
    struct Node* x = y->left;
    struct 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 ___;
}
4单选题

以下哪个不是AVL树旋转操作的标准类型？

A左旋
B右旋
C前旋
D左右双旋
5判断题

在AVL树中，如果某个节点的平衡因子为-2，且其右子节点的平衡因子为1，则需要进行右左双旋。