《C++进阶之STL》【AVL树】

往期《C++初阶》回顾：

《C++初阶》目录导航

---

往期《C++进阶》回顾：
/------------ 继承多态 ------------/
【普通类/模板类的继承 + 父类&子类的转换 + 继承的作用域 + 子类的默认成员函数】
【final + 继承与友元 + 继承与静态成员 + 继承模型 + 继承和组合】
【多态：概念 + 实现 + 拓展 + 原理】
/------------ STL ------------/
【二叉搜索树】

前言：

Hi~ 小伙伴们大家好呀(✿◡‿◡)！回头一看，我去距离上次更新居然已经过去 10 天了┗( T﹏T )┛ —— 真没料到自己不知不觉 “鸽” 了这么久！
其实原本计划处暑那天就更新的，可结果一拖再拖，愣是 “鸽” 到了七夕，哈哈真不是有意为之，属实是有点 “咕咕精” 实锤了～～(￣▽￣*)ゞ

不过今天总算赶回来啦٩(◕‿◕｡)۶！这次要和大家分享的内容是 【AVL 树】 。
咱们之前提过，最终目标是吃透红黑树，从底层拿下set/map容器，但直接上手红黑树对现在的我们来说，难度还是有点高(＞﹏＜)。
而 AVL 树不仅和红黑树有不少相通的核心逻辑，学习门槛还更适中，刚好能帮我们做好过渡、打牢基础。
所以，准备好跟着节奏一起探索 AVL 树了吗？(ﾉ>ω<)ﾉ Let’s go！

------------概念介绍------------

1. 什么是AVL树？

AVL树：是一种 自平衡二叉搜索树，由苏联数学家 Georgy Adelson-Velsky 和 Evgenii Landis 在 1962 年提出，其名称来源于这两位发明者的名字缩写。

• AVL树是最早发明的 自平衡二叉搜索树
• AVL树是在普通二叉搜索树的基础上增加了平衡条件，确保树始终保持近似平衡状态
• AVL树要么是空树，要么是满足以下性质的二叉搜索树：
  • 其左、右子树也都是 AVL 树
  • 并且左、右子树的高度差的绝对值不超过 1

2. AVL树的基本性质怎么样？

核心特点：

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

---

基本操作：

• 插入：新节点插入后，从插入节点开始向上检查祖先节点的平衡因子。如果发现某个节点的平衡因子绝对值超过 1，就需要进行旋转操作来恢复平衡。
  • 例如：插入节点后，某节点左子树高度比右子树高度大 2，且插入位置在该节点左子树的左子树上，此时就需要进行右旋操作。
• 删除：删除节点后，同样从删除节点的位置向上检查祖先节点的平衡因子。如果出现不平衡，通过一系列的旋转操作和节点调整来重新平衡树。
  • 而且删除操作相对插入更复杂，因为可能需要多次旋转来恢复平衡。
• 查找：和普通二叉搜索树查找方式相同，从根节点开始，根据比较节点值的大小，决定向左子树或右子树继续查找，直到找到目标节点或者确定目标节点不存在，时间复杂度为$O(logn)$

---

优缺比较：

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

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

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

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

• 当树的节点数为 2、4 ……等特定数量时，最优的高度差只能是 1，无法强制达到 0

• 这说明 AVL 树的平衡条件是在 "绝对平衡" 和 "实现可行性" 之间的权衡设计

4. 什么是平衡因子？

通过前面关于 AVL 树的介绍，博主相信小伙伴们已经对其有了一定认知，在惊叹于它高效的数据查找能力之余。

我相信小伙伴们也一定会好奇：AVL 树究竟是如何控制二叉搜索树的高度，使其始终保持平衡状态的呢？

---

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

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

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

---

当然平衡因子并非 AVL 树的必需属性（还有其他的方法使AVL树保持平衡状态），但它如同一个 “风向标”

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

------------基本操作------------

一、查找操作

1. 步骤

查找操作的步骤：

1. 定义进行遍历节点的指针
2. 使用while循环查找对应节点
   • 情况1：当前遍历到的节点的键 < 要查找的键 —> “继续向当前节点的右子树中查找”
   • 情况2：当前遍历到的节点的键 > 要查找的键 —> “继续向当前节点的左子树中查找”
   • 情况3：当前遍历到的节点的键 = 要查找的键 —> “找到了要查找的键”
3. 跳出了循环，说明没有找到的键为key的节点

2. 简述

查找操作的简述：

1. 初始化：从根节点开始查找，定义一个指针curr指向根节点_root
2. 比较与移动：在while循环中，不断将当前节点的键curr->_kv.first与要查找的键key进行比较：
   • 如果curr->_kv.first < key，这意味着要查找的节点在当前节点的右子树中，所以将curr更新为curr->_right，继续在右子树中查找
   • 如果curr->_kv.first > key，说明要查找的节点在当前节点的左子树中，将curr更新为curr->_left，继续在左子树中查找
   • 如果curr->_kv.first == key，表示找到了要查找的节点，直接返回当前节点的指针curr
3. 查找失败：当while循环结束，curr变为nullptr，这表明在整个 AVL 树中没有找到键为key的节点，此时返回nullptr

---

AVL 树的高度是 $O(logn)$，在查找过程中，每次比较都会将查找范围缩小到树的一半（类似二分查找 ），因此查找操作的时间复杂度为 $O(logn)$

这意味着：即使树中节点数量非常庞大，查找操作也能在相对较短的时间内完成。

二、插入操作

1. 本质

插入操作的本质是：

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

2. 简述

插入操作的简述：

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

流程分 5 步：

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

3. 步骤

插入操作的步骤：

/----------------第一阶段：准备阶段----------------/

1. 创建一个遍历树的当前节点指针
2. 创建当前遍历节点的父节点的指针

/----------------第二阶段：查找阶段----------------/

循环查找插入位置

• 情况1：当前遍历到的节点的键 < 要插入的键 —> “继续寻找”
• 情况2：当前遍历到的节点的键 > 要插入的键 —> “继续寻找”
• 情况3：当前遍历到的节点的键 = 要插入的键 —> “键已存在”—> 查找插入位置失败

/----------------第三阶段：插入阶段----------------/

1. 创建要插入的节点
2. 将新节点连接到二叉搜索树中
   • 情况1：新节点的键 < 父节点的键
   • 情况2：新节点的键 > 父节点的键

/----------------第四阶段：连接阶段----------------/

1. 更新新插入节点的父节点

---

核心操作第五阶段：调整阶段

while (parent)

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

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

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

• 情况1：父节点的平衡因子为 0 —> 高度变化未影响上层，结束更新
• 情况2：父节点的平衡因子为±1 —> 高度变化需向上传递，继续更新上层节点
• 情况3：父节点的平衡因子为±2 —> 树失衡，需要旋转调整
  • 失衡1：左左失衡（父子平衡因子都为“负”） —> 右单旋
  • 失衡2：右右失衡（父子平衡因子都为“正”） —> 左单旋
  • 失衡3：左右失衡（父为“负”，子为“正”） —> 左右双旋
  • 失衡4：右左失衡（父为“正”，子为“负”） ----> 右左双旋
  • 特殊情况：非法平衡因子 —> 断言失败
  • break
• 情况4：非法平衡因子 —> 断言失败

return true;

4. 图示

根据父节点的平衡因子做进一步的更新“

图示1：演示“情况1 + 情况3”

图示2：演示“情况2”的最坏情况：“一次插入，不停的更新”

• AVL树进行插入的最坏情况，从插入节点到根节点，一路上父节点的平衡因子均为±1， 不断向上更新上层节点，直至更新到根节点。

三、删除操作

哈哈，下面咱先不着急搞 AVL 树的删除操作啦！为啥呢？因为这玩意儿的删除操作啊，简直难出天际 —— 就像你本想轻松拆个小快递，结果发现里面是个嵌套了十层的俄罗斯套娃，每一步都得小心翼翼，稍有不慎就把树的平衡给搞崩，得不停地调整、旋转。

不过别慌，等以后有机会了，一定把这 “折磨人” 的 AVL 删除操作好好补上，现阶段就让我们先略过吧😄

------------旋转平衡------------

AVL树通过下面的四种旋转操作维护平衡，这些操作在插入或删除节点导致树失衡时自动触发。

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

单旋

一、右单旋

1. 条件

右单旋的触发条件：

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

2. 核心

右单旋的核心操作：

旋转过程分为三步（以节点parent为旋转中心）：

1. 提升左子节点：将parent的左子节点subL提升为新的根节点。
2. 处理"悬挂"子树：subL的右子树subLR需要重新挂接到parent的左子树。
3. 更新父子关系：调整各节点的_parent指针，维护三叉链结构。

3. 步骤

/---------------第一阶段：准备阶段---------------/

1. 记录parent的左子节点的“指针
2. 记录parent的左子节点的右子节点的“指针
3. 记录parent的父节点的“指针

/---------------第二阶段：调整阶段---------------/

1. 调整parent和subLR的关系
2. 调整parent和subL的关系
3. 调整根节点或祖父节点的子树指向
   • 情况1：parent节点是根节点 —> 调整根节点
   • 情况2：parent节点不是根节点 —> 调整祖父节点的子树指向
4. 更新平衡因子 —> 右单旋后subL和parent的平衡因子均为0

4. 图示

图示1：AVL树右单旋的原理图：

• 上图展示的是以 10 为根的树结构，其中 a、b、c 抽象为三棵高度为 $h（h\ge 0）$的子树，且 a、b、c 各自均符合 AVL 树的平衡要求
  • 这里的 10，既可能是整棵 AVL 树的根节点，也可能是整棵树中某局部子树的根
  • 把 a、b、c 概括为高度 h 的子树，是一种抽象表示，它涵盖了所有右单旋场景的共性，实际右单旋的具体形态多样，下面的图示会展开详细呈现
• 当在 a 子树中插入新节点后，a 子树高度从 h 增长为 h + 1
  • 随着平衡因子沿父节点向上更新传递，10 节点的平衡因子从 -1 变为 -2 ，使得以 10 为根的子树，左右子树高度差超过 1
  • 违反 AVL 树的平衡规则（呈现左子树过高的失衡状态 ），此时，需要对以 10 为根的子树执行右单旋操作，调整子树结构来重新平衡
• 右单旋的核心步骤逻辑：由于遵循 “5 < b 子树节点值 < 10” 的搜索树有序性规则，旋转时，把 b 子树调整为 10 节点的左子树，让 10 节点成为 5 节点的右子树，5 节点则升级为这棵子树新的根节点
  • 这样调整后，既维持了二叉搜索树的有序性，又使子树恢复平衡，同时子树高度回到插入前的 h + 2 ，符合 AVL 树旋转调整的原则
  • 若原本 10 所在子树是整棵树的局部子树，完成这次旋转后，上层节点的平衡状态不会再受影响，本次插入操作的平衡调整流程就结束了

图示2：情况1 ---> “插入前a/b/c 的高度h==0”

图示3：情况2 ---> “插入前a/b/c 的高度h==1”

图示4：情况3 ---> “插入前a/b/c 的高度h==2”

结论：当插入前a/b/c 的高度h=2 时候，总共有36中触发右单旋转的场景

疑问：这36中触发右单旋的场景是怎么计算出来的？ —> 3*3*4=36

• 第一个3：指的是b子树可以是高度为h==2的AVL树x/y/z中的任意一种
• 第二个3：指的是c子树可以是高度为h==2的AVL树x/y/z中的任意一种
• 4：指的是a子树中有4个位置可以再插入一个节点触发“右单旋”

---

图示5：情况4 ---> “插入前a/b/c 的高度h==3”

结论：当插入前a/b/c 的高度h=3 时候，总共有5400中触发右单旋转的场景

疑问：这5400中触发右单旋的场景是怎么计算出来的？ —> 15*15*(8+4*4)=5400

---

一般计算触发旋转的场景数的计算公式就是：

b子树可能存在的情况数量 * c子树可能存在的情况数量 * a子树可以触发旋转的位置数量

• 第一个15：指的是b子树可以是高度为h==3的AVL树（1棵满AVL树 + 14棵叶子节点为任意1个/任意2个/任意3个的AVL树）中的任意一种
• 第二个15：指的是c子树可以是高度为h==3的15棵AVL树中的任意一种
• 8：指的是a子树为高度为h==3的15棵AVL树中满二叉树时，有8个位置可以再插入一个节点触发“右单旋”
• 4*4：指的是a子树为高度为h==3的另外14棵AVL树中只有4棵是可以实现触发parent节点的有单旋，并且这4棵AVL树中每棵AVL树中有4个位置可以再插入一个节点触发“右单旋”，所以一共有4*4中触发“右单旋”的位置

二、左单旋

1. 条件

左单旋的触发条件：

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

2. 核心

左单旋的核心操作：

旋转过程分为三步（以节点parent为旋转中心）：

1. 提升右子节点：将parent的右子节点subR提升为新的根节点。
2. 处理"悬挂"子树：subR的左子树subRL需要重新挂接到parent的右子树。
3. 更新父子关系：调整各节点的_parent指针，维护三叉链结构。

3. 步骤

/---------------第一阶段：准备阶段---------------/

1. 记录parent的右子节点的“指针
2. 记录parent的右子节点的左子节点的“指针”
3. 记录parent的父节点的“指针”

/---------------第二阶段：调整阶段---------------/

1. 调整parent和subRL的关系
2. 调整parent和subR的关系
3. 调整根节点或祖父节点的子树指向
   • 情况1：parent节点是根节点 —> 调整根节点
   • 情况2：parent节点不是根节点 —> 调整祖父节点的子树指向
4. 更新平衡因子 —> 左单旋后subR和parent的平衡因子均为0

4. 图示

• 上面的图展示的是以 10 为根的树结构，其中 a、b、c 被抽象为三棵高度为 $h（h\ge 0）$的子树，且 a、b、c 各自均符合 AVL 树的平衡要求
  • 这里的 10，既可能是整棵 AVL 树的根节点，也可能是整棵树中某局部子树的根
  • 把 a、b、c 概括为高度 h 的子树，是一种抽象表示，它涵盖了所有左单旋场景的共性（实际左单旋的具体形态多样，和前文右单旋类似，可参照理解 ）
• 当在 a 子树中插入新节点后，a 子树高度从 h 增长为 h + 1
  • 随着平衡因子沿父节点向上更新传递，10 节点的平衡因子从 1 变为 2 ，使得以 10 为根的子树，左右子树高度差超过 1
  • 违反 AVL 树的平衡规则（呈现右子树过高的失衡状态 ）,此时，需要对以 10 为根的子树执行左单旋操作，调整子树结构来重新平衡
• 左单旋的核心步骤逻辑：由于遵循 “10 < b 子树节点值 < 15” 的搜索树有序性规则，旋转时，把 b 子树调整为 10 节点的右子树，让 10 节点成为 15 节点的左子树，15 节点则升级为这棵子树新的根节点
  • 这样调整后，既维持了二叉搜索树的有序性，又使子树恢复平衡，同时子树高度回到插入前的 h + 2 ，符合 AVL 树旋转调整的原则
  • 若原本 10 所在子树是整棵树的局部子树，完成这次旋转后，上层节点的平衡状态不会再受影响，本次插入操作的平衡调整流程就结束了

双旋

看了上面关于单旋的介绍，相信一部分小伙伴就已经觉得OK了：右单旋转可以解决左失衡问题，左单旋转可以解决右失衡问题，那么凭借这两个旋转操作就可以应对AVL树中所有的平衡调整情况。

真的是这样吗？我们还是用实际的案例来看一看吧！

图示1：情况1 ---> “插入前a/b/c 的高度h==0”（错误演示：使用右单旋解决左右失衡问题）

图示2：情况2 ---> “插入前a/b/c 的高度h==1”（错误演示：使用右单旋解决左右失衡问题）

通过上面的两个图可知，当树呈现左子树高的状态时，若新节点并非插入到 a 子树，而是插入到 b 子树，会使 b 子树的高度从 h 变为 h + 1，进而引发旋转操作。此时，仅用右单旋无法解决失衡问题，执行右单旋后，树依旧处于不平衡状态 。

右单旋能处理 “单纯左子树高（即失衡源于左子树的左子树插入节点）” 的情况，可这里因为新节点插入到了 b 子树，以 10 为根的子树不再是简单的左高结构：

从 10 的视角看是左子树高，但从 5 的视角看，5 的右子树更高（属于 “左子树的右子树插入导致失衡”，即 LR 型失衡 ）。这种复杂失衡需要两次旋转来解决：

• 先以 5 为旋转点执行左单旋
• 再以 10 为旋转点执行右单旋

经过这样的操作，树就能重新恢复平衡 。

一、左右双旋

1. 条件

左右双旋的触发条件：

当 AVL 树中某个节点的左子树高度比右子树高度大 2，且失衡是由左子树的右子树插入节点导致（即左子树的右子树深度增加，称为 “LR 型失衡” ）时，需要通过左右双旋恢复平衡。

• 左右双旋是 左单旋 + 右单旋 的复合操作，专门处理 LR 型失衡
• 左右双旋通过 “先左旋修正左子树方向，再右旋整体平衡” 的两步操作，解决 LR 型失衡问题
• 其核心是在保持 BST 有序性的前提下，分阶段调整子树结构，确保任意节点的左右子树高度差 ≤ 1
• 这种复合旋转机制让 AVL 树能处理更复杂的失衡场景，始终维持近似平衡，保证操作的时间复杂度稳定在 $O(logn)$

2. 核心

左右双旋的核心操作：

1. 对subL执行左单旋：
   • 将subL的右子节点subLR提升为新根
   • subLR的左子树subLRL挂接到subL的右子树
2. 对parent执行右单旋：
   • 将subLR提升为整棵子树的根
   • subLR的原右子树subLRR挂接到parent的左子树
3. 更新父子关系：
   • 调整各节点的_parent指针，确保三叉链结构正确
4. 更新平衡因子：
   • 根据插入位置（subLR的左 / 右子树），分情况修正subLR、subL、parent的平衡因子为 0 或 ±1

3. 步骤

/---------------第一阶段：准备阶段---------------/

1. 记录parent的右子节点的“指针”
2. 记录parent的右子节点的左子节点的“指针”
3. 记录parent的右子节点的左子节点的“平衡因子”

/---------------第二阶段：旋转阶段---------------/

1. 首先对当前的节点的右子树进行“右单旋”
2. 然后对当前的节点进行“左单旋”

/---------------第三阶段：更新阶段---------------/

• 情况1：subRL节点原始的平衡因子为“-1”
• 情况2：subRL节点原始的平衡因子为“1”
• 情况3：subRL节点原始的平衡因子为“0”
• 情况4：非法平衡因子，断言失败

4. 图示

图示：情况3 ---> “插入前a/b/c 的高度h==n”（正确演示：使用左右单旋解决左右失衡问题）

介绍双旋时展示的两张图示分别对左右双旋中 h=0 和 h=1 的具体场景展开分析。

接下来，我们把 a、b、c 子树抽象为高度为 h 的 AVL 子树进行统一探讨，同时需进一步展开 b 子树的细节：将其拆分为新增的子树（可理解为 “8” ），以及高度为 h-1 的 e、f 子树（作为 b 子树的左、右子树 ）

这是因为后续要以 b 的父节点 5 为旋转点执行左单旋，而左单旋操作会涉及 b 子树的左子树调整。

---

由于 b 子树中新增结点的位置不同，平衡因子更新的细节也有差异，我们通过观察中间节点（可理解为 “8” ）平衡因子的不同取值，分以下 三种场景 讨论：

• 场景 1：当 h≥1 时，新增结点插入到 e 子树中。e 子树高度从 h-1 增长到 h ，触发平衡因子向上更新（路径为 8→5→10 ），引发旋转。
  • 此场景下，节点 8 的平衡因子为 -1
  • 旋转完成后，节点 8 和 5 的平衡因子变为 0 ，节点 10 的平衡因子变为 1
• 场景 2：当 h≥1 时，新增结点插入到 f 子树中。f 子树高度从 h-1 增长到 h ，同样触发平衡因子向上更新（路径为 8→5→10 ），引发旋转。
  • 此场景下，节点 8 的平衡因子为 1
  • 旋转完成后，节点 8 和 10 的平衡因子变为 0 ，节点 5 的平衡因子变为 -1
• 场景 3：当 h=0 时，a、b、c 均为空树，此时 b 本身就是新增的结点。插入后触发平衡因子向上更新（路径为 5→10 ），引发旋转。
  • 此场景下，节点 8 的平衡因子为 0
  • 旋转完成后，节点 8、10、5 的平衡因子均变为 0 ，树恢复平衡

二、右左双旋

1. 条件

右左双旋的触发条件：

当 AVL 树中某个节点的右子树高度比左子树高度大 2，且失衡是由右子树的左子树插入节点导致（即右子树的左子树深度增加，称为 “RL 型失衡” ）时，需要通过右左双旋恢复平衡。

• 右左双旋是 右单旋 + 左单旋 的复合操作，专门处理 RL 型失衡

• 右左双旋通过 “先右旋修正右子树方向，再左旋整体平衡” 的两步操作，解决 RL 型失衡问题

• 其核心是在保持 BST 有序性的前提下，分阶段调整子树结构，确保任意节点的左右子树高度差 ≤ 1

• 这种复合旋转机制让 AVL 树能处理更复杂的失衡场景，始终维持近似平衡，保证操作的时间复杂度稳定在 $O(logn)$

2. 核心

右左双旋的核心操作：

1. 对subR执行右单旋：
   • 将subR的左子节点subRL提升为新根
   • subRL的左子树subRLR挂接到subR的左子树
2. 对parent执行左单旋：
   • 将subRL提升为整棵子树的根
   • subRL的原左子树subRLL挂接到parent的右子树
3. 更新父子关系：
   • 调整各节点的_parent指针，确保三叉链结构正确
4. 更新平衡因子：
   • 根据插入位置（subRL的左 / 右子树），分情况修正subRL、subR、parent的平衡因子为 0 或 ±1

3. 步骤

/---------------第一阶段：准备阶段---------------/

1. 记录parent的左子节点的“指针”
2. 记录parent的左子节点的右子节点的“指针”
3. 记录parent的左子节点的右子节点的“平衡因子”

/---------------第二阶段：旋转阶段---------------/

1. 首先对当前的节点的左子树进行“左单旋”
2. 然后对当前的节点进行“右单旋”

/---------------第三阶段：更新阶段---------------/

• 情况1：subLR节点原始的平衡因子为“-1”
• 情况2：subLR节点原始的平衡因子为“1”
• 情况3：subLR节点原始的平衡因子为“0”
• 情况4：非法平衡因子，断言失败

4. 图示

与左右双旋的分析思路类似，我们将 a、b、c 子树抽象为高度为 h 的 AVL 子树展开分析。

同时，需进一步细化 b 子树的结构：把它拆分为子树 12，以及高度为 h-1 的 e、f 子树（作为 b 子树的左、右子树 ）

这是因为后续要以 b 的父节点 15 为旋转点执行右单旋，而右单旋操作会涉及 b 子树的右子树调整。

---

由于 b 子树中新增结点的位置不同，平衡因子更新的细节也有差异，我们通过观察中间节点 12 的平衡因子变化，分以下 三种场景 讨论：

• 场景 1：当 h≥1 时，新增结点插入到 e 子树中。e 子树高度从 h-1 增长到 h ，触发平衡因子沿 12→15→10 的路径向上更新，引发旋转。
  • 此场景下，节点 12 的平衡因子为 -1
  • 旋转完成后，节点 10 和 12 的平衡因子变为 0 ，节点 15 的平衡因子变为 1
• 场景 2：当 h≥1 时，新增结点插入到 f 子树中。f 子树高度从 h-1 增长到 h ，同样触发平衡因子沿 12→15→10 的路径向上更新，引发旋转。
  • 此场景下，节点 12 的平衡因子为 1
  • 旋转完成后，节点 15 和 12 的平衡因子变为 0 ，节点 10 的平衡因子变为 -1
• 场景 3：当 h=0 时，a、b、c 均为空树，此时 b 本身就是新增的结点。插入后触发平衡因子沿 15→10 的路径向上更新，引发旋转。
  • 此场景下，节点 12 的平衡因子为 0
  • 旋转完成后，节点 10、12、15 的平衡因子均变为 0 ，树恢复平衡

------------代码实现------------

1. AVL树的存储结构是什么样的？

一、节点的存储结构

如果你之前还记得我们实现的 “二叉搜索树” 的话，应该会记得二叉搜索树的存储结构采用的是二叉链（每个节点仅包含左、右子节点指针 ）

---

疑问：那 AVL 树呢？它本质上也属于二叉搜索树，不过更准确的说法是 平衡二叉搜索树 。既然带着 “平衡” 的特殊性质，大家肯定会好奇：它的存储结构，还是简单的二叉链吗？

答案：AVL 树在二叉链基础上，额外增加了父节点指针、平衡因子 来实现 “自平衡”。

• 严格来说，它属于 三叉链存储结构（节点包含左子、右子、父节点三类指针 ），再配合平衡因子记录子树高度差，以此让树始终维持平衡。

---

这样的设计，就是为了在插入、删除节点后，能通过调整指针和平衡因子，快速让树恢复平衡，保证查找效率稳定在 $O(lo{g}_{2}n)～$

/*----------------定义AVL树节点的结构模板----------------*/template <class K,class V>
struct AVLTreeNode
{/*----------------第一部分：成员变量----------------*///1.节点存储的键值对//2.左右子节点的指针//3.父节点的指针//4.平衡因子pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf;/*----------------第二部分：成员函数----------------*///1.AVL树节点的构造函数AVLTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){ }
};

二、树的存储结构

/*----------------定义AVL树的类模板----------------*/
template <class K, class V>
class AVLTree
{
private:/*----------------第一部分：成员变量----------------*/AVLTreeNode<K, V>* _root = nullptr;/*----------------第二部分：类型别名----------------*///1.重新定义AVL树节点的类型：pair<K,V> ---> Nodetypedef AVLTreeNode<K, V> Node;public://...
};

2. 怎么使用代码实现AVL树？

头文件：AVLTree.h

#pragma once//任务1：包含需要使用头文件
#include <iostream>
#include <assert.h>
using namespace std;//任务2：定义AVL树节点的结构模板
template <class K,class V>
struct AVLTreeNode
{/*----------------第一部分：成员变量----------------*///1.节点存储的键值对//2.左右子节点的指针//3.父节点的指针//4.平衡因子pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf;/*----------------第二部分：成员函数----------------*///1.AVL树节点的构造函数AVLTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){ }
};//任务3：定义AVL树的类模板
template <class K, class V>
class AVLTree
{
private:/*----------------第一部分：成员变量----------------*/AVLTreeNode<K, V>* _root = nullptr;/*----------------第二部分：类型别名----------------*///1.重新定义AVL树节点的类型：pair<K,V> ---> Nodetypedef AVLTreeNode<K, V> Node;/*----------------第三部分：成员函数（私有）----------------*///1.实现：“中序遍历”的操作void _InOrder(Node* root){//处理“特殊情况”+ “递归出口”if (root == nullptr){return;}//处理“正常情况”//1.首先递归遍历“左子树”_InOrder(root->_left);//2.然后输出遍历到的当前的节点cout << root->_kv.first << ":" << root->_kv.second << endl;//3.最后递归遍历“右子树”_InOrder(root->_right);}//2.实现：“获取树的高度”的操作int _Height(Node* root){//处理“特殊情况”+ “递归出口”if (root == nullptr){return 0;}//处理“正常情况”//1.递归计算左子树的高度int leftHeight = _Height(root->_left);//2.递归计算右子树的高度int rightHeight = _Height(root->_right);//3.返回左右子树中高度最高的那一个return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;}//3.实现：“获取节点的数量”的操作int _Size(Node* root){//处理“特殊情况”+ “递归出口”if (root == nullptr){return 0;}//处理“正常情况”//1.直接返回递归计算的左子树和右子树的节点的数量之和return _Size(root->_left) + _Size(root->_right) + 1;}//4.实现：“判断一棵树是不是AVL树”bool _IsAVLTree(Node* root){//处理“特殊情况”+ “递归出口”if (root == nullptr){return true; //空树是AVL树}//处理“正常情况”/*-------------------第一步：计算平衡因子-------------------*/int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int bf = rightHeight - leftHeight;/*-------------------第一步：检查平衡因子-------------------*///1.检查平衡因子“是否合法”if (abs(bf) >= 2){cout << root->_kv.first << "平衡因子不合法" << endl;return false;}//2.检查平衡因子“是否异常”if (root->_bf != bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}/*-------------------第三步：递归验证-------------------*/return _IsAVLTree(root->_left) && _IsAVLTree(root->_right);}public:/*----------------第三部分：成员函数（公有）----------------*///1.实现：“查找键对应节点”Node* Find(const K& key){//1.定义进行遍历节点的指针Node* curr = _root;//2.使用while循环查找对应节点while (curr){//情况1：当前遍历到的节点的键 < 要查找的键 ---> “继续向当前节点的右子树中查找”if (curr->_kv.first < key){curr = curr->_right;}//情况2：当前遍历到的节点的键 > 要查找的键 ---> “继续向当前节点的左子树中查找”else if (curr->_kv.first > key){curr = curr->_left;}//情况3：当前遍历到的节点的键 = 要查找的键 ---> “找到了要查找的键”else{return curr;}}//3.跳出了循环，说明没有找到的键为key的节点return nullptr;}//2.实现：“插入操作”bool Insert(const pair<K, V>& kv)  //注意：没学pair之前我们是这样写的：bool Insert(const K& key, const V& value){//特殊情况：要插入的节点的树是“空树”if (_root == nullptr){//1.直接创建一个节点为跟节点_root = new Node(kv);  //注意：没学pair之前我们是这样写的：_root = new Node(key, value); //2.返回true即可return true;}//正常情况：要插入的节点的树是“非空树”/*----------------第一阶段：准备阶段----------------*///1.创建一个遍历树的当前节点指针Node* current = _root;//2.创建当前遍历节点的父节点的指针Node* parent = nullptr;/*----------------第二阶段：查找阶段----------------*/while (current) //循环查找插入位置{//情况1：当前遍历到的节点的键 < 要插入的键  ---> “继续寻找”if (current->_kv.first < kv.first)  //注意：没学pair之前我们是这样写的：if (current->_key < key){//1.更新当前遍历节点的父节点 parent = current;//不同之处1：这里的需要更新parent指针的位置 //原因：下面我们要在curr指针指向的位置进行插入操作，所以我们需要记录当前遍历到节点的父节点//2.继续去右子树中寻找current = current->_right;}//情况2：当前遍历到的节点的键 > 要插入的键  ---> “继续寻找”else if (current->_kv.first > kv.first) //注意：没学pair之前我们是这样写的：else if (current->_key > key){parent = current;current = current->_left; //继续去左子树中寻找}//情况3：当前遍历到的节点的键 = 要插入的键  ---> “键已存在”---> 查找插入位置失败else{return false;//不同之处2：这里放回的是false//原因：我们实现的二叉搜索树不支持存储“键相等的节点”}}/*----------------第三阶段：插入阶段----------------*///1.创建要插入的节点current = new Node(kv); //注意：没学pair之前我们是这样写的：current = new Node(key, value);//2.将新节点连接到二叉搜索树中 ---> 注意并不能简单的进行插入操作要先判断：// “新节点和父节点的键之间的大小关系，从而判断出新节点是应该插入到父节点的左子节点还是右子节点”//情况1：新节点的键 <  父节点的键if (kv.first < parent->_kv.first) //注意：没学pair之前我们是这样写的：if (key < parent->_key){parent->_left = current;}//情况2：新节点的键 > 父节点的键else   //注意：这里使用else表面上看是：满足key >= parent->_key条件的情况都可以执行下面的代码{	   //但其实key = parent->_key这种情况在上面的第二阶段中已经被的return false排除掉了parent->_right = current;}/*------------------声明：如果是普通的二叉搜索树，到这里插入操作就已经算作是结束了，但是对于平衡二叉搜索树还有步骤------------------*//*----------------第四阶段：连接阶段----------------*///1.更新新插入节点的父节点current->_parent = parent;  //这里之所以要进行更新是因为，AVL树节点的存储了三个指针，也就是其底层是用“三叉链”的结构进行存储的/*----------------第五阶段：调整阶段----------------*/while (parent)  //循环进行平衡二叉搜索树的高度{/*-------------第一步：更新新插入节点的父节点的平衡因子-------------*///位置1：新插入节点是左子节点 ---> 父节点的平衡因子 -1if (current == parent->_left){parent->_bf--; // 插入到左子树，左子树高度+1，平衡因子-1}//位置2：新插入节点是右子节点 ---> 父节点的平衡因子 +1else{parent->_bf++; // 插入到右子树，右子树高度+1，平衡因子+1}/*-------------第二步：根据父节点的平衡因子做进一步的更新-------------*///情况1：父节点的平衡因子为 0 ---> 高度变化未影响上层，结束更新if (parent->_bf == 0){break;}//情况2：父节点的平衡因子为±1 ---> 高度变化需向上传递，继续更新上层节点else if (parent->_bf == -1 || parent->_bf == 1){//1.新节点 ---> 父节点current = current->_parent;  //或者写成：current = parent; //2.父节点 ---> 爷爷节点parent = parent->_parent;  //注意：这里也就体现了，为什么我们要对二叉搜索树底层结构中再设计一个指针_parent了，//因为：调整阶段我们需要更新上层的节点，多引入一个_parent指针可以让我们更方便的找到上层的节点}//情况3：父节点的平衡因子为±2 ---> 树失衡，需要旋转调整else if (parent->_bf == -2 || parent->_bf == 2)  //注意：按理说这里我们因该使用一个else即可，因为平衡因子只可能是：0，±1，±2			{											//但是不怕一万就怕万一，这里我们使用防御性编程，再另设一个情况4（特殊情况）//失衡1：左左失衡（父子平衡因子都为“负”） ---> 右单旋if (parent->_bf == -2 && current->_bf == -1){RotateR(parent);}//失衡2：右右失衡（父子平衡因子都为“正”） ---> 左单旋else if (parent->_bf == 2 && current->_bf == 1){RotateL(parent);}//失衡3：左右失衡（父为“负”，子为“正”） ---> 左右双旋else if (parent->_bf == -2 && current->_bf == 1){RotateLR(parent);}//失衡4：右左失衡（父为“正”，子为“负”） ----> 右左双旋else if (parent->_bf == 2 && current->_bf == -1){RotateRL(parent);}//特殊情况：非法平衡因子 ---> 断言失败else{assert(false);}	break;  //注意：这里一定要添加一个break，因为这个break是调整成功出while循环的唯一方式}//情况4：非法平衡因子 ---> 断言失败else{assert(false); }}return true; // 跳出了调整阶段while循环，说明已经调整成功了，返回true}//3.实现：“右单旋”操作（处理左左失衡的情况）void RotateR(Node* parent){/*---------------第一阶段：准备阶段---------------*///1.记录parent的左子节点的“指针”//2.记录parent的左子节点的右子节点的“指针”//3.记录parent的父节点的“指针”Node* subL = parent->_left;Node* subLR = parent->_left->_right;  //或者写成：Node* subLR = subL->_right;Node* pParent = parent->_parent;/*---------------第二阶段：调整阶段---------------*///1.调整parent和subLR的关系parent->_left = subLR;if (subLR) //注意细节：subLR不一定存在，所以这里为了判断防止对空指针进行解引用，先使用if对subLR指针进行一个判断{subLR->_parent = parent;}//2.调整parent和subL的关系parent->_parent = subL;subL->_right = parent;//3.调整根节点或祖父节点的子树指向//情况1：parent节点是根节点 ---> 调整根节点if (parent == _root){//1.调整根节点_root = subL;  //注意：这里的调整根节点要写成：_root = subL，千万不要写成了subL = _root;//2.更新subL的父节点subL->_parent = nullptr;  //或者写成：_root->_parent =nullptr;}//情况2：parent节点不是根节点 ---> 调整祖父节点的子树指向else{//1.调整祖父节点的子树指向if (parent == pParent->_left){pParent->_left = subL;}else{pParent->_right = subL;}//2.更新subL的父节点subL->_parent = pParent;}//4.更新平衡因子 ---> 右单旋后subL和parent的平衡因子均为0subL->_bf = 0;parent->_bf = 0;}//4.实现：“左单旋”操作（处理右右失衡的情况）void RotateL(Node* parent){/*---------------第一阶段：准备阶段---------------*///1.记录parent的右子节点的“指针”//2.记录parent的右子节点的左子节点的“指针”//3.记录parent的父节点的“指针”Node* subR = parent->_right;Node* subRL = parent->_right->_left;  //或者写成：Node* subLR = subL->_left;Node* pParent = parent->_parent;/*---------------第二阶段：调整阶段---------------*///1.调整parent和subRL的关系parent->_right = subRL;if (subRL){subRL->_parent = parent;}//2.调整parent和subR的关系parent->_parent = subR;subR->_left = parent;//3.调整根节点或祖父节点的子树指向//情况1：parent节点是根节点 ---> 调整根节点if (pParent == nullptr) //或者写成：parent == _root{//1.调整根节点_root = subR;//2.更新subL的父节点subR->_parent = nullptr; //或者写成：_root->_parent = nullptr;}//情况2：parent节点不是根节点 ---> 调整祖父节点的子树指向else{//1.调整祖父节点的子树指向if (parent == pParent->_left){pParent->_left = subR;}else{pParent->_right = subR;}//2.更新subL的父节点subR->_parent = pParent;}//4.更新平衡因子 ---> 左单旋后subR和parent的平衡因子均为0subR->_bf = 0;parent->_bf = 0;}//5.实现：“左右双旋”操作（处理左右失衡的情况）void RotateLR(Node* parent){/*---------------第一阶段：准备阶段---------------*///1.记录parent的左子节点的“指针”//2.记录parent的左子节点的右子节点的“指针”//3.记录parent的左子节点的右子节点的“平衡因子”Node* subL = parent->_left;Node* subLR = parent->_left->_right; //或者写成：Node* subLR = subL->_right;int bf = subLR->_bf;  //注意：双选可以使用两个单旋复用实现，所以我们不需要重新实现节点之间的关系的更新了，但是双旋还有一个难点：“节点的平衡因子的更新”//所以：这里我们需要定义一个变量记录subLR的平衡因子//因为：经过双旋之后，节点平衡因子的更新依赖于“subLR节点原始的平衡因子”/*---------------第二阶段：旋转阶段---------------*///1.首先对当前的节点的左子树进行“左单旋”RotateL(parent->_left);//2.然后对当前的节点进行“右单旋”RotateR(parent);/*---------------第三阶段：更新阶段---------------*///情况1：subLR节点原始的平衡因子为“-1”if (bf == -1){subLR->_bf = 0;   subL->_bf = 0;parent->_bf = 1;}//情况2：subLR节点原始的平衡因子为“1”else if (bf == 1){subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}//情况3：subLR节点原始的平衡因子为“0”else if (bf == 0) //注意：同样的按理说：subLR的平衡因子只可能是：0，1，-1这三中情况，也就是说这里我们因该使用else即可，所以我们还使用防御性编程，以防万一{subLR->_bf = 0; //注意：这里表面看上去并不需要进行更新，这里只是为了以防万一subL->_bf = 0;parent->_bf = 0;}//情况4：非法平衡因子，断言失败else{assert(false); }}//6.实现：“右左双旋”操作（处理右左失衡的情况）void RotateRL(Node* parent){/*---------------第一阶段：准备阶段---------------*///1.记录parent的右子节点的“指针”//2.记录parent的右子节点的左子节点的“指针”//3.记录parent的右子节点的左子节点的“平衡因子”Node* subR = parent->_right;Node* subRL = parent->_right->_left; //或者写成：Node* subRL = subR->_left;int bf = subRL->_bf;//注意：双选可以使用两个单旋复用实现，所以我们不需要重新实现节点之间的关系的更新了，但是双旋还有一个难点：“节点的平衡因子的更新”//所以：这里我们需要定义一个变量记录subRL的平衡因子//因为：经过双旋之后，节点平衡因子的更新依赖于“subRL节点原始的平衡因子”/*---------------第二阶段：旋转阶段---------------*///1.首先对当前的节点的右子树进行“右单旋”RotateR(parent->_right);//2.然后对当前的节点进行“左单旋”RotateL(parent);/*---------------第三阶段：更新阶段---------------*///情况1：subRL节点原始的平衡因子为“-1”if (bf == -1){subRL->_bf = 0;subR->_bf = 1;parent->_bf = 0;}//情况2：subRL节点原始的平衡因子为“1”else if (bf == 1){subRL->_bf = 0;subR->_bf =0;parent->_bf = -1;}//情况3：subRL节点原始的平衡因子为“0”else if (bf == 0) {subRL->_bf = 0; subR->_bf = 0;parent->_bf = 0;}//情况4：非法平衡因子，断言失败else{assert(false);}}//7.实现：“中序遍历”操作void InOrder(){_InOrder(_root); //注意：这里我们实际上是调用private权限下的_InOrder()接口函数实现中序遍历cout << endl;}//8.实现：“获取树的高度”操作int Height(){return _Height(_root); //和上面的一样我们还调用其他接口实现}//9.实现：“获取节点的数量”操作int Size(){return _Size(_root);}//10.实现：“判断一棵树是不是AVL树”bool IsAVLTree(){return _IsAVLTree(_root);}
};

测试文件：Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
#include"AVLTree.h"  // 测试用例1：使用固定数据集测试AVL树的基本插入和平衡性
void TestAVLTree1()
{cout << "------------------测试基本插入和平衡性------------------" << endl;/*---------------第一步：创建AVL树---------------*/AVLTree<int, int> t;  /*---------------第二步：赋值AVL树---------------*///1.常规测试数据集 - 用于基础功能验证int a1[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };//2.特殊测试数据集 - 包含需要双旋操作的场景int a2[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };//3.向AVL树中插入所有测试数据for (auto e : a2){t.Insert({ e, e });  // 键值对均使用相同的整数值}/*---------------第三步：测试AVL树---------------*///1.中序遍历AVL树（应输出有序序列）t.InOrder();  //2.验证树是否保持AVL平衡特性cout <<"如果构建的那棵树是AVL树的话请扣1：" << t.IsAVLTree() << endl;
}// 测试用例2：使用大量随机数据测试AVL树的性能和平衡性
void TestAVLTree2()
{/*---------------第一步：准备 + 设置 随机化---------------*///1.定义测试数据量为100万const int N = 1000000;  //2.初始化随机数种子，确保每次测试生成不同数据srand((unsigned int)time(0));  /*---------------第二步：创建 + 赋值 AVL树---------------*/vector<int> v;v.reserve(N);  //预先分配足够内存，避免动态扩容开销for (int i = 0; i < N; i++){v.push_back(rand() + i); //通过rand()+i确保数值唯一性}/*---------------第二步：插入 + 查找 功能的测试---------------*/AVLTree<int, int> t;/*------------------测试插入性能------------------*/cout << "\n------------------测试插入性能------------------" << endl;//1.1：测试AVL树的插入效率size_t begin1 = clock();  // 记录开始时间for (auto e : v){t.Insert(make_pair(e, e));  // 插入键值对}size_t end1 = clock();  // 记录结束时间cout << "向AVL树中插入100万个节点耗时:" << end1 - begin1 << endl;  // 输出插入操作总耗时//1.2：测试AVL树的高度cout << "该AVL树的高度为:" << t.Height() << endl;  // 输出树的高度（应约为log2(N)）//1.3：验证树是否保持AVL平衡特性cout << "如果构建的那棵树是AVL树的话请扣1：" << t.IsAVLTree() << endl;//1.4：验证树的节点数量是否正确cout << "该AVL树中节点的数量为:" << t.Size() << endl;  /*------------------测试查找性能------------------*/cout << "------------------测试查找性能------------------" << endl;//2.1：测试查找已存在键的性能size_t begin2 = clock();for (auto e : v){t.Find(e);  // 查找每个已插入的键}size_t end2 = clock();cout << "查找100万个AVL树中已存在键的时间消耗为:" << end2 - begin2 << endl;  //2.2：测试查找随机键的性能size_t begin3 = clock();for (int i = 0; i < N; i++){t.Find((rand() + i));}size_t end3 = clock();cout << "在AVL树中查找100万随机键的时间消耗为:" << end3 - begin3 << endl;  
}int main()
{TestAVLTree1();TestAVLTree2();return 0;
}

运行结果：