C++平衡二叉树详解（从零实现AVL树：C++数据结构核心教程）

为什么需要平衡？

普通的二叉搜索树在极端情况下（如按顺序插入数据）会退化成链表，导致操作效率从 O(log n) 退化到 O(n)。而 C++数据结构中的 AVL 树通过旋转操作自动维持平衡，确保高效性能。

AVL 树的核心概念

• 平衡因子（Balance Factor）：节点左子树高度减去右子树高度，取值只能是 -1、0 或 1。
• 旋转操作：当插入或删除导致不平衡时，通过左旋、右旋、左右旋或右左旋恢复平衡。

C++ 实现 AVL 树

下面我们逐步实现一个完整的 AVL 树类。

1. 定义节点结构

struct Node {    int key;    Node* left;    Node* right;    int height;    Node(int k) : key(k), left(nullptr), right(nullptr), height(1) {}};

2. 辅助函数：获取高度与更新高度

int getHeight(Node* node) {    if (node == nullptr) return 0;    return node->height;}void updateHeight(Node* node) {    if (node == nullptr) return;    node->height = 1 + std::max(getHeight(node->left), getHeight(node->right));}

3. 旋转操作

// 右旋（用于处理左-左情况）Node* rotateRight(Node* y) {    Node* x = y->left;    Node* T2 = x->right;    x->right = y;    y->left = T2;    updateHeight(y);    updateHeight(x);    return x;}// 左旋（用于处理右-右情况）Node* rotateLeft(Node* x) {    Node* y = x->right;    Node* T2 = y->left;    y->left = x;    x->right = T2;    updateHeight(x);    updateHeight(y);    return y;}

4. 插入函数（含平衡逻辑）

Node* insert(Node* node, int key) {    // 1. 执行标准 BST 插入    if (node == nullptr)        return new Node(key);    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. 更新当前节点高度    updateHeight(node);    // 3. 获取平衡因子    int balance = getHeight(node->left) - getHeight(node->right);    // 4. 如果不平衡，进行旋转    // Left Left Case    if (balance > 1 && key < node->left->key)        return rotateRight(node);    // Right Right Case    if (balance < -1 && key > node->right->key)        return rotateLeft(node);    // Left Right Case    if (balance > 1 && key > node->left->key) {        node->left = rotateLeft(node->left);        return rotateRight(node);    }    // Right Left Case    if (balance < -1 && key < node->right->key) {        node->right = rotateRight(node->right);        return rotateLeft(node);    }    return node;}

完整使用示例

#include #include // 上述所有函数定义...int main() {    Node* root = nullptr;    root = insert(root, 10);    root = insert(root, 20);    root = insert(root, 30); // 触发左旋    root = insert(root, 40);    root = insert(root, 50);    root = insert(root, 25); // 触发左右旋    std::cout << "AVL 树构建完成！根节点为: " << root->key << std::endl;    return 0;}

总结

通过本教程，你已经掌握了如何用 C++ 实现一个完整的 AVL树实现。AVL 树作为经典的自平衡二叉搜索树，是理解更高级数据结构（如红黑树）的基础。希望你能动手实践，加深对 C++平衡二叉树 和 C++数据结构 的理解！

提示：实际项目中可考虑使用 STL 的 std::set 或 std::map（底层通常为红黑树），但理解 AVL 树原理对算法面试和系统设计至关重要。