AVL树从零实现（C++语言详解AVL树的插入、旋转与平衡机制）

AVL树的核心：四种旋转操作

当插入或删除节点导致某节点的平衡因子超出 [-1, 1] 范围时，就需要通过旋转来恢复平衡。共有四种情况：

1. 右右（RR）情况 → 左旋（Left Rotation）
2. 左左（LL）情况 → 右旋（Right Rotation）
3. 左右（LR）情况 → 先左旋再右旋
4. 右左（RL）情况 → 先右旋再左旋

C++实现AVL树

1. 定义AVL节点结构

struct AVLNode {    int data;    AVLNode* left;    AVLNode* right;    int height; // 节点高度    AVLNode(int val) : data(val), left(nullptr), right(nullptr), height(1) {}};

2. 辅助函数：获取高度与计算平衡因子

int getHeight(AVLNode* node) {    if (node == nullptr) return 0;    return node->height;}int getBalanceFactor(AVLNode* node) {    if (node == nullptr) return 0;    return getHeight(node->left) - getHeight(node->right);}

3. 实现四种旋转

// 右旋（用于LL情况）AVLNode* rotateRight(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* rotateLeft(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; // 新的根节点}

4. 插入节点并自动平衡

AVLNode* insert(AVLNode* node, int key) {    // 1. 执行标准BST插入    if (node == nullptr)        return new AVLNode(key);    if (key < node->data)        node->left = insert(node->left, key);    else if (key > node->data)        node->right = insert(node->right, key);    else        return node; // 不允许重复值    // 2. 更新当前节点高度    node->height = 1 + max(getHeight(node->left), getHeight(node->right));    // 3. 获取平衡因子    int balance = getBalanceFactor(node);    // 4. 如果不平衡，进行旋转    // Left Left Case    if (balance > 1 && key < node->left->data)        return rotateRight(node);    // Right Right Case    if (balance < -1 && key > node->right->data)        return rotateLeft(node);    // Left Right Case    if (balance > 1 && key > node->left->data) {        node->left = rotateLeft(node->left);        return rotateRight(node);    }    // Right Left Case    if (balance < -1 && key < node->right->data) {        node->right = rotateRight(node->right);        return rotateLeft(node);    }    // 无需旋转，返回原节点    return node;}

总结

通过以上步骤，你已经掌握了如何用 C++ 实现 AVL 树。AVL树作为经典的自平衡二叉树结构，在数据库索引、内存管理等领域有广泛应用。理解其旋转机制是掌握高级数据结构的关键一步。

记住四个关键词：AVL树实现、C++ AVL树、平衡二叉搜索树、自平衡二叉树——它们不仅是面试高频考点，也是构建高效程序的基础。

建议你动手编写完整代码，并测试各种插入顺序，观察树如何自动保持平衡。实践出真知！