AVL 树原理与 C++ 实现：构建自平衡二叉搜索树

AVL 树概念

起源与定义

AVL 树是最早被发明的平衡二叉搜索树。它是一颗空树，或者满足以下性质的二叉搜索树：左右子树均为 AVL 树，且左右子树的高度差绝对值不超过 1。

这种结构通过严格控制高度来维持平衡。虽然 AVL 树无法像红黑树那样作为数据库存储索引的首选（因为旋转开销较大），但在对查找性能要求极高且插入频率适中的场景下，它依然非常有效。AVL 树遵循二叉搜索树的基本性质：根节点大于左子树所有节点，小于右子树所有节点。

AVL 树得名于其发明者 G. M. Adelson-Velsky 和 E. M. Landis，他们在 1962 年的论文《An algorithm for the organization of information》中首次提出了这一概念。

平衡因子

为了判断树是否平衡，我们需要引入平衡因子的概念。在 AVL 树中，每个节点的平衡因子定义为：

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

若一棵二叉搜索树是平衡的，则任意节点的平衡因子只能是 -1、0 或 1。如果某个节点的平衡因子绝对值超过 1，说明该节点失衡，需要通过旋转操作进行调整。

为什么允许 -1 或 1？

有些读者可能会疑惑，既然追求平衡，为何不强制平衡因子为 0？这是因为 AVL 树的设计目标是保持整体平衡，而非局部完美对称。当插入节点数为偶数时，很难保证每个节点的左右子树高度完全一致。允许平衡因子为 -1 或 1，能在保持树高 O(log n) 的同时，减少不必要的旋转操作，提升效率。

AVL 树实现准备

节点结构设计

实现 AVL 树的第一步是定义节点结构。由于后续需要频繁进行键值对操作，我们通常使用 std::pair 来存储数据。此外，AVL 树属于三叉链表结构，除了左孩子和右孩子指针外，还需要一个指向父节点的指针。

存储父节点指针的主要原因是为了在旋转操作后，能够方便地向上回溯并更新平衡因子，避免每次都需要重新遍历整棵树来计算高度。

struct Node {
    std::pair<int, int> data; // 键值对
    int height;               // 节点高度
    int balanceFactor;        // 平衡因子
    Node* left;               // 左子节点
    Node* right;              // 右子节点
    Node* parent;             // 父节点
};

在实际编码中，我们可以将高度和平衡因子合并计算，但显式存储能简化逻辑。接下来我们将讨论如何在插入和删除操作中维护这些属性。