前言：

 AVL 树：它是空树，左右子树也都是 AVL 树,任意节点的左右子树高度差的绝对值 ≤ 1
简单来说，AVL 树就是「加了严格平衡限制的二叉搜索树」，通过控制高度差来保证树的高度不会无限增长。

一、AVL 树插入的核心流程

AVL 树是自平衡二叉搜索树，核心特性是：任意节点的左右子树高度差（平衡因子）绝对值不超过

1.插入节点的完整流程如下：

1. 按二叉搜索树规则插入新节点：保证树的 BST 性质不变
2. 回溯更新平衡因子：从新节点向上，更新所有祖先节点的平衡因子
3. 根据平衡因子判断终止 / 旋转：
   • 平衡因子变为 0：子树高度不变，直接终止
   • 平衡因子变为 ±1：子树高度 + 1，继续向上更新
   • 平衡因子变为 ±2：子树失衡，旋转修复后终止

二、平衡因子更新的核心规则

1. 基础定义

• 平衡因子 (BF) = 右子树高度 - 左子树高度
• 高度定义：叶子节点高度为 1，非叶子节点高度 = max(左子树高度, 右子树高度) + 1
• 插入对 BF 的影响：
  • 新节点插在父节点左子树 → 父节点 BF -= 1
  • 新节点插在父节点右子树 → 父节点 BF += 1

2. 三大终止 / 更新规则

3.三大终止对应三种典型场景

场景 1：插入触发失衡，需要旋转

场景说明

新节点13插入在14的左子树，回溯更新时触发10的 BF 变为 2，子树失衡，需要旋转。

详细推导

1. 插入前状态：
   • 14的 BF=0（叶子节点），10的 BF=1（右子树14比左子树高 1），8的 BF=-1（左子树3比右子树10高 1）
2. 插入后回溯更新：
   • 新节点13插在14左子树 → 14的 BF 从0变为-1（0→-1，高度 + 1，继续向上）
   • 14是10的右子树 → 10的 BF 从1变为2（1→2，失衡，触发旋转）
3. 旋转后终止：旋转会将10的子树重新调平衡，同时将子树高度恢复到插入前的高度，因此不会影响上层的8，插入流程直接结束。

场景 2：插入中途终止，无需向上更新

场景说明

新节点插入在1的左子树，回溯更新到3时 BF 变为 0，子树高度不变，直接终止。

详细推导

1. 插入前状态：3的 BF=1（右子树6比左子树1高 1），8的 BF=-1（左子树3比右子树10高 1）
2. 插入后回溯更新：新节点插在3的左子树 → 3的 BF 从1变为0（1→0，高度不变）
3. 直接终止：3的子树高度不变，不会影响上层的8，因此无需继续向上更新，插入流程结束。

场景 3：最坏情况，一路更新到根节点

场景说明

新节点7插入在6的右子树，需要一路回溯更新到根节点8，最终触发旋转。

详细推导

1. 插入前状态：6的 BF=0（左右子树等高），3的 BF=1（右子树6比左子树1高 1），8的 BF=-1（左子树3比右子树10高 1）
2. 插入后回溯更新：
   • 新节点7插在6右子树 → 6的 BF 从0变为1（0→1，高度 + 1，继续向上）
   • 6是3的右子树 → 3的 BF 从1变为2（1→2，失衡，触发旋转）
   • 若旋转后根节点8仍失衡，则继续旋转，直到根节点平衡，这就是「最坏更新到根」的含义
3. 旋转后终止：旋转后子树高度恢复，插入流程结束。

三.AV树插入情况分析

右单旋

1. 触发场景：LL 型失衡

右单旋是 AVL 树中最基础的旋转操作，专门用于修复 **LL 型（左子树的左子树插入）** 导致的失衡：

• 失衡节点parent（图中10）的平衡因子为-2（左子树高度远高于右子树）
• 其左孩子subL（图中5）的平衡因子为-1/0（新节点插入在subL的左子树a中）
• 本质原因：左子树a插入新节点后高度从h变为h+1，向上回溯更新导致parent失衡

2. 旋转的三大核心目标

1. 严格保持二叉搜索树（BST）规则：所有节点满足「左子树 < 根 < 右子树」，大小关系完全不变
2. 恢复 AVL 平衡：旋转后所有节点平衡因子回到-1/0/1的合法范围
3. 降低子树高度：将失衡的h+3高度，恢复为插入前的h+2，不再影响上层祖先

3. 旋转核心步骤（结合图解）

以10为失衡节点、5为左孩子为例，核心操作如下：

• 由于5 < b子树的值 < 10，将中间子树b（5的右孩子）变为10的左子树
• 将10变为5的右子树
• 将5提升为这棵子树的新根
• 旋转后子树高度恢复为h+2，平衡因子全部重置为0，插入结束

---

右单旋的完整图解

1. 初始平衡状态（左图）

• 根节点10：左子树（5为根）高度h+1，右子树b高度h → bf = h - (h+1) = -1（合法）
• 节点5：左右子树a、b高度均为h → bf = 0（合法）
• 所有子树a/b/c均为高度h的 AVL 树，整棵树完全平衡

2. 插入后失衡状态（中图）

• 在a子树插入新节点，a高度从h变为h+1
• 向上回溯更新平衡因子：5的bf从0变为-1，10的bf从-1变为-2
• 10为根的子树左右高度差超过 1，违反 AVL 平衡规则，触发右单旋

3. 旋转后平衡状态（右图）

• 中间子树b成为10的左子树，10成为5的右子树，5成为新根
• 5和10的平衡因子均重置为0，子树高度恢复为h+2
• 整棵树重新满足 AVL 平衡规则，且 BST 大小关系完全不变

// 右单旋：parent为失衡节点（bf=-2），subL为其左孩子
void RotateR(Node* parent)
{
    Node* subL = parent->_left;    // 左孩子5（subL：sub Left）
    Node* subLR = subL->_right;    // 中间子树b（subLR：sub Left Right）

    // 1. 迁移中间子树：b成为parent(10)的左孩子
    parent->_left = subLR;
    // 注意：如果subLR不为空，必须更新其parent指针（空指针不能访问成员，否则崩溃）
    if (subLR != nullptr)
    {
        subLR->_parent = parent;
    }

    // 2. parent(10)成为subL(5)的右孩子
    subL->_right = parent;
    // 更新parent的父指针为subL
    parent->_parent = subL;

    // 3. 保存parent的父节点，用于后续更新上层指针
    Node* pParent = parent->_parent;

    // 4. 处理parent的父节点（分根节点/局部子树两种情况）
    if (parent == _root)
    {
        // 情况1：parent是整棵树的根，subL成为新根
        _root = subL;
        subL->_parent = nullptr;  // 根节点父指针必须为空
    }
    else
    {
        // 情况2：parent是局部子树，判断它是父节点的左/右孩子
        if (pParent->_left == parent)
        {
            pParent->_left = subL;
        }
        else
        {
            pParent->_right = subL;
        }
        // 更新subL的父指针为原parent的父节点
        subL->_parent = pParent;
    }

    // 5. 更新平衡因子：旋转后parent和subL的bf均为0
    subL->_bf = 0;
    parent->_bf = 0;
}

易错点

• 空指针安全：subLR可能为空（如5没有右孩子），必须加if (subLR != nullptr)判断，否则会触发段错误
• 父指针维护：AVL 树采用三叉链结构（left/right/parent），旋转后必须同步更新所有相关节点的parent指针，否则树结构会断裂
• 根节点处理：区分parent是整棵树的根还是局部子树的根，分别处理上层指针
• 平衡因子重置：旋转后subL和parent的平衡因子均为0，无需再向上更新，插入直接结束

左单旋

1. 触发场景：RR 型失衡

左单旋是 AVL 树中与右单旋对称的基础旋转操作，专门用于修复 **RR 型（右子树的右子树插入）** 导致的失衡：

• 失衡节点parent（图中10）的平衡因子为2（右子树高度远高于左子树）
• 其右孩子subR（图中15）的平衡因子为1/0（新节点插入在subR的右子树a中）
• 本质原因：右子树a插入新节点后高度从h变为h+1，向上回溯更新导致parent失衡

2. 旋转的三大核心目标

1. 严格保持二叉搜索树（BST）规则：所有节点满足「左子树 < 根 < 右子树」，大小关系完全不变
2. 恢复 AVL 平衡：旋转后所有节点平衡因子回到-1/0/1的合法范围
3. 降低子树高度：将失衡的h+3高度，恢复为插入前的h+2，不再影响上层祖先

3. 旋转核心步骤（结合图解）

以10为失衡节点、15为右孩子为例，核心操作如下：

• 由于10 < b子树的值 < 15，将中间子树b（15的左孩子）变为10的右子树
• 将10变为15的左子树
• 将15提升为这棵子树的新根
• 旋转后子树高度恢复为h+2，平衡因子全部重置为0，插入结束

---

左单旋的完整图解

1. 初始平衡状态（左图）

• 根节点10：左子树c高度h，右子树（15为根）高度h+1 → bf = (h+1) - h = 1（合法）
• 节点15：左右子树b、a高度均为h → bf = 0（合法）
• 所有子树a/b/c均为高度h的 AVL 树，整棵树完全平衡

2. 插入后失衡状态（中图）

• 在a子树插入新节点，a高度从h变为h+1
• 向上回溯更新平衡因子：15的bf从0变为1，10的bf从1变为2
• 10为根的子树左右高度差超过 1，违反 AVL 平衡规则，触发左单旋

3. 旋转后平衡状态（右图）

• 中间子树b成为10的右子树，10成为15的左子树，15成为新根
• 10和15的平衡因子均重置为0，子树高度恢复为h+2
• 整棵树重新满足 AVL 平衡规则，且 BST 大小关系完全不变

// 左单旋：parent为失衡节点（bf=2），subR为其右孩子
void RotateL(Node* parent)
{
    Node* subR = parent->_right;    // 右孩子15（subR：sub Right）
    Node* subRL = subR->_left;      // 中间子树b（subRL：sub Right Left）

    // 1. 迁移中间子树：b成为parent(10)的右孩子
    parent->_right = subRL;
    // 注意：如果subRL不为空，必须更新其parent指针（空指针不能访问成员，否则崩溃）
    if (subRL != nullptr)
    {
        subRL->_parent = parent;
    }

    // 2. parent(10)成为subR(15)的左孩子
    subR->_left = parent;
    // parent的父指针必须指向subR（新根），而非subRL
    parent->_parent = subR;

    // 3. 保存parent的父节点，用于后续更新上层指针
    Node* pParent = parent->_parent;

    // 4. 处理parent的父节点（分根节点/局部子树两种情况）
    if (pParent == nullptr)
    {
        // 情况1：parent是整棵树的根，subR成为新根
        _root = subR;
        subR->_parent = nullptr;  // 根节点父指针必须为空
    }
    else
    {
        // 情况2：parent是局部子树，判断它是父节点的左/右孩子
        if (pParent->_left == parent)
        {
            pParent->_left = subR;
        }
        else
        {
            pParent->_right = subR;
        }
        // 更新subR的父指针为原parent的父节点
        subR->_parent = pParent;
    }

    // 5. 更新平衡因子：旋转后parent和subR的bf均为0
    parent->_bf = 0;
    subR->_bf = 0;
}

代码关键细节

• 空指针安全：subRL可能为空（如15没有左孩子），必须加if (subRL != nullptr)判断，否则会触发段错误
• 父指针维护：AVL 树采用三叉链结构（left/right/parent），旋转后必须同步更新所有相关节点的parent指针，否则树结构会断裂
• 根节点处理：区分parent是整棵树的根还是局部子树的根，分别处理上层指针
• 平衡因子重置：旋转后subR和parent的平衡因子均为0，无需再向上更新，插入直接结束
• 与右单旋的对称性：左单旋是右单旋的完全镜像，仅需将left/right互换、subL/subR互换即可

左右双旋

1. 触发场景：LR 型失衡

左右双旋是 AVL 树中用于修复 **LR 型（左子树的右子树插入）** 失衡的复合旋转操作，是单旋的组合应用：

• 失衡节点parent（图中10）的平衡因子为-2（左子树整体太高）
• 其左孩子subL（图中5）的平衡因子为1（新节点插入在subL的右子树中）
• 本质原因：subL的右子树插入新节点后，导致parent左子树高度异常，无法通过单次单旋直接修复，必须先左单旋、再右单旋

2. 旋转的三大核心目标

1. 严格保持二叉搜索树（BST）规则：所有节点满足「左子树 < 根 < 右子树」，大小关系完全不变
2. 恢复 AVL 平衡：旋转后所有节点平衡因子回到-1/0/1的合法范围
3. 降低子树高度：将失衡的h+3高度，恢复为插入前的h+2，不再影响上层祖先

二、两种典型插入场景的完整图解

场景 1：8 的右子树插入 9（LR 型，subLR.bf=1）

1. 插入前平衡状态

• 根节点10：左子树（5为根）高度 2，右子树15高度 1 → bf = 1-2 = -1（合法）
• 节点5：左子树1高度 1，右子树8高度 1 → bf = 1-1 = 0（合法）
• 节点8：左右子树高度 0 → bf = 0（合法）
• 所有节点平衡因子均在-1/0/1范围内，树完全平衡

2. 插入 9 后失衡状态

• 按 BST 规则，9 > 8，插入为8的右孩子（红色节点）
• 向上回溯更新平衡因子：
  • 8：插入在右子树 → bf从0→1（高度 + 1，继续）
  • 5：插入在右子树 → bf从0→1（高度 + 1，继续）
  • 10：插入在左子树 → bf从-1→-2（失衡！，触发 LR 型双旋）

3. 双旋修复过程

1. 第一步：对 5 做左单旋
   • 将8提升为5的父节点，5成为8的左孩子，8的左子树（空）成为5的右孩子
   • 此时10的左孩子变为8，10的bf仍为-2，LR 型转化为 LL 型
2. 第二步：对 10 做右单旋
   • 将8提升为10的父节点，10成为8的右孩子，8的右子树（5的右子树）成为10的左孩子
   • 旋转后树结构恢复平衡，高度回到插入前的 3 层

4. 最终平衡状态

• 新根8，左孩子5，右孩子10
• 5的左孩子1，右孩子（空）；10的左孩子9，右孩子15
• 所有节点平衡因子均为0，完全符合 AVL 规则

场景 2：8 的左子树插入 6（LR 型，subLR.bf=-1）

1. 插入前平衡状态

• 根节点10：左子树（5为根）高度 2，右子树15高度 1 → bf = -1（合法）
• 节点5：左子树1高度 1，右子树8高度 1 → bf = 0（合法）
• 节点8：左右子树高度 0 → bf = 0（合法）

2. 插入 6 后失衡状态

• 按 BST 规则，6 < 8且6 > 5，插入为8的左孩子（红色节点）
• 向上回溯更新平衡因子：
  • 8：插入在左子树 → bf从0→-1（高度 + 1，继续）
  • 5：插入在右子树 → bf从0→1（高度 + 1，继续）
  • 10：插入在左子树 → bf从-1→-2（失衡！，触发 LR 型双旋）

3. 双旋修复过程

1. 第一步：对 5 做左单旋
   • 将8提升为5的父节点，5成为8的左孩子，8的左子树6成为5的右孩子
   • 此时10的左孩子变为8，10的bf仍为-2，LR 型转化为 LL 型
2. 第二步：对 10 做右单旋
   • 将8提升为10的父节点，10成为8的右孩子，8的右子树（空）成为10的左孩子
   • 旋转后树结构恢复平衡，高度回到插入前的 3 层

4. 最终平衡状态

• 新根8，左孩子5，右孩子10
• 5的左孩子1，右孩子6；10的左孩子（空），右孩子15
• 所有节点平衡因子均合法，完全符合 AVL 规则

---

抽象通用场景（覆盖所有 LR 型情况）

下图是 LR 型双旋的抽象通用模型，a/e/f/c为高度h的 AVL 子树，覆盖了所有插入场景：

• 初始状态：10为根，5为左孩子，8为5的右孩子
• 插入后：在e（8的左子树）或f（8的右子树）插入新节点，导致10的bf变为-2
• 双旋过程：先对5左单旋，再对10右单旋，根据8的bf值更新所有节点的bf
• 最终状态：8为新根，5为左孩子，10为右孩子，子树高度恢复，所有节点bf合法

// 左右双旋：parent为失衡节点（bf=-2），subL为其左孩子，subLR为subL的右孩子
// 用于修复LR型失衡：parent.bf=-2，subL.bf=1
void RotateLR(Node* parent)
{
    Node* subL = parent->_left;    // 左孩子5（subL：sub Left）
    Node* subLR = subL->_right;    // 中间节点8（subLR：sub Left Right）
    int bf = subLR->_bf;           // 保存中间节点的平衡因子，用于后续更新

    // 第一步：对subL(5)做左单旋，将LR型转化为LL型
    RotateL(parent->_left);
    // 第二步：对parent(10)做右单旋，最终修复失衡
    RotateR(parent);

    // 根据中间节点subLR(8)的平衡因子，更新所有节点的bf
    if (bf == 0)
    {
        // 场景：subLR原本平衡，插入后bf=0（如subLR为叶子节点插入）
        subL->_bf = 0;
        subLR->_bf = 0;
        parent->_bf = 0;
    }
    else if (bf == -1)
    {
        // 场景：新节点插入在subLR的左子树（如8的左孩子插入6）
        subL->_bf = 0;
        subLR->_bf = 0;
        parent->_bf = 1;
    }
    else if (bf == 1)
    {
        // 场景：新节点插入在subLR的右子树（如8的右孩子插入9）
        subL->_bf = -1;
        subLR->_bf = 0;
        parent->_bf = 0;
    }
    else
    {
        // 非法情况，触发断言，方便调试
        assert(false);
    }
}

代码关键细节说明

1. 旋转顺序：必须先左单旋（对 subL），再右单旋（对 parent），顺序不可颠倒，否则会破坏 BST 结构
2. 中间节点 bf 保存：旋转前必须保存subLR的 bf 值，因为旋转会修改节点的 bf，导致后续判断错误
3. 三种 bf 分支逻辑：
   • bf=0：中间节点原本平衡，插入后仍平衡，所有节点 bf 重置为 0
   • bf=-1：新节点插入中间节点左子树（如插入 6），parent 的 bf 为 1
   • bf=1：新节点插入中间节点右子树（如插入 9），subL 的 bf 为 - 1
4. 空指针安全：依赖RotateL/RotateR中的空指针判断，无需额外处理
5. 父指针维护：由RotateL/RotateR完成，无需重复操作，保证三叉链结构完整

右左双旋

触发场景：RL 型失衡

右左双旋是 AVL 树中与左右双旋（LR 型）完全对称的复合旋转操作，专门用于修复 **RL 型（右子树的左子树插入）** 导致的失衡：

• 失衡节点parent（图中10）的平衡因子为2（右子树整体太高）
• 其右孩子subR（图中15）的平衡因子为-1（新节点插入在subR的左子树中）
• 本质原因：subR的左子树插入新节点后，导致parent右子树高度异常，无法通过单次单旋直接修复，必须先右单旋、再左单旋

2. 旋转的三大核心目标

1. 严格保持二叉搜索树（BST）规则：所有节点满足「左子树 < 根 < 右子树」，大小关系完全不变
2. 恢复 AVL 平衡：旋转后所有节点平衡因子回到-1/0/1的合法范围
3. 降低子树高度：将失衡的h+3高度，恢复为插入前的h+2，不再影响上层祖先

---

右左双旋的完整图解与场景分析

1. 抽象模型与初始状态

我们将a/b/c抽象为高度为h的 AVL 子树，进一步展开b子树为节点12，以及其高度为h-1的左右子树e、f，覆盖所有 RL 型失衡场景：

• 初始平衡状态：根节点10，右孩子15，15的左孩子12
• 节点10的平衡因子：1（右子树高度h+1，左子树高度h，合法）
• 节点15的平衡因子：0（左右子树高度均为h，合法）
• 节点12的平衡因子：0（左右子树高度均为h-1，合法）

2. 三种典型插入场景

场景 1：h >= 1，e子树（12的左子树）插入新节点

• 插入后失衡：e子树高度从h-1变为h，向上回溯更新平衡因子：
  • 12的bf从0变为-1
  • 15的bf从0变为-1
  • 10的bf从1变为2（失衡！，触发 RL 型双旋）
• 双旋过程：
  1. 第一步：对15做右单旋，将12提升为15的父节点，把 RL 型转化为 RR 型
  2. 第二步：对10做左单旋，将12提升为10的父节点，彻底修复失衡
• 最终平衡因子：10的bf=0，12的bf=0，15的bf=1

场景 2：h >= 1，f子树（12的右子树）插入新节点

• 插入后失衡：f子树高度从h-1变为h，向上回溯更新平衡因子：
  • 12的bf从0变为1
  • 15的bf从0变为-1
  • 10的bf从1变为2（失衡！，触发 RL 型双旋）
• 双旋过程：
  1. 第一步：对15做右单旋，将12提升为15的父节点，把 RL 型转化为 RR 型
  2. 第二步：对10做左单旋，将12提升为10的父节点，彻底修复失衡
• 最终平衡因子：15的bf=0，12的bf=0，10的bf=-1

场景 3：h == 0，b子树为新增节点（a/b/c均为空）

• 插入后失衡：12作为新增节点插入15的左子树，向上回溯更新平衡因子：
  • 15的bf从0变为-1
  • 10的bf从1变为2（失衡！，触发 RL 型双旋）
• 双旋过程：
  1. 第一步：对15做右单旋，将12提升为15的父节点
  2. 第二步：对10做左单旋，将12提升为10的父节点
• 最终平衡因子：10、12、15的bf均为0

// 右左双旋：parent为失衡节点（bf=2），subR为其右孩子，subRL为subR的左孩子
// 用于修复RL型失衡：parent.bf=2，subR.bf=-1
void RotateRL(Node* parent)
{
    Node* subR = parent->_right;    // 右孩子15（subR：sub Right）
    Node* subRL = subR->_left;      // 中间节点12（subRL：sub Right Left）
    int bf = subRL->_bf;             // 保存中间节点的平衡因子，用于后续更新

    // 第一步：对subR(15)做右单旋，将RL型转化为RR型
    RotateR(parent->_right);
    // 第二步：对parent(10)做左单旋，最终修复失衡
    RotateL(parent);

    // 根据中间节点subRL(12)的平衡因子，更新所有节点的bf
    if (bf == 0)
    {
        // 场景3：h==0，中间节点为新增节点，bf=0
        // 旋转后所有节点bf均为0
        subR->_bf = 0;
        subRL->_bf = 0;
        parent->_bf = 0;
    }
    else if (bf == 1)
    {
        // 场景2：新节点插入在subRL的右子树（f子树），bf=1
        // 旋转后parent(10)的bf=-1，subR(15)和subRL(12)的bf=0
        subR->_bf = 0;
        subRL->_bf = 0;
        parent->_bf = -1;
    }
    else if (bf == -1)
    {
        // 场景1：新节点插入在subRL的左子树（e子树），bf=-1
        // 旋转后subR(15)的bf=1，subRL(12)和parent(10)的bf=0
        subR->_bf = 1;
        subRL->_bf = 0;
        parent->_bf = 0;
    }
    else
    {
        // 非法情况，触发断言，方便调试
        assert(false);
    }
}

代码关键细节说明

1. 旋转顺序：必须先右单旋（对 subR），再左单旋（对 parent），顺序不可颠倒，否则会破坏 BST 结构
2. 中间节点 bf 保存：旋转前必须保存subRL的 bf 值，因为旋转会修改节点的 bf，导致后续判断错误
3. 三种 bf 分支逻辑：
   • bf=0：中间节点为新增节点（h==0场景），所有节点 bf 重置为 0
   • bf=1：新节点插入中间节点右子树（f子树），parent的 bf 为-1
   • bf=-1：新节点插入中间节点左子树（e子树），subR的 bf 为1
4. 与左右双旋的对称性：右左双旋是左右双旋的完全镜像，仅需将left/right互换、subL/subR互换即可
5. 空指针安全：依赖RotateR/RotateL中的空指针判断，无需额外处理
6. 父指针维护：由RotateR/RotateL完成，无需重复操作，保证三叉链结构完整

四.完整实现代码

#include <iostream>
#include <cassert>
using namespace std;

// AVL树节点结构（三叉链：left/right/parent + 平衡因子bf）
struct Node
{
    int _val;           // 节点值
    Node* _left;        // 左孩子
    Node* _right;       // 右孩子
    Node* _parent;      // 父节点
    int _bf;            // 平衡因子：右子树高度 - 左子树高度

    // 构造函数
    Node(int val)
        : _val(val)
        , _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _bf(0)
    {}
};

// AVL树类
class AVLTree
{
private:
    Node* _root;    // 根节点

public:
    // 构造函数
    AVLTree()
        : _root(nullptr)
    {}

    // 插入节点（对外接口）
    bool Insert(int val)
    {
        // 1. 按BST规则插入
        if (_root == nullptr)
        {
            _root = new Node(val);
            return true;
        }

        Node* parent = nullptr;
        Node* cur = _root;

        // 找到插入位置
        while (cur != nullptr)
        {
            parent = cur;
            if (cur->_val < val)
                cur = cur->_right;
            else if (cur->_val > val)
                cur = cur->_left;
            else
                return false;   // 值重复，插入失败
        }

        // 新建节点
        cur = new Node(val);
        if (parent->_val < val)
            parent->_right = cur;
        else
            parent->_left = cur;
        cur->_parent = parent;

        // 2. 回溯更新平衡因子 + 旋转修复
        while (parent != nullptr)
        {
            // 更新父节点平衡因子
            if (parent->_left == cur)
                parent->_bf--;
            else
                parent->_bf++;

            // 判断是否需要继续向上更新
            if (parent->_bf == 0)
            {
                // 高度不变，终止更新
                break;
            }
            else if (parent->_bf == 1 || parent->_bf == -1)
            {
                // 高度变化，继续向上
                cur = parent;
                parent = parent->_parent;
            }
            else if (parent->_bf == 2 || parent->_bf == -2)
            {
                // 失衡，旋转修复
                if (parent->_bf == 2)
                {
                    // RR / RL
                    if (cur->_bf == 1)
                    {
                        // RR型：左单旋
                        RotateL(parent);
                    }
                    else
                    {
                        // RL型：右左双旋
                        RotateRL(parent);
                    }
                }
                else // parent->_bf == -2
                {
                    // LL / LR
                    if (cur->_bf == -1)
                    {
                        // LL型：右单旋
                        RotateR(parent);
                    }
                    else
                    {
                        // LR型：左右双旋
                        RotateLR(parent);
                    }
                }
                break;
            }
        }
        return true;
    }

    // 中序遍历（验证BST性质：有序）
    void InOrder()
    {
        _InOrder(_root);
        cout << endl;
    }

    // 验证是否是AVL树（对外接口）
    bool IsAVLTree()
    {
        return _IsAVLTree(_root);
    }

private:
    // 中序遍历递归实现
    void _InOrder(Node* root)
    {
        if (root == nullptr)
            return;

        _InOrder(root->_left);
        cout << root->_val << " ";
        _InOrder(root->_right);
    }

    // 获取树高度
    int _Height(Node* root)
    {
        if (root == nullptr)
            return 0;

        int leftH = _Height(root->_left);
        int rightH = _Height(root->_right);
        return leftH > rightH ? leftH + 1 : rightH + 1;
    }

    // 递归验证AVL树合法性
    bool _IsAVLTree(Node* root)
    {
        if (root == nullptr)
            return true;

        int leftH = _Height(root->_left);
        int rightH = _Height(root->_right);

        // 验证平衡因子
        if (rightH - leftH != root->_bf)
        {
            cout << "平衡因子异常：" << root->_val << endl;
            return false;
        }

        // 验证高度差绝对值 ≤1
        if (abs(leftH - rightH) > 1)
        {
            cout << "失衡节点：" << root->_val << endl;
            return false;
        }

        // 递归验证左右子树
        return _IsAVLTree(root->_left) && _IsAVLTree(root->_right);
    }

    // ===================== 你提供的四种旋转（完全不变）=====================
    // 右单旋：LL型
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        parent->_left = subLR;
        if (subLR != nullptr)
        {
            subLR->_parent = parent;
        }

        subL->_right = parent;
        parent->_parent = subL;

        Node* pParent = parent->_parent;

        if (parent == _root)
        {
            _root = subL;
            subL->_parent = nullptr;
        }
        else
        {
            if (pParent->_left == parent)
            {
                pParent->_left = subL;
            }
            else
            {
                pParent->_right = subL;
            }
            subL->_parent = pParent;
        }

        subL->_bf = 0;
        parent->_bf = 0;
    }

    // 左单旋：RR型
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        parent->_right = subRL;
        if (subRL != nullptr)
        {
            subRL->_parent = parent;
        }

        subR->_left = parent;
        parent->_parent = subR;

        Node* pParent = parent->_parent;

        if (pParent == nullptr)
        {
            _root = subR;
            subR->_parent = nullptr;
        }
        else
        {
            if (pParent->_left == parent)
            {
                pParent->_left = subR;
            }
            else
            {
                pParent->_right = subR;
            }
            subR->_parent = pParent;
        }

        parent->_bf = 0;
        subR->_bf = 0;
    }

    // 左右双旋：LR型
    void RotateLR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        int bf = subLR->_bf;

        RotateL(parent->_left);
        RotateR(parent);

        if (bf == 0)
        {
            subL->_bf = 0;
            subLR->_bf = 0;
            parent->_bf = 0;
        }
        else if (bf == -1)
        {
            subL->_bf = 0;
            subLR->_bf = 0;
            parent->_bf = 1;
        }
        else if (bf == 1)
        {
            subL->_bf = -1;
            subLR->_bf = 0;
            parent->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }

    // 右左双旋：RL型
    void RotateRL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        int bf = subRL->_bf;

        RotateR(parent->_right);
        RotateL(parent);

        if (bf == 0)
        {
            subR->_bf = 0;
            subRL->_bf = 0;
            parent->_bf = 0;
        }
        else if (bf == 1)
        {
            subR->_bf = 0;
            subRL->_bf = 0;
            parent->_bf = -1;
        }
        else if (bf == -1)
        {
            subR->_bf = 1;
            subRL->_bf = 0;
            parent->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }
};

// 测试代码
int main()
{
    AVLTree tree;

    // 测试插入（可自行修改）
    int arr[] = { 10, 5, 14, 3, 8, 13, 15 };
    for (int e : arr)
    {
        tree.Insert(e);
    }

    // 中序遍历验证BST
    cout << "中序遍历：";
    tree.InOrder();

    // 验证是否是合法AVL树
    if (tree.IsAVLTree())
        cout << "是合法AVL树" << endl;
    else
        cout << "不是AVL树" << endl;

    return 0;
}