平衡二叉树（AVL树）

一、什么是平衡二叉树（AVL树）

AVL树是以其发明者 G. M. Adelson-Velsky 和 E. M. Landis（1962年）命名的自平衡二叉搜索树（Self-Balancing Binary Search Tree）。它是计算机科学中最早被发明的自平衡二叉搜索树，也是理解后续各类平衡树（红黑树、B树、Treap等）的基础。

AVL树的定义

一棵AVL树要么是空树，要么是具有以下性质的二叉搜索树：

首先是一棵标准的二叉搜索树（BST）——任意节点的左子树所有节点值均小于该节点值，右子树所有节点值均大于该节点值
任意节点的左子树和右子树的高度差（平衡因子）的绝对值不超过1
任意节点的左子树和右子树也分别是AVL树（递归定义）

AVL树的核心思想是：在每次插入或删除操作之后，通过旋转（Rotation）操作来恢复树的平衡，从而保证树的高度始终维持在 O(log n) 级别。这意味着无论输入数据如何，AVL树的查找、插入、删除操作都能在对数时间内完成，不会退化到链表的 O(n) 复杂度。

为什么需要平衡？

普通的二叉搜索树在极端情况下（如插入已排序的数据）会退化为链表，此时查找时间复杂度从 O(log n) 恶化为 O(n)。AVL树通过强制维持平衡因子在 {-1, 0, 1} 范围内，保证了树的高度始终约为 1.44 * log₂(n)，从而保证了高效的查找性能。

二、平衡因子（Balance Factor）

平衡因子（BF）是衡量节点平衡状态的关键指标，定义如下：

平衡因子 = 左子树高度 - 右子树高度

取值范围：{-1, 0, 1} —— 超出此范围则视为不平衡，需要旋转调整。

树中节点的高度定义为从该节点到最远叶子节点的路径长度（边数），叶子节点的高度为 0，空节点的高度为 -1。

AVL树节点的数据结构

// AVL树节点结构体（C++）
struct AVLNode {
    int key;             // 节点存储的关键字
    AVLNode* left;       // 左孩子指针
    AVLNode* right;      // 右孩子指针
    int height;          // 以当前节点为根的子树高度

    AVLNode(int k) : key(k), left(nullptr), right(nullptr), height(0) {}
};

// 获取节点高度（处理空节点）
int getHeight(AVLNode* node) {
    return node ? node->height : -1;
}

// 计算并返回平衡因子
int getBalanceFactor(AVLNode* node) {
    if (!node) return 0;
    return getHeight(node->left) - getHeight(node->right);
}

// 更新节点的高度值
void updateHeight(AVLNode* node) {
    if (!node) return;
    int leftH  = getHeight(node->left);
    int rightH = getHeight(node->right);
    node->height = 1 + (leftH > rightH ? leftH : rightH);
}

平衡因子的计算是AVL树旋转判断的基础。每当一个节点的高度发生变化（插入或删除后），需要沿路径向上回溯更新所有祖先节点的高度，并检查其平衡因子是否越界。

平衡因子图示

以下是一个平衡的AVL树示例（节点旁标注了平衡因子BF）：

10 (BF=1) / \ 5 (BF=0) 15 (BF=0) / \ / \ 2(BF=0) 7(BF=0) 12(BF=0) 20(BF=0)

上图中所有节点的平衡因子均为 0，这是最理想的情况——树完全平衡。在AVL树中，只要所有节点的平衡因子绝对值不超过1，树就是合法的。

三、AVL树的四种旋转操作

当插入或删除导致某个节点的平衡因子变为 2 或 -2 时，需要通过旋转操作恢复平衡。旋转操作的本质是重新调整子树中节点的父子关系，同时保持二叉搜索树的顺序性质。AVL树的旋转分为四种基本类型：LL（左左）、RR（右右）、LR（左右）、RL（右左）。

1. LL失衡 — 右旋（Right Rotation）

当在某个节点左子树的左子树上插入新节点导致失衡时，称为LL失衡。此时需要执行一次右旋操作。

失衡节点(y) 新根(x) / / \ x =右旋=> T1 y / \ / T1 T2 T2

// 右旋操作 —— 处理LL失衡
// 返回旋转后的新根节点
AVLNode* rotateRight(AVLNode* y) {
    AVLNode* x  = y->left;    // x 将成为新根
    AVLNode* T2 = x->right;   // 暂存T2子树

    // 执行旋转
    x->right = y;
    y->left  = T2;

    // 更新高度（先更新下层节点y，再更新上层节点x）
    updateHeight(y);
    updateHeight(x);

    return x;  // 返回新根
}

2. RR失衡 — 左旋（Left Rotation）

当在某个节点右子树的右子树上插入新节点导致失衡时，称为RR失衡。此时需要执行一次左旋操作。左旋是右旋的镜像操作。

失衡节点(x) 新根(y) \ / \ y =左旋=> x T2 / \ \ T1 T2 T1

// 左旋操作 —— 处理RR失衡
// 返回旋转后的新根节点
AVLNode* rotateLeft(AVLNode* x) {
    AVLNode* y  = x->right;   // y 将成为新根
    AVLNode* T1 = y->left;    // 暂存T1子树

    // 执行旋转
    y->left  = x;
    x->right = T1;

    // 更新高度
    updateHeight(x);
    updateHeight(y);

    return y;  // 返回新根
}

3. LR失衡 — 先左旋后右旋（Left-Right Rotation）

当在某个节点左子树的右子树上插入新节点导致失衡时，称为LR失衡。这是LL和RR的组合情况，需要先对左子树执行左旋（转化为LL情况），再对当前节点执行右旋。

失衡节点(z) 先左旋再右旋 / z new x ====> / ====> / \ / \ new x z T1 new / \ x T3 / \ T1 T2

// LR失衡处理：先左旋左孩子，再右旋当前节点
AVLNode* rotateLR(AVLNode* z) {
    z->left = rotateLeft(z->left);   // 第一步：左旋左子树
    return rotateRight(z);           // 第二步：右旋当前节点
}

4. RL失衡 — 先右旋后左旋（Right-Left Rotation）

当在某个节点右子树的左子树上插入新节点导致失衡时，称为RL失衡。这是RR和LL的组合情况，需要先对右子树执行右旋（转化为RR情况），再对当前节点执行左旋。

// RL失衡处理：先右旋右孩子，再左旋当前节点
AVLNode* rotateRL(AVLNode* z) {
    z->right = rotateRight(z->right);  // 第一步：右旋右子树
    return rotateLeft(z);              // 第二步：左旋当前节点
}

旋转决策速查表

通过平衡因子判断旋转类型：

BF = 2 且左孩子 BF ≥ 0 → LL → 右旋
BF = 2 且左孩子 BF ＜ 0 → LR → 先左旋再右旋
BF = -2 且右孩子 BF ≤ 0 → RR → 左旋
BF = -2 且右孩子 BF ＞ 0 → RL → 先右旋再左旋

四、AVL树的插入操作

AVL树的插入操作分为三个步骤：

标准BST插入：按照二叉搜索树的规则，递归找到合适的位置插入新节点
回溯更新高度：从插入位置沿路径向上，更新每个祖先节点的高度
检查平衡并旋转：对每个祖先节点计算平衡因子，若失衡则执行对应的旋转操作

由于插入操作最坏情况下可能影响从插入节点到根节点路径上的所有节点，因此每次插入后需要沿路径向上回溯，最多执行 O(log n) 次平衡检查。但值得注意的是，AVL树插入导致的失衡最多只需要一次旋转（单旋或双旋）即可恢复整棵树的平衡。

// AVL树插入操作的完整实现
AVLNode* insert(AVLNode* root, int key) {
    // 第1步：标准BST递归插入
    if (!root) {
        return new AVLNode(key);
    }

    if (key < root->key) {
        root->left = insert(root->left, key);
    } else if (key > root->key) {
        root->right = insert(root->right, key);
    } else {
        // 相等键值不重复插入（取决于具体实现策略）
        return root;
    }

    // 第2步：更新当前节点的高度
    updateHeight(root);

    // 第3步：计算平衡因子，判断是否失衡
    int bf = getBalanceFactor(root);

    // 四种失衡情况处理

    // 情况1：LL — 左左失衡
    if (bf > 1 && key < root->left->key) {
        return rotateRight(root);
    }

    // 情况2：RR — 右右失衡
    if (bf < -1 && key > root->right->key) {
        return rotateLeft(root);
    }

    // 情况3：LR — 左右失衡
    if (bf > 1 && key > root->left->key) {
        root->left = rotateLeft(root->left);
        return rotateRight(root);
    }

    // 情况4：RL — 右左失衡
    if (bf < -1 && key < root->right->key) {
        root->right = rotateRight(root->right);
        return rotateLeft(root);
    }

    // 未失衡，直接返回原节点
    return root;
}

上述代码清晰地展示了插入操作的完整流程。判断失衡类型时，结合了当前节点的平衡因子和插入键值与子节点键值的大小关系，从而确定是哪种旋转类型。这种基于比较的判断方式直观且可靠。

五、AVL树的删除操作

AVL树的删除操作比插入稍复杂，但基本思路相同：

标准BST删除：找到目标节点并删除（叶子节点直接删除；单孩子节点用孩子替代；双孩子节点用前驱或后继替代）
回溯更新高度并检查平衡因子
执行旋转恢复平衡

与插入的一个重要区别是：删除操作可能导致多个祖先节点依次失衡，需要向上回溯进行多次旋转（而插入只需要一次旋转即可恢复全局平衡）。因此删除操作的最坏时间复杂度虽然也是 O(log n)，但常数因子比插入更大。

// 查找以root为根的子树中的最小值节点
AVLNode* getMinNode(AVLNode* root) {
    AVLNode* cur = root;
    while (cur->left) {
        cur = cur->left;
    }
    return cur;
}

// AVL树删除操作
AVLNode* erase(AVLNode* root, int key) {
    // 第1步：标准BST删除
    if (!root) return nullptr;

    if (key < root->key) {
        root->left = erase(root->left, key);
    } else if (key > root->key) {
        root->right = erase(root->right, key);
    } else {
        // 找到待删除节点
        if (!root->left || !root->right) {
            // 情况A：0个或1个孩子
            AVLNode* temp = root->left ? root->left : root->right;
            delete root;
            root = temp;  // temp 可能为 nullptr
        } else {
            // 情况B：两个孩子，用后继节点替代
            AVLNode* successor = getMinNode(root->right);
            root->key = successor->key;
            root->right = erase(root->right, successor->key);
        }
    }

    if (!root) return nullptr;  // 树为空

    // 第2步：更新高度
    updateHeight(root);

    // 第3步：检查平衡因子并旋转
    int bf = getBalanceFactor(root);

    // LL
    if (bf > 1 && getBalanceFactor(root->left) >= 0) {
        return rotateRight(root);
    }

    // LR
    if (bf > 1 && getBalanceFactor(root->left) < 0) {
        root->left = rotateLeft(root->left);
        return rotateRight(root);
    }

    // RR
    if (bf < -1 && getBalanceFactor(root->right) <= 0) {
        return rotateLeft(root);
    }

    // RL
    if (bf < -1 && getBalanceFactor(root->right) > 0) {
        root->right = rotateRight(root->right);
        return rotateLeft(root);
    }

    return root;
}

删除操作中判断旋转类型时，使用了子节点的平衡因子而非键值比较，这是因为删除后的键值关系不再直接反映插入路径。这种方法在逻辑上更加通用和稳健。

六、AVL树的其他基本操作

查找操作

AVL树的查找与普通二叉搜索树完全相同，因为旋转操作不会破坏二叉搜索树的有序性。

// 查找指定键值是否存在于AVL树中
bool contains(AVLNode* root, int key) {
    if (!root) return false;
    if (key == root->key) return true;
    if (key < root->key) return contains(root->left, key);
    return contains(root->right, key);
}

// 中序遍历：输出有序序列
void inorderTraversal(AVLNode* root) {
    if (!root) return;
    inorderTraversal(root->left);
    std::cout << root->key << " ";
    inorderTraversal(root->right);
}

验证AVL树的合法性

在实现AVL树时，编写一个验证函数来检查树是否满足AVL性质是非常有用的调试辅助手段。

// 验证以root为根的二叉树是否为合法的AVL树
bool isAVLTree(AVLNode* root) {
    if (!root) return true;

    int bf = getBalanceFactor(root);

    // 检查平衡因子是否越界
    if (bf < -1 || bf > 1) {
        std::cout << "节点 " << root->key
                  << " 平衡因子为 " << bf << "，不平衡！" << std::endl;
        return false;
    }

    // 检查高度值是否正确
    int expectedHeight = 1 + std::max(getHeight(root->left),
                                      getHeight(root->right));
    if (root->height != expectedHeight) {
        std::cout << "节点 " << root->key << " 高度值错误！"
                  << std::endl;
        return false;
    }

    // 递归检查左右子树
    return isAVLTree(root->left) && isAVLTree(root->right);
}

七、时间复杂度分析

AVL树通过维持严格的平衡条件，保证了各种操作在最坏情况下仍具有对数级别的时间复杂度：

操作	平均时间复杂度	最坏时间复杂度
查找（Search）	O(log n)	O(log n)
插入（Insert）	O(log n)	O(log n)
删除（Delete）	O(log n)	O(log n)
获取最大/最小值	O(log n)	O(log n)
中序遍历	O(n)	O(n)

AVL树的高度上界

可以证明，高度为 h 的 AVL 树至少包含 F_h+3 - 1 个节点（其中 F_i 是斐波那契数列）。反过来，包含 n 个节点的 AVL 树的最大高度满足：

h ≤ 1.44 · log₂(n + 2) - 1.33

这意味着 AVL 树的高度永远不会超过最优完全二叉树高度的约 1.44 倍，保证了最坏情况下的查找效率。

相比于普通的二叉搜索树在最坏情况下可能退化为 O(n) 的高度，AVL树的严格平衡特性使其在各种应用场景中都能提供稳定可靠的 O(log n) 性能保证。

八、AVL树 vs 红黑树

AVL树和红黑树都是常用的自平衡二叉搜索树，但二者在平衡策略、性能和适用场景上有显著差异。红黑树通过颜色约束（红黑规则）维持近似平衡，允许左右子树高度差最多相差一倍。

对比维度	AVL树	红黑树
平衡程度	严格平衡（BF ∈ {-1,0,1}）	近似平衡（黑高平衡）
最大高度	≈ 1.44 · log₂(n)	≈ 2 · log₂(n)
查找性能	更优（更矮更平衡）	略差（相对更高）
插入/删除性能	略差（更多旋转）	更优（平均旋转更少）
实现复杂度	中等（旋转逻辑清晰）	较高（颜色维护复杂）
空间开销	每个节点存高度（int）	每个节点存颜色（1 bit）

选型建议

查找密集型应用（字典、数据库索引）→ 选择AVL树，利用其更好的平衡性获得更快查找
插入删除密集型应用（内存分配器、任务调度）→ 选择红黑树，利用其更少的旋转开销
实际工程经验：C++ STL的 std::map 和 std::set 通常使用红黑树实现；而需要频繁查找的场景（如Windows内核某些组件）则采用AVL树

九、AVL树的实际应用

AVL树凭借其严格平衡特性和稳定的查找性能，在众多计算机系统中有广泛的应用：

1. 数据库索引

在内存数据库或需要快速查找的缓存系统中，AVL树可作为索引结构。虽然现代磁盘数据库多采用B/B+树（优化磁盘I/O），但内存数据库中AVL树由于其简单高效的特性仍有广泛应用。

2. 内存中的有序集合

需要维护有序数据且频繁进行范围查询的场景中，AVL树的中序遍历特性使其天然支持高效的顺序访问。例如某些语言的标准库Set/Map实现。

3. 网络路由表

网络设备中需要快速查找最长前缀匹配的路由表项，平衡树结构可用于实现高效的IP路由查找算法。

4. 编译器和解释器

符号表管理、变量作用域追踪等场景中，AVL树可用于快速查找和插入标识符信息。其O(log n)的稳定性能对于编译器的实时性保证非常重要。

5. 事件模拟器

离散事件模拟系统中，事件按时间排序存储在优先队列中。AVL树可以作为高效的事件调度器，支持事件的插入和删除操作。

十、AVL树的完整实现示例

以下是一个完整的AVL树C++实现，包含上述所有操作的统一代码：

#include <iostream>
#include <algorithm>  // for std::max

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

    AVLNode(int k) : key(k), left(nullptr), right(nullptr), height(0) {}
};

class AVLTree {
private:
    AVLNode* root;

    int getHeight(AVLNode* node) {
        return node ? node->height : -1;
    }

    int getBalanceFactor(AVLNode* node) {
        return node ? getHeight(node->left) - getHeight(node->right) : 0;
    }

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

    AVLNode* rotateRight(AVLNode* y) {
        AVLNode* x  = y->left;
        AVLNode* T2 = x->right;
        x->right = y;
        y->left  = T2;
        updateHeight(y);
        updateHeight(x);
        return x;
    }

    AVLNode* rotateLeft(AVLNode* x) {
        AVLNode* y  = x->right;
        AVLNode* T1 = y->left;
        y->left  = x;
        x->right = T1;
        updateHeight(x);
        updateHeight(y);
        return y;
    }

    AVLNode* insert(AVLNode* node, int key) {
        if (!node) return new AVLNode(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 bf = getBalanceFactor(node);

        // LL
        if (bf > 1 && key < node->left->key)
            return rotateRight(node);
        // RR
        if (bf < -1 && key > node->right->key)
            return rotateLeft(node);
        // LR
        if (bf > 1 && key > node->left->key) {
            node->left = rotateLeft(node->left);
            return rotateRight(node);
        }
        // RL
        if (bf < -1 && key < node->right->key) {
            node->right = rotateRight(node->right);
            return rotateLeft(node);
        }
        return node;
    }

    AVLNode* getMinNode(AVLNode* node) {
        AVLNode* cur = node;
        while (cur->left) cur = cur->left;
        return cur;
    }

    AVLNode* erase(AVLNode* node, int key) {
        if (!node) return nullptr;
        if (key < node->key)
            node->left = erase(node->left, key);
        else if (key > node->key)
            node->right = erase(node->right, key);
        else {
            if (!node->left || !node->right) {
                AVLNode* temp = node->left ? node->left : node->right;
                delete node;
                return temp;
            } else {
                AVLNode* successor = getMinNode(node->right);
                node->key = successor->key;
                node->right = erase(node->right, successor->key);
            }
        }
        if (!node) return nullptr;

        updateHeight(node);
        int bf = getBalanceFactor(node);

        // LL
        if (bf > 1 && getBalanceFactor(node->left) >= 0)
            return rotateRight(node);
        // LR
        if (bf > 1 && getBalanceFactor(node->left) < 0) {
            node->left = rotateLeft(node->left);
            return rotateRight(node);
        }
        // RR
        if (bf < -1 && getBalanceFactor(node->right) <= 0)
            return rotateLeft(node);
        // RL
        if (bf < -1 && getBalanceFactor(node->right) > 0) {
            node->right = rotateRight(node->right);
            return rotateLeft(node);
        }
        return node;
    }

    void inorder(AVLNode* node) {
        if (!node) return;
        inorder(node->left);
        std::cout << node->key << " ";
        inorder(node->right);
    }

    void clear(AVLNode* node) {
        if (!node) return;
        clear(node->left);
        clear(node->right);
        delete node;
    }

public:
    AVLTree() : root(nullptr) {}
    ~AVLTree() { clear(root); }

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

    bool contains(int key) {
        AVLNode* cur = root;
        while (cur) {
            if (key == cur->key) return true;
            if (key < cur->key) cur = cur->left;
            else cur = cur->right;
        }
        return false;
    }

    void printInorder() {
        inorder(root);
        std::cout << std::endl;
    }
};

int main() {
    AVLTree tree;

    // 插入测试数据
    int values[] = {10, 20, 30, 40, 50, 25};
    for (int v : values) {
        tree.insert(v);
    }

    // 输出中序遍历结果（应得到有序序列）
    std::cout << "中序遍历: ";
    tree.printInorder();  // 输出: 10 20 25 30 40 50

    // 测试查找
    std::cout << "查找 25: " << (tree.contains(25) ? "找到" : "未找到")
              << std::endl;
    std::cout << "查找 100: " << (tree.contains(100) ? "找到" : "未找到")
              << std::endl;

    // 测试删除
    tree.erase(40);
    std::cout << "删除40后中序遍历: ";
    tree.printInorder();  // 输出: 10 20 25 30 50

    return 0;
}

运行上述程序，将输出以下结果，验证AVL树在各种操作后仍保持正确的有序性和平衡性：

中序遍历: 10 20 25 30 40 50
查找 25: 找到
查找 100: 未找到
删除40后中序遍历: 10 20 25 30 50

十二、进一步思考与练习

进阶思考题

实现迭代版本的AVL树：上述实现使用递归，你能用非递归（栈模拟）的方式实现AVL树的插入和删除吗？迭代版本在某些场景下性能可能更优
AVL树的区间查询：如何高效地查找AVL树中所有落在 [L, R] 范围内的键值？时间复杂度是多少？
并AVL树：如何合并两棵AVL树？如何将一棵AVL树拆分为两棵？这类操作在数据库系统中非常有用
扩展到多维数据：KD-Tree是AVL树的多维推广，你能理解KD-Tree的平衡策略和AVL树的相似之处吗？
性能测量：编写程序对比AVL树、红黑树和std::set在大量随机插入和查找操作下的性能差异，验证理论分析的结论