平衡二叉树（Balanced Binary Tree）介绍

平衡二叉树（Balanced Binary Tree）是一种特殊的二叉搜索树（BST），它在 插入、删除操作后仍能保持高度平衡，从而保证查找、插入、删除的时间复杂度为 O(log n)。

1. 为什么需要平衡二叉树？

普通二叉搜索树（BST）的问题：

最坏情况下可能退化为链表，导致查找效率从 O(log n) 变为 O(n)。
例如，对于以下

有序插入的情况：
```
1
 \
  2
   \
    3
     \
      4
```
这里的 BST 退化成了一条单链表，查找效率大大降低。

平衡二叉树的目标：

保证 任意节点的左右子树高度差不超过一定范围，确保树的高度保持在 O(log n)，从而提高查找效率。

2. 常见的平衡二叉树类型

(1) AVL 树

特点：

AVL 树是 最早提出的自平衡二叉搜索树（1962 年）。
任何节点的 左右子树高度差不超过 1。
通过 旋转（左旋、右旋、双旋） 保持平衡。

缺点：

插入和删除时的 调整次数较多，维护成本较高。
适用于 查找较多，插入/删除较少的场景（如数据库索引）。

(2) 红黑树（Red-Black Tree）

特点：

每个节点要么是红色，要么是黑色。
通过颜色变化+旋转维持平衡，保证最长路径不超过最短路径的 2 倍。
适用于 插入、删除频繁 的场景（如 STL 的 map、set）。

对比 AVL 树：

AVL 树查找更快（更严格平衡），但插入/删除调整较多。
红黑树插入/删除更快，适用于动态数据结构。

(3) Treap（树堆）

特点：

结合了二叉搜索树（BST）和堆（Heap）的特性：
- BST：按照键值（key）排序，左子树 < 根 < 右子树。
- 堆：按照优先级（priority）排序，父节点优先级高于子节点。
插入时随机分配 优先级，通过旋转维持平衡。

优点：

实现简单，适用于 随机化数据结构，常用于 竞赛和高效算法。

(4) Splay 树

特点：

自调整二叉搜索树：每次访问某个节点时，会通过旋转使该节点成为根。
访问频繁的节点会更接近根，提高局部查找速度（自适应特性）。

应用场景：

缓存系统（LRU 实现）、字符串搜索（如 Rope 数据结构）。

3. AVL 树的实现

AVL 树的核心操作：

旋转操作（保持平衡）：
- 左旋（Left Rotation）
- 右旋（Right Rotation）
- 左右双旋（Left-Right Rotation）
- 右左双旋（Right-Left Rotation）
插入操作：
- 插入后，可能导致不平衡，需要 旋转恢复平衡。
删除操作：
- 删除节点后，也可能导致不平衡，需要 旋转恢复平衡。

C++ AVL 树实现

#include <iostream>

using namespace std;

struct Node {
    int key;
    int height;
    Node* left;
    Node* right;

    Node(int val) : key(val), height(1), left(nullptr), right(nullptr) {}
};

class AVLTree {
private:
    Node* root;

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

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

    // 更新高度
    void updateHeight(Node* node) {
        node->height = 1 + max(getHeight(node->left), getHeight(node->right));
    }

    // 左旋
    Node* leftRotate(Node* x) {
        Node* y = x->right;
        x->right = y->left;
        y->left = x;
        updateHeight(x);
        updateHeight(y);
        return y;
    }

    // 右旋
    Node* rightRotate(Node* y) {
        Node* x = y->left;
        y->left = x->right;
        x->right = y;
        updateHeight(y);
        updateHeight(x);
        return x;
    }

    // 插入节点
    Node* insert(Node* node, int key) {
        if (!node) 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;

        updateHeight(node);

        // 平衡因子
        int balance = getBalanceFactor(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;
    }

    // 中序遍历
    void inorder(Node* node) {
        if (!node) return;
        inorder(node->left);
        cout << node->key << " ";
        inorder(node->right);
    }

public:
    AVLTree() : root(nullptr) {}

    void insert(int key) {
        root = insert(root, key);
    }

    void display() {
        inorder(root);
        cout << endl;
    }
};

int main() {
    AVLTree tree;
    tree.insert(10);
    tree.insert(20);
    tree.insert(30);
    tree.insert(25);
    tree.insert(5);
    tree.insert(15);

    tree.display();
    return 0;
}