C++ AVL树详解（从零实现平衡二叉搜索树的完整教程）

AVL树的基本操作

AVL树支持以下基本操作：

• 插入（Insert）
• 删除（Delete）
• 查找（Search）
• 获取高度（Get Height）
• 旋转（Rotate）：左旋、右旋、左右旋、右左旋

C++ 实现 AVL 树

下面是一个完整的 C++ 平衡二叉树（AVL树）实现。我们将使用类封装，并详细注释每一步逻辑。

// AVLTree.h#include <iostream>#include <algorithm>class AVLNode {public:    int data;    AVLNode* left;    AVLNode* right;    int height;    AVLNode(int val) : data(val), left(nullptr), right(nullptr), height(1) {}};class AVLTree {private:    AVLNode* root;    int getHeight(AVLNode* node) {        if (!node) return 0;        return node->height;    }    int getBalanceFactor(AVLNode* node) {        if (!node) return 0;        return getHeight(node->left) - getHeight(node->right);    }    AVLNode* rotateRight(AVLNode* y) {        AVLNode* x = y->left;        AVLNode* T2 = x->right;        x->right = y;        y->left = T2;        y->height = std::max(getHeight(y->left), getHeight(y->right)) + 1;        x->height = std::max(getHeight(x->left), getHeight(x->right)) + 1;        return x;    }    AVLNode* rotateLeft(AVLNode* x) {        AVLNode* y = x->right;        AVLNode* T2 = y->left;        y->left = x;        x->right = T2;        x->height = std::max(getHeight(x->left), getHeight(x->right)) + 1;        y->height = std::max(getHeight(y->left), getHeight(y->right)) + 1;        return y;    }    AVLNode* insertHelper(AVLNode* node, int key) {        // 1. 执行标准BST插入        if (!node) return new AVLNode(key);        if (key < node->data)            node->left = insertHelper(node->left, key);        else if (key > node->data)            node->right = insertHelper(node->right, key);        else            return node; // 不允许重复值        // 2. 更新当前节点的高度        node->height = 1 + std::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;    }    void inorderHelper(AVLNode* node) {        if (node) {            inorderHelper(node->left);            std::cout << node->data << " ";            inorderHelper(node->right);        }    }public:    AVLTree() : root(nullptr) {}    void insert(int key) {        root = insertHelper(root, key);    }    void inorder() {        inorderHelper(root);        std::cout << std::endl;    }};

使用示例：AVL树应用实例

现在我们来测试这个AVL树。以下代码演示了如何插入一系列数字并输出中序遍历结果（应为有序序列）：

int main() {    AVLTree tree;    tree.insert(10);    tree.insert(20);    tree.insert(30); // 触发左旋    tree.insert(40);    tree.insert(50);    tree.insert(25); // 触发左右旋    std::cout << "中序遍历结果: ";    tree.inorder(); // 输出: 10 20 25 30 40 50    return 0;}

运行此程序，你会发现无论插入顺序如何，AVL树始终维持平衡，确保高效操作。这就是 AVL树应用实例 的典型场景——适用于需要频繁插入/查找且要求稳定性能的系统，如数据库索引、内存管理等。

总结

通过本教程，你已经掌握了 C++ AVL树 的基本原理、旋转机制和完整实现。虽然代码看起来有点复杂，但只要理解四种旋转情形和平衡因子的计算，就能轻松驾驭这种强大的数据结构。

记住，C++平衡二叉树（如AVL树）是面试和实际开发中的高频考点与实用工具。多加练习，你一定能熟练运用！

希望这篇关于 AVL树实现 的教程对你有帮助。欢迎动手实践并尝试扩展删除功能！