AVL 树 (Adelson-Velsky and Landis Tree)

AVL 树是历史上最早发明的自平衡二叉搜索树 (Self-Balancing Binary Search Tree)。它通过在每个节点维护子树高度，并在失衡时执行单旋转或双旋转，确保整棵树的高度严格保持在 \(\mathcal{O}(\log n)\) 级别。

---

核心平衡性质

对于 AVL 树中的任意节点 \(u\)，定义其平衡因子 (Balance Factor)：

\[ \text{BF}(u) = \text{height}(\text{left}(u)) - \text{height}(\text{right}(u)) \]

AVL 树的充要平衡条件为：对树中所有节点，其平衡因子只能是 \(-1, 0, 1\)。若某次插入或删除操作导致 \(|\text{BF}(u)| > 1\)，则必须通过旋转操作使之重新平衡。

四种失衡与旋转情形

失衡类型	发生原因	修复操作
LL 型	插入到左孩子的左子树	右单旋（对根节点向右旋转）
RR 型	插入到右孩子的右子树	左单旋（对根节点向左旋转）
LR 型	插入到左孩子的右子树	先左旋再右旋（先对其左孩子左旋，再对根节点右旋）
RL 型	插入到右孩子的左子树	先右旋再左旋（先对其右孩子右旋，再对根节点左旋）

---

完整 C++ 模版实现

支持基础集合操作、查询数值排名、查询第 \(k\) 小、求前驱与后继。

#include <iostream>
#include <algorithm>

template <typename T>
struct AVLTree {
    struct Node {
        T val;
        int height;
        int count; // 相同元素出现频次
        int size;  // 子树节点总数
        Node *left = nullptr;
        Node *right = nullptr;
        Node(T v) : val(v), height(1), count(1), size(1) {}
    };

    Node *root = nullptr;

    int get_height(Node *u) const { return u ? u->height : 0; }
    int get_size(Node *u) const { return u ? u->size : 0; }

    void update(Node *u) {
        if (!u) return;
        u->height = 1 + std::max(get_height(u->left), get_height(u->right));
        u->size = u->count + get_size(u->left) + get_size(u->right);
    }

    int get_balance(Node *u) const {
        return u ? get_height(u->left) - get_height(u->right) : 0;
    }

    // 右单旋 (LL)
    Node* rotate_right(Node *y) {
        Node *x = y->left;
        Node *T2 = x->right;
        x->right = y;
        y->left = T2;
        update(y);
        update(x);
        return x;
    }

    // 左单旋 (RR)
    Node* rotate_left(Node *x) {
        Node *y = x->right;
        Node *T2 = y->left;
        y->left = x;
        x->right = T2;
        update(x);
        update(y);
        return y;
    }

    Node* rebalance(Node *u) {
        update(u);
        int bf = get_balance(u);

        // LL
        if (bf > 1 && get_balance(u->left) >= 0) {
            return rotate_right(u);
        }
        // LR
        if (bf > 1 && get_balance(u->left) < 0) {
            u->left = rotate_left(u->left);
            return rotate_right(u);
        }
        // RR
        if (bf < -1 && get_balance(u->right) <= 0) {
            return rotate_left(u);
        }
        // RL
        if (bf < -1 && get_balance(u->right) > 0) {
            u->right = rotate_right(u->right);
            return rotate_left(u);
        }
        return u;
    }

    Node* insert(Node *u, T val) {
        if (!u) return new Node(val);
        if (val == u->val) {
            u->count++;
            u->size++;
            return u;
        }
        if (val < u->val) u->left = insert(u->left, val);
        else u->right = insert(u->right, val);
        return rebalance(u);
    }

    Node* get_min_node(Node *u) {
        while (u && u->left) u = u->left;
        return u;
    }

    Node* erase(Node *u, T val) {
        if (!u) return nullptr;
        if (val < u->val) {
            u->left = erase(u->left, val);
        } else if (val > u->val) {
            u->right = erase(u->right, val);
        } else {
            if (u->count > 1) {
                u->count--;
                u->size--;
                return u;
            }
            if (!u->left || !u->right) {
                Node *temp = u->left ? u->left : u->right;
                delete u;
                return temp;
            } else {
                Node *temp = get_min_node(u->right);
                u->val = temp->val;
                u->count = temp->count;
                temp->count = 1; // 确保只删 1 次
                u->right = erase(u->right, temp->val);
            }
        }
        return rebalance(u);
    }

    // 常用对外接口
    void insert(T val) { root = insert(root, val); }
    void erase(T val) { root = erase(root, val); }

    // 查询小于 val 的元素个数 + 1 (1-indexed 排名)
    int rank(T val) {
        Node *cur = root;
        int rk = 1;
        while (cur) {
            if (val <= cur->val) {
                cur = cur->left;
            } else {
                rk += get_size(cur->left) + cur->count;
                cur = cur->right;
            }
        }
        return rk;
    }

    // 查询排名第 k 的元素 (1-indexed)
    T kth(int k) {
        Node *cur = root;
        while (cur) {
            int left_sz = get_size(cur->left);
            if (k <= left_sz) {
                cur = cur->left;
            } else if (k <= left_sz + cur->count) {
                return cur->val;
            } else {
                k -= left_sz + cur->count;
                cur = cur->right;
            }
        }
        return T();
    }

    // 前驱：小于 val 的最大元素
    T prev(T val) {
        Node *cur = root;
        T ans = T();
        while (cur) {
            if (cur->val < val) {
                ans = cur->val;
                cur = cur->right;
            } else {
                cur = cur->left;
            }
        }
        return ans;
    }

    // 后继：大于 val 的最小元素
    T next(T val) {
        Node *cur = root;
        T ans = T();
        while (cur) {
            if (cur->val > val) {
                ans = cur->val;
                cur = cur->left;
            } else {
                cur = cur->right;
            }
        }
        return ans;
    }
};

---

复杂度与竞赛评价

• 时间复杂度：
• 查找、插入、删除、求 Rank、求第 \(k\) 小均为严格 \(\mathcal{O}(\log n)\)。
• 由于 AVL 树的平衡条件比红黑树更严格，其查找速度通常比红黑树更快（树高平均减少约 10%~15%），但插入/删除时维护平衡旋转的开销略大。
• 空间复杂度：\(\mathcal{O}(n)\)。