C++ 实现 AVL 平衡二叉搜索树

• AVL 树是最早发明的自平衡二叉搜索树
  • 当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过 1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
• AVL 树是在普通二叉搜索树的基础上增加了平衡条件，确保树始终保持近似平衡状态
• AVL 树要么是空树，要么是满足以下性质的二叉搜索树：
  • 其左、右子树也都是 AVL 树
  • 左、右子树高度之差 (简称平衡因子) 的绝对值不超过 1

如果一棵二叉搜索树是高度平衡的，它就是 AVL 树。如果它有 n 个结点，其高度可保持在 O(log2 n)，搜索时间复杂度O(log2 n)

平衡因子

AVL 树是一颗高度平衡的搜索二叉树，通过控制高度差去控制平衡

AVL 树可以始终保持平衡状态，是因为在实现 AVL 树时，我们引入了 平衡因子（balance factor） 的概念：

每个节点都有一个平衡因子，其值等于该节点右子树的高度减去左子树的高度

• 因此：任何节点的平衡因子只能是 0、1 或 -1

当然平衡因子并非 AVL 树的必需属性，因为AVL 树的维持平衡不一定需要平衡因子，也可以动态计算高度或其他方法使 AVL 树保持平衡

• 使用平衡因子实现只是实现平衡的其中一种方式

但平衡因子如同一个 '风向标'：

• 可以更方便我们去观察和控制树是否平衡
• 高效控制树的平衡维护过程 —— 通过判断平衡因子是否超出 [-1, 1] 范围
• 可快速定位需要调整的节点，进而通过旋转操作恢复树的平衡

以下就是一颗 AVL 树，同时附有相应的平衡因子

而下面这棵树就不是一棵 AVL 树，因为 10 这个节点它的左右子树的高度差超过了 1

基本性质

核心特点：

• 高度近似平衡：AVL 树通过不断调整树的结构，保证树的左右子树高度差始终在允许范围内，使得树的高度相对较低。
  • 例如：在插入或删除节点后，会通过旋转操作（左旋、右旋、左右双旋、右左双旋）来重新平衡树，从而维持高度平衡。
• 查找效率稳定：
  • 由于 AVL 树高度平衡，其高度近似于 O(log N)，其中 n 是节点数量，这意味着在 AVL 树中进行查找操作时，时间复杂度稳定在 O(log N)
  • 相比于普通二叉搜索树在最坏情况下可能退化为链表，查找时间复杂度为 O(n)，AVL 树查找效率更高且稳定

基本操作：

• 插入：
  • 新节点插入后，从插入节点开始向上检查祖先节点的平衡因子。如果发现某个节点的平衡因子绝对值超过 1，就需要进行旋转操作来恢复平衡。
• 查找：
  • 按照普通二叉搜索树的查找逻辑查找，时间复杂度为 O(log N)

优缺比较：

• 优点：查找效率高且稳定，时间复杂度为 O(log N)，适用于对查找效率要求较高，且插入和删除操作相对不太频繁的场景。
• 缺点：每次插入和删除操作都可能需要进行旋转来维持平衡，这会增加额外的计算开销，导致插入和删除操作的时间复杂度比普通二叉搜索树要高一些。

为什么 AVL 树不要求左右子树的高度为 0 呢？

为什么AVL 树要求左右子树的高度差不超过 1，而非必须为 0 呢？

从平衡的理想状态看，高度差为 0 确实更平衡，但实际情况中，部分树的结构无法满足这一要求：

• 当树的节点数为 2、4 ……等特定数量时，最优的高度差只能是 1，无法强制达到 0
• 这说明 AVL 树的平衡条件是在 '绝对平衡' 和 '实现可行性' 之间的权衡设计

3. AVL 树的实现

整体架构设计

AVL 树的结点定义

• AVL 树为模版实现

template<class K, class V>
struct AVLTreeNode {
    pair<K, V> _kv; // 键值对
    // 三叉链
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent; // 插入结点后，需要更新平衡因子，有了_parent，可以很方便的找父节点
    int _balanceFactor; // balance factor 平衡因子，用于判断当前子树 有没有出现不平衡的问题

    // Node 结点 的构造函数
    AVLTreeNode(const pair<K, V>& kv) :
        _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _balanceFactor(0) // 新结点 初始的平衡因子为 0
    {}
};

• 搜索树常用于存储键值，方便查找关键字，这里我们使用 std::pair<K, V> 来存储我们的键值对
• 结点中的成员变量：采用三叉链的方式实现
  • AVLTreeNode<K, V>* _left：指向左孩子的指针
  • AVLTreeNode<K, V>* _right：指向右孩子的指针
  • AVLTreeNode<K, V>* _parent：指向父节点的指针
    • 插入结点后，需要更新平衡因子，有了 _parent，可以很方便的找父节点
  • int _balanceFactor：平衡因子，用于判断当前子树 有没有出现不平衡的问题
• 默认构造函数 AVLTreeNode(const pair<K, V>& kv)：
  • 将三个指针初始化为 nullptr，初始化平衡因子为 0
  • 使用 kv 初始化类内的 _kv 成员
• 结点采用 struct 设计，默认权限为 public，方便下文的 AVLTree 类访问成员

AVL 树设计

• 我们采用的设计：左右子树高度之差的绝对值 小于等于 1 (-1 0 1)
• 方便起见：我们使用 平衡因子 == 右子树的高度 - 左子树的高度

template<class K, class V>
class AVLTree {
    typedef AVLTreeNode<K, V> Node;
private:
    AVLTreeNode<K, V>* _root = nullptr;
public:
    // ... 对外共有接口
private:
    // ... 内部私有成员函数
};

• AVLTreeNode<K, V>* _root = nullptr：初始时根节点为空
• typedef AVLTreeNode<K, V> Node：结点类型重定义，简化书写

AVL 树的操作实现

插入

1. 本质

插入操作的本质是：

• AVL 树的插入操作是在二叉搜索树插入逻辑基础上，增加了平衡维护的关键步骤，核心要解决 '插入新节点可能破坏树的平衡，导致查询效率下降' 的问题。

2. 思路简述

插入操作思路的简述：

AVL 树插入 == 二叉搜索树插入（找位置、挂节点） + 平衡修复（更新平衡因子 + 旋转调整）

流程分 5 步：

1. 空树处理：树为空时，新节点直接作为根
2. 查找插入位置：从根出发，按二叉搜索树规则（小往左、大往右）找到新节点的父节点 parent，确定挂左还是挂右
3. 挂载新节点：创建新节点，连接到 parent 的 左 or 右 子树，并维护 parent 指针
4. 更新平衡因子：从新节点的父节点开始，向上更新路径上所有节点的平衡因子（_balacnFactor），反映子树高度变化
5. 平衡修复：根据平衡因子判断是否失衡（绝对值 ≥ 2），若失衡则通过旋转操作（单旋 / 双旋）恢复平衡，同时更新旋转后节点的平衡因子

3. 二叉搜索树的插入逻辑

public:
bool insert(const pair<K, V>& kv) {
    // 先走二叉搜索树的插入逻辑
    if (_root == nullptr) {
        _root = new Node(kv);
        return true;
    }
    // _root 不为空时的操作
    Node* parent = nullptr;
    Node* curNode = _root;
    // 先找空，找到一个可以插入的位置
    while (curNode) {
        if (kv.first < curNode->_kv.first) {
            parent = curNode;
            curNode = curNode->_left;
        } else if (kv.first > curNode->_kv.first) {
            parent = curNode;
            curNode = curNode->_right;
        } else // 搜索树中不允许有重复的值 对于已有值，不插入
            return false;
    }
    // while 循环结束后，代表找到了可以插入的位置
    // 找到位置了，但父节点不知道 新结点 比自己大还是比自己小，需要再次判断
    curNode = new Node(kv);
    if (curNode->_kv.first < parent->_kv.first)
        parent->_left = curNode;
    else
        parent->_right = curNode;
    curNode->_parent = parent;
    // 以上是二叉搜索树的插入逻辑，这样插入可能导致树不平衡，从而导致查找效率退化为 O(n)
    // 以下是 AVL 树对二叉搜索树 进行的 控制平衡 操作 的代码
    // 控制平衡 ...
}

详细讲解二叉搜索树迭代插入的逻辑）：

• 插入时，需要先找到空位置，默认插入的元素不能重复

1. 空树特判：若 _root == nullptr，直接把根设为新节点（new Node(key)）。
2. 否则从 _root 向下查找插入位置：
   • 使用 curNode 跟随，parent 保存其父节点（因为当 curNode 为 nullptr 时需要把新节点挂到 parent）。
   • 如果 kv.first > curNode->_kv.first，curNode沿右子树移动；kv.first < curNode->_kv.first时，curNode沿左子树移动。
   • 如果 kv.first == curNode->_kv.first，返回 false（二叉搜索树默认不允许重复键）。
3. 当 curNode 走到 nullptr（找到空位）后，代表 curNode已找到合适的可以插入的位置。
4. new Node(kv) 建节点
   • 要插入新结点，必须修改 curNode的父节点内的左右孩子指针，但父节点并不知道要插入的 key 比自己大还是自己小，只知道下面由位置可以插入，不知道插入到哪个位置
   • 因此要根据 key 与 parent->_key 的比较把它接为左/右子节点。
     • 如果 curNode->_kv.first > parent->_kv.first → 插到右边 (parent->_right = curNode)
     • 如果 curNode->_kv.first < parent->_kv.first → 插到左边 (parent->_left = curNode)

• 总结：✔️ 循环结束时，位置已经找到了，就是 curNode == nullptr 的地方。 ✔️ 但是插入操作不能直接修改 curNode，必须通过 parent 去改指针。 ✔️ 而 parent 自己并不知道空位是在左边还是右边，所以需要再比较一次来决定。

4. 更新平衡因子

1. 插入后父节点的平衡因子变化分析

• 新创建结点的平衡因子：

• 新结点插入在右：

• 新结点插入在左：

2. 平衡因子更新后的三种情况：

1. 更新后平衡因子 == 0：不用继续沿着到 root的路径往上更新平衡因子

2. 更新后平衡因子 == 1 or -1：继续沿着到 root的路径往上更新平衡因子

3. 更新后平衡因子 == 2 or -2：树已失衡，需进行旋转

3. 更新平衡因子的最坏情况

• 更新平衡因子的最坏情况：为一路更新到根节点，因此可以使用循环控制更新，循环条件为 while(parent)

4. 更新平衡因子的代码实现

public:
bool insert(const pair<K, V>& kv) {
    // ... 以上是二叉搜索树的插入逻辑，这样插入可能导致树不平衡，从而导致查找效率退化为 O(n)
    // 以下是 AVL 树对二叉搜索树 进行的 控制平衡 操作 ...
    // 插入后，最坏情况时：可能 root 的平衡因子需要更新，只有 root 的 parent 为空
    while (parent) {
        // 插入后，先更新平衡因子
        if (curNode == parent->_left)
            --parent->_balanceFactor;
        else // if (curNode == parent->_right)
            ++parent->_balanceFactor;

        // 当前 parent 结点更新完了，判断是否还需要再往上更新
        // 处理平衡因子更新后有三种情况
        // 情况一 parent 所在子树高度不变且平衡，无需更新 和 旋转，结束循环
        if (parent->_balanceFactor == 0) {
            break;
        }
        // 情况二 parent 所在子树高度变了，继续往上更新
        else if (parent->_balanceFactor == 1 || parent->_balanceFactor == -1) {
            curNode = parent;
            parent = parent->_parent;
        }
        // 情况三 当前子树不平衡了，需要旋转
        else if (parent->_balanceFactor == 2 || parent->_balanceFactor == -2) {
            // 旋转的情况和操作
        }
        else // 其他情况报错
            assert(false);
    }
    // 插入结束后，return true
    return true;
}

核心操作：

while (parent)

/-------------第一步：更新新插入节点的父节点的平衡因子-------------/

• 新插入节点是左子节点 —> 父节点的平衡因子 -1
• 新插入节点是右子节点 —> 父节点的平衡因子 +1

/-------------第二步：根据父节点的平衡因子做进一步的更新-------------/

• 情况 1：父节点的平衡因子为 0 —> 高度变化未影响上层，结束更新
• 情况 2：父节点的平衡因子为±1 —> 高度变化需向上传递，继续更新上层节点
• 情况 3：父节点的平衡因子为±2 —> 树失衡，需要旋转调整
• 情况 4：非法平衡因子 —> 断言失败 return true;

旋转操作

旋转的目的

• 保持搜索树的规则
• 不平衡的树变成平衡的，其次降低旋转树的高度

旋转总共分为四种：根据不同的不平衡情况我们需要采取不同的旋转方式，这些操作在插入或删除节点导致树失衡时自动触发

• 左单旋：处理 RR 型失衡
• 右单旋：处理 LL 型失衡
• 左右双旋：处理 RL 型失衡
• 右左双旋：处理 LR 型失衡

需要旋转的情况：父节点的平衡因子为±2 —> 树失衡，需要旋转调整

• 失衡 1：左左失衡（父子平衡因子都为'负'） —> 右单旋
• 失衡 2：右右失衡（父子平衡因子都为'正'） —> 左单旋
• 失衡 3：左右失衡（父为'负'，子为'正'） —> 左右双旋
• 失衡 4：右左失衡（父为'正'，子为'负'） ----> 右左双旋
• 特殊情况：非法平衡因子 —> 断言失败

一、左单旋

触发条件

• 左单旋的触发条件：
  • 当 AVL 树中某个节点的右子树高度比左子树高度大 2，且失衡是由右子树的右子树插入节点导致（即右子树的右子树深度增加，称为 'RR 型失衡'）时，需要通过左单旋恢复平衡。

左单旋原理与核心操作

核心操作：旋转过程分为三步（以节点 60(curNode) 为旋转中心，对 parent 进行左单旋）

1. 先处理 curNode 的 left 结点或子树：处理 curLeft 和 parent 的链接关系，注意 curLeft可能为空
2. parent 可能是整棵树的根节点，也可能是某棵树的子树
   • parent 是根节点时：curNode成为整棵树的新根，_parent 指向 nullptr。最后再将 parent正确挂载，成为 curNode的左子树
   • parent 不是根节点时：需要先保存 curNode的祖父结点 ppNode，判断parent 是 ppNode 的左孩子还是右孩子，再更改链接关系。最后再将 parent正确挂载，成为 curNode的左子树
3. 最后将 parent 和 curNode 的平衡因子都更改为 0

左单旋原理：

代码实现

private:
// 左单旋 2 1 newNode 练成线，单纯的右边高
void RotateL(Node* parent) {
    if (parent == nullptr || parent->_right == nullptr)
        return;
    Node* curNode = parent->_right;
    Node* curLeft = curNode->_left; // curLeft 有可能为空

    // 先处理 curNode 的 left 结点，curLeft 有可能是空
    parent->_right = curLeft;
    if (curLeft)
        curLeft->_parent = parent;

    // 再处理 curNode 结点
    // parent 有可能是根节点，也有可能是子树的根节点
    if (parent == _root) {
        // 先立新根
        _root = curNode;
        curNode->_parent = nullptr;
        // 再挂旧根
        parent->_parent = curNode;
        curNode->_left = parent;
    } else {
        Node* ppNode = parent->_parent; // 这里不知道 parent 是 ppNode 的 左孩子 还是 右孩子
        if (parent == ppNode->_left)
            ppNode->_left = curNode;
        else
            ppNode->_right = curNode;
        curNode->_parent = ppNode;
        // 挂 parent
        parent->_parent = curNode;
        curNode->_left = parent;
    }
    parent->_balanceFactor = curNode->_balanceFactor = 0;
}

二、右单旋

右单旋可以看做是左单旋的镜像操作

触发条件

• 右单旋的触发条件：
  • 当 AVL 树中某个节点的左子树高度比右子树高度大 2，且失衡是由左子树的左子树插入节点导致（即右子树的右子树深度增加，称为 'LL 型失衡'）时，需要通过右单旋恢复平衡。

右单旋原理与核心操作

核心操作：旋转过程分为三步（以节点 30(curNode) 为旋转中心，对 parent 进行右单旋）

1. 先处理 curNode 的 right 结点或子树：处理 curRight 和 parent 的链接关系，注意 curRight可能为空
2. parent 可能是整棵树的根节点，也可能是某棵树的子树
   • parent 是根节点时：curNode成为整棵树的新根，_parent 指向 nullptr。最后再将 parent正确挂载，成为 curNode的左子树
   • parent 不是根节点时：需要先保存 curNode的祖父结点 ppNode，判断parent 是 ppNode 的左孩子还是右孩子，再更改链接关系。最后再将 parent正确挂载，成为 curNode的右子树
3. 最后将 parent 和 curNode 的平衡因子都更改为 0

parent 为根节点的情况：

parent 为某棵树的子树的情况：

代码实现

private:
// 右单旋 -2 -1 newNode 连成线，单纯的左边高
void RotateR(Node* parent) {
    // parent 为空 或 curNode 为空的情况
    if (parent == nullptr || parent->_left == nullptr)
        return;
    Node* curNode = parent->_left;
    Node* curRight = curNode->_right;

    // 把 curNode 的 right 给给 parent 的 left
    parent->_left = curRight;
    if (curRight)
        curRight->_parent = parent;

    if (parent == _root) {
        // 先立新根
        _root = curNode;
        curNode->_parent = nullptr;
        // 再挂旧根
        curNode->_right = parent;
        parent->_parent = curNode;
    } else {
        Node* ppNode = parent->_parent; // 找 parent 是 ppNode 的左还是右
        if (parent == ppNode->_left)
            ppNode->_left = curNode;
        else
            ppNode->_right = curNode;
        curNode->_parent = ppNode;
        // 挂 parent
        curNode->_right = parent;
        parent->_parent = curNode;
    }
    curNode->_balanceFactor = parent->_balanceFactor = 0;
}

三、单旋有效与失效的场景

仅单旋有效的场景总结：

单旋失效场景总结：

四、双旋的分析

双旋的简单样例

双旋的本质

双旋后平衡因子的更新

• 双旋平衡因子的更新分为三种情况讨论，以下为左右双旋的场景：

• 双旋的核心操作不在于旋转，因为双旋只是左单旋和右单旋的简单组合
  • 双旋的核心操作在于旋转后平衡因子的更新

五、左右双旋

触发条件

• 左右双旋的触发条件：折线的拐角在左边
• 当 AVL 树中某个节点的左子树高度比右子树高度大 2，且失衡是由左子树的右子树插入节点导致（即左子树的右子树深度增加，称为 'LR 型失衡' ）时，需要通过左右双旋恢复平衡。
• 左右双旋是 左单旋 + 右单旋 的复合操作，专门处理 LR 型失衡
• 左右双旋通过 '先左旋修正左子树方向，再右旋整体平衡' 的两步操作，解决 LR 型失衡问题

左右双旋的过程以及平衡因子的更新：

代码实现

关键操作：

1. 对 cur结点进行左旋
2. 再对 parent结点进行右旋
3. 最终 curRight结点成为树的新根
4. 旋转完后进行平衡因子的更新

// 左右双旋
void RotateLR(Node* parent) {
    Node* curNode = parent->_left;
    Node* curRight = curNode->_right;
    int bf_curRight = curRight->_balanceFactor;

    // 旋转
    RotateL(parent->_left);
    RotateR(parent);

    // 双旋 这里的麻烦事 是平衡因子的更新
    // 更新平衡因子
    if (bf_curRight == 0) {
        parent->_balanceFactor = 0;
        curNode->_balanceFactor = 0;
        curRight->_balanceFactor = 0;
    } else if (bf_curRight == 1) {
        parent->_balanceFactor = 0;
        curNode->_balanceFactor = -1;
        curRight->_balanceFactor = 0;
    } else if (bf_curRight == -1) {
        parent->_balanceFactor = 1;
        curNode->_balanceFactor = 0;
        curRight->_balanceFactor = 0;
    } else
        assert(false);
}

六、右左双旋

右左双旋可以看做是左右双旋的镜像操作，二者可以看作是一个对称的关系。当插入节点在不平衡节点的右子树的左边时，可以记作右左型 (RL 型)，此时采用右左双旋的方法去调整平衡，即先对不平衡节点的右子树进行一次右单旋，之后再对不平衡节点为根的子树进行一次左单旋。

触发条件

• 右左双旋的触发条件：折线的拐角在右边
• 当 AVL 树中某个节点的右子树高度比左子树高度大 2，且失衡是由右子树的左子树插入节点导致（即右子树的左子树深度增加，称为 'RL 型失衡' ）时，需要通过右左双旋恢复平衡。
• 左双旋是 右单旋 + 左单旋 的复合操作，专门处理RL 型失衡
• 右左双旋通过 '先右旋修正右子树方向，再左旋整体平衡' 的两步操作，解决 RL 型失衡问题

右左双旋的过程以及平衡因子的更新：

代码实现

关键操作：

1. 对 cur结点进行右旋
2. 再对 parent结点进行左旋
3. 最终 curLeft结点成为树的新根
4. 旋转完后进行平衡因子的更新

// 右左双旋 parent 的平衡因子为 2 或 -2
void RotateRL(Node* parent) {
    Node* curNode = parent->_right;
    Node* curLeft = curNode->_left;
    int bf_curLeft = curLeft->_balanceFactor;

    // 旋转
    RotateR(parent->_right);
    RotateL(parent);

    // 双旋 这里的麻烦事 是平衡因子的更新
    // 更新平衡因子
    if (bf_curLeft == 0) {
        parent->_balanceFactor = 0;
        curNode->_balanceFactor = 0;
        curLeft->_balanceFactor = 0;
    } else if (bf_curLeft == 1) {
        parent->_balanceFactor = -1;
        curNode->_balanceFactor = 0;
        curLeft->_balanceFactor = 0;
    } else if (bf_curLeft == -1) {
        parent->_balanceFactor = 0;
        curNode->_balanceFactor = 1;
        curLeft->_balanceFactor = 0;
    } else
        assert(false);
}

插入的总结与完整代码

总结流程：

1. 空树处理：树为空时，新节点直接作为根
2. 查找插入位置：从根出发，按二叉搜索树规则（小往左、大往右）找到新节点的父节点 parent，确定挂左还是挂右
3. 挂载新节点：创建新节点，连接到 parent 的 左 or 右 子树，并维护 parent 指针
4. 更新平衡因子：从新节点的父节点开始，向上更新路径上所有节点的平衡因子（_balacnFactor），反映子树高度变化
5. 平衡修复：根据平衡因子判断是否失衡（绝对值 ≥ 2），若失衡则通过旋转操作（单旋 / 双旋）恢复平衡，同时更新旋转后节点的平衡因子
   • 右单旋：处理 LL 型失衡
   • 左单旋：处理 RR 型失衡
   • 左右双旋：处理 RL 型失衡
   • 右左双旋：处理 LR 型失衡

完整插入代码

public:
bool insert(const pair<K, V>& kv) {
    // 先走二叉搜索树的插入逻辑
    if (_root == nullptr) {
        _root = new Node(kv);
        return true;
    }
    // _root 不为空时，二叉搜索树的逻辑
    Node* parent = nullptr;
    Node* curNode = _root;
    // 先找空，找到一个可以插入的位置
    while (curNode) {
        if (kv.first < curNode->_kv.first) {
            parent = curNode;
            curNode = curNode->_left;
        } else if (kv.first > curNode->_kv.first) {
            parent = curNode;
            curNode = curNode->_right;
        } else // 搜索树中不允许有重复的值 对于已有值，不插入
            return false;
    }
    // while 循环结束后，代表找到了可以插入的位置
    // 找到位置了，但父节点不知道 新结点比自己大还是比自己小
    curNode = new Node(kv);
    if (curNode->_kv.first < parent->_kv.first) {
        parent->_left = curNode;
    } else {
        parent->_right = curNode;
    }
    curNode->_parent = parent;

    // 以上是二叉搜索树的插入逻辑，这样插入可能导致树不平衡，从而导致查找效率退化为 O(n)
    // 以下是 AVL 树对二叉搜索树 进行的 控制平衡 操作
    // 控制平衡 ...
    // 插入后，先更新平衡因子
    // 插入后，最坏情况时：可能 root 的平衡因子需要更新，只有 root 的 parent 为空
    while (parent) {
        // 更新平衡因子
        if (curNode == parent->_left)
            --parent->_balanceFactor;
        else // if (curNode == parent->_right)
            ++parent->_balanceFactor;

        // 当前 parent 结点更新完了，判断是否还需要再往上更新
        // 处理平衡因子更新后有三种情况
        // 情况一 parent 所在子树高度不变且平衡，无需更新 和 旋转 结束循环
        if (parent->_balanceFactor == 0) {
            break;
        }
        // 情况二 parent 所在子树高度变了，继续往上更新
        else if (parent->_balanceFactor == 1 || parent->_balanceFactor == -1) {
            curNode = parent;
            parent = parent->_parent;
        }
        // 情况三 当前子树不平衡了，需要旋转
        else if (parent->_balanceFactor == 2 || parent->_balanceFactor == -2) {
            // 左单旋'右子树右高'的一种情况
            // 2 1 newNode 排成直线，单纯的右边高，进行 左单旋
            // 2 -> 右高，1 -> 右高，右右 左单旋
            if (parent->_balanceFactor == 2 && curNode->_balanceFactor == 1) {
                RotateL(parent);
            }
            // -2 -1 newNode 排成直线，单纯的右边高，进行，右单旋
            // -2 -> 左高，-1 -> 左高，左左 右单旋
            else if (parent->_balanceFactor == -2 && curNode->_balanceFactor == -1) {
                RotateR(parent);
            }
            // 2 -1 newNode 排成折线 右左双旋
            else if (parent->_balanceFactor == 2 && curNode->_balanceFactor == -1) {
                RotateRL(parent);
            }
            // -2 1 newNode 排成折线 左右双旋
            else if (parent->_balanceFactor == -2 && curNode->_balanceFactor == 1) {
                RotateLR(parent);
            } else {
                assert(false);
            }
            // 旋转后，让这棵树平衡，且降低了这棵树的高度，
            // 旋转后 就无需再更新平衡因子了，可以跳出循环
            break;
        } else {
            assert(false); // 平衡因子不是 0 1 -1 2 -2 直接报错
        }
    }
    return true;
}

AVL 树的删除

AVL 树的删除操作这里不做重点讲解，这个操作会比插入稍复杂一些，但核心思路依然是走正常的二叉搜索树的删除操作 + 更新平衡因子 + 失衡时进行旋转

只不过与二叉搜索树删除不同的是，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。

具体实现可参考《算法导论》或《数据结构 - 用面向对象方法与 C++ 描述》殷人昆版

4. 验证操作

求树的高度

求树的高度思路如下：

• 先分别求树的左右子树高度
• 最终返回左右子树中 高度更大的高度 + 1

public:
int Height(Node* root) {
    if (root == nullptr)
        return 0;
    // 分别求左右子树的高度
    int leftHeight = Height(root->_left);
    int rightHeight = Height(root->_right);
    // 左右子树中 高度更大的那个 + 1
    return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

判断树是否是 AVL 平衡树

• 先分别求树的左右子树高度
• AVL 平衡树的条件：
  • 当前树是 AVL 树：abs(rightHeight - leftHeight) < 2 &&
    • 左右子树也都是 AVL 树：_IsBalance(root->_left) && _IsBalance(root->_right);

public:
// 判断是否是 AVL 树
bool isBalance() {
    return _IsBalance(_root);
}
private:
bool _IsBalance(Node* root) {
    if (root == nullptr)
        return true;
    int leftHeight = Height(root->_left);
    int rightHeight = Height(root->_right);
    // 加一层保障
    if (rightHeight - leftHeight != root->_balanceFactor) {
        cout << " 平衡因子异常：" << root->_kv.first << "->" << root->_balanceFactor << endl;
        return false;
    }
    return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);
}

测试 AVL 树的正确性

• 使用 20000000 个随机数测试

void test() {
    const int N = 20000000;
    vector<int> v;
    v.reserve(N);
    srand(time(0));
    AVLTree<int, int> t;
    for (size_t i = 0; i < N; ++i)
        v.push_back(rand());
    for (auto e : v)
        t.insert(make_pair(e, e));
    cout << t.isBalance() << endl;
}
int main() {
    test();
    return 0;
}

4. 完整代码实现

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;

template<class K, class V>
struct AVLTreeNode {
    pair<K, V> _kv; // 键值对
    // 三叉链
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent; // 插入结点后，需要更新平衡因子，有了_parent，可以很方便的找父节点
    // 平衡因子，用于判断当前子树 有没有出现不平衡的问题
    int _balanceFactor; // balance factor 平衡因子

    // Node 的构造函数
    AVLTreeNode(const pair<K, V>& kv) :
        _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _balanceFactor(0) // 新结点 初始的平衡因子为 0
    {}

    // 我们使用 平衡因子 = 右子树的高度 - 左子树的高度
    // AVL 树的实现不是一定需要平衡因子，也可以动态的计算高度来判断
    // 使用平衡因子实现只是其中一种方式
};

// 左右子树高度之差的绝对值 小于等于 1 (-1 0 1)
template<class K, class V>
class AVLTree {
    typedef AVLTreeNode<K, V> Node;
private:
    AVLTreeNode<K, V>* _root = nullptr;
public:
    bool insert(const pair<K, V>& kv) {
        // 先走二叉搜索树的插入逻辑
        if (_root == nullptr) {
            _root = new Node(kv);
            return true;
        }
        // _root 不为空时，二叉搜索树的逻辑
        Node* parent = nullptr;
        Node* curNode = _root;
        // 先找空，找到一个可以插入的位置
        while (curNode) {
            if (kv.first < curNode->_kv.first) {
                parent = curNode;
                curNode = curNode->_left;
            } else if (kv.first > curNode->_kv.first) {
                parent = curNode;
                curNode = curNode->_right;
            } else // 搜索树中不允许有重复的值 对于已有值，不插入
                return false;
        }
        // while 循环结束后，代表找到了可以插入的位置
        // 找到位置了，但父节点不知道 新结点比自己大还是比自己小
        curNode = new Node(kv);
        if (curNode->_kv.first < parent->_kv.first) {
            parent->_left = curNode;
        } else {
            parent->_right = curNode;
        }
        curNode->_parent = parent;

        // 以上是二叉搜索树的插入逻辑，这样插入可能导致树不平衡，从而导致查找效率退化为 O(n)
        // 以下是 AVL 树对二叉搜索树 进行的 控制平衡 操作
        // 控制平衡 ...
        // 插入后，先更新平衡因子
        // 插入后，最坏情况时：可能 root 的平衡因子需要更新，只有 root 的 parent 为空
        while (parent) {
            // 更新平衡因子
            if (curNode == parent->_left)
                --parent->_balanceFactor;
            else // if (curNode == parent->_right)
                ++parent->_balanceFactor;

            // 当前 parent 结点更新完了，判断是否还需要再往上更新
            // 处理平衡因子更新后有三种情况
            // 情况一 parent 所在子树高度不变且平衡，无需更新 和 旋转 结束循环
            if (parent->_balanceFactor == 0) {
                break;
            }
            // 情况二 parent 所在子树高度变了，继续往上更新
            else if (parent->_balanceFactor == 1 || parent->_balanceFactor == -1) {
                curNode = parent;
                parent = parent->_parent;
            }
            // 情况三 当前子树不平衡了，需要旋转
            else if (parent->_balanceFactor == 2 || parent->_balanceFactor == -2) {
                // 左单旋'右子树右高'的一种情况
                // 2 1 newNode 排成直线，单纯的右边高，进行 左单旋
                // 2 -> 右高，1 -> 右高，右右 左单旋
                if (parent->_balanceFactor == 2 && curNode->_balanceFactor == 1) {
                    RotateL(parent);
                }
                // -2 -1 newNode 排成直线，单纯的右边高，进行，右单旋
                // -2 -> 左高，-1 -> 左高，左左 右单旋
                else if (parent->_balanceFactor == -2 && curNode->_balanceFactor == -1) {
                    RotateR(parent);
                }
                // 2 -1 newNode 排成折线 右左双旋
                else if (parent->_balanceFactor == 2 && curNode->_balanceFactor == -1) {
                    RotateRL(parent);
                }
                // -2 1 newNode 排成折线 左右双旋
                else if (parent->_balanceFactor == -2 && curNode->_balanceFactor == 1) {
                    RotateLR(parent);
                } else {
                    assert(false);
                }
                // 旋转后，让这棵树平衡，且降低了这棵树的高度，
                // 旋转后 就无需再更新平衡因子了，可以跳出循环
                break;
            } else {
                assert(false); // 平衡因子不是 0 1 -1 2 -2 直接报错
            }
        }
        return true;
    }

    // 判断是否是 AVL 树
    bool isBalance() {
        return _IsBalance(_root);
    }
private:
    bool _IsBalance(Node* root) {
        if (root == nullptr)
            return true;
        int leftHeight = Height(root->_left);
        int rightHeight = Height(root->_right);
        // 加一层保障
        if (rightHeight - leftHeight != root->_balanceFactor) {
            cout << " 平衡因子异常：" << root->_kv.first << "->" << root->_balanceFactor << endl;
            return false;
        }
        return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);
    }

    int Height(Node* root) {
        if (root == nullptr)
            return 0;
        // 分别求左右子树的高度
        int leftHeight = Height(root->_left);
        int rightHeight = Height(root->_right);
        // 左右子树中 高度更大的那个 + 1
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    // 左单旋 复习版
    void RotateL_review(Node* parent) {
        if (parent == nullptr || parent->_right == nullptr)
            return;
        Node* curNode = parent->_right;
        Node* curLeft = curNode->_left;
        parent->_right = curLeft;
        if (curLeft) // curLeft 可能为空
            curLeft->_parent = parent;
        // parent 可能是根节点，也可能是一颗子树
        if (parent == _root) {
            // 先立新根
            _root = curNode;
            curNode->_parent = nullptr;
            // 再挂旧根
            parent->_parent = curNode;
            curNode->_left = parent;
        } else {
            Node* ppNode = parent->_parent; // 先立新根
            // 这里不知道 parent 是 ppNode 的左 还是右
            if (parent == ppNode->_left)
                ppNode->_left = curNode;
            else
                ppNode->_right = curNode;
            curNode->_parent = ppNode;
            // 再挂 parent
            parent->_parent = curNode;
            curNode->_left = parent;
        }
        parent->_balanceFactor = curNode->_balanceFactor = 0;
    }

    // 左单旋 2 1 newNode 练成线，单纯的右边高
    void RotateL(Node* parent) {
        if (parent == nullptr || parent->_right == nullptr)
            return;
        Node* curNode = parent->_right;
        Node* curLeft = curNode->_left; // curLeft 有可能为空
        // 先处理 curNode 的 left 结点，curLeft 有可能是空
        parent->_right = curLeft;
        if (curLeft)
            curLeft->_parent = parent;
        // 再处理 curNode 结点
        // parent 有可能是根节点，也有可能是子树的根节点
        if (parent == _root) {
            // 先立新根
            _root = curNode;
            curNode->_parent = nullptr;
            // 再挂旧根
            parent->_parent = curNode;
            curNode->_left = parent;
        } else {
            Node* ppNode = parent->_parent; // 这里不知道 parent 是 ppNode 的 左孩子 还是 右孩子
            if (parent == ppNode->_left)
                ppNode->_left = curNode;
            else
                ppNode->_right = curNode;
            curNode->_parent = ppNode;
            // 挂 parent
            parent->_parent = curNode;
            curNode->_left = parent;
        }
        parent->_balanceFactor = curNode->_balanceFactor = 0;
    }

    // 右单旋 -2 -1 newNode 连成线，单纯的左边高
    void RotateR(Node* parent) {
        // parent 为空 或 curNode 为空的情况
        if (parent == nullptr || parent->_left == nullptr)
            return;
        Node* curNode = parent->_left;
        Node* curRight = curNode->_right;
        // 把 curNode 的 right 给给 parent 的 left
        parent->_left = curRight;
        if (curRight)
            curRight->_parent = parent;
        if (parent == _root) {
            // 先立新根
            _root = curNode;
            curNode->_parent = nullptr;
            // 再挂旧根
            curNode->_right = parent;
            parent->_parent = curNode;
        } else {
            Node* ppNode = parent->_parent; // 找 parent 是 ppNode 的左还是右
            if (parent == ppNode->_left)
                ppNode->_left = curNode;
            else
                ppNode->_right = curNode;
            curNode->_parent = ppNode;
            // 挂 parent
            curNode->_right = parent;
            parent->_parent = curNode;
        }
        curNode->_balanceFactor = parent->_balanceFactor = 0;
    }

    // 右左双旋 parent 的平衡因子为 2 或 -2
    void RotateRL(Node* parent) {
        Node* curNode = parent->_right;
        Node* curLeft = curNode->_left;
        int bf_curLeft = curLeft->_balanceFactor;
        // 旋转
        RotateR(parent->_right);
        RotateL(parent);
        // 双旋 这里的麻烦事 是平衡因子的更新
        // 更新平衡因子
        if (bf_curLeft == 0) {
            parent->_balanceFactor = 0;
            curNode->_balanceFactor = 0;
            curLeft->_balanceFactor = 0;
        } else if (bf_curLeft == 1) {
            parent->_balanceFactor = -1;
            curNode->_balanceFactor = 0;
            curLeft->_balanceFactor = 0;
        } else if (bf_curLeft == -1) {
            parent->_balanceFactor = 0;
            curNode->_balanceFactor = 1;
            curLeft->_balanceFactor = 0;
        } else
            assert(false);
    }

    // 左右双旋
    void RotateLR(Node* parent) {
        Node* curNode = parent->_left;
        Node* curRight = curNode->_right;
        int bf_curRight = curRight->_balanceFactor;
        // 旋转
        RotateL(parent->_left);
        RotateR(parent);
        // 双旋 这里的麻烦事 是平衡因子的更新
        // 更新平衡因子
        if (bf_curRight == 0) {
            parent->_balanceFactor = 0;
            curNode->_balanceFactor = 0;
            curRight->_balanceFactor = 0;
        } else if (bf_curRight == 1) {
            parent->_balanceFactor = 0;
            curNode->_balanceFactor = -1;
            curRight->_balanceFactor = 0;
        } else if (bf_curRight == -1) {
            parent->_balanceFactor = 1;
            curNode->_balanceFactor = 0;
            curRight->_balanceFactor = 0;
        } else
            assert(false);
    }
};

5. 结语

从最初的二叉搜索树到 AVL 树，我们一步步地走完了'从失衡到平衡'的进化历程。

AVL 树通过平衡因子 + 旋转操作巧妙地在插入、删除之间保持树的高度稳定，让查找性能始终维持在对数级别。

它是现代平衡树结构（如红黑树、Treap、B 树等）的理论基石，也让我们深刻理解了'以空间换时间'、'以维护换性能'的设计哲学。

虽然 AVL 树在插入删除时的维护成本略高，但在查找密集的场景中，它的稳定性与高效性仍然无可替代。

希望这篇文章能帮助你彻底理解平衡二叉树的核心思想，为你后续深入学习红黑树、STL map/set 底层实现打下坚实的基础。