《C++进阶之STL》【AVL树】-EW帮帮网

【AVL树】目录

前言：
------------概念介绍------------
------------基本操作------------
------------旋转平衡------------
单旋
- 一、右单旋
- 二、左单旋
双旋
------------代码实现------------
1. AVL树的存储结构是什么样的？
- 一、节点的存储结构
- 二、树的存储结构
2. 怎么使用代码实现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 (l o g n)$ ，其中 $n$ 是节点数量，这意味着在 AVL 树中进行查找操作时，时间复杂度稳定在 $O (l o g n)$

相比于普通二叉搜索树在最坏情况下可能退化为链表，查找时间复杂度为 $O (n)$ ，其查找效率更高且稳定

基本操作：

插入：新节点插入后，从插入节点开始向上检查祖先节点的平衡因子。如果发现某个节点的平衡因子绝对值超过 1，就需要进行旋转操作来恢复平衡。

例如：插入节点后，某节点左子树高度比右子树高度大 2，且插入位置在该节点左子树的左子树上，此时就需要进行右旋操作。

删除：删除节点后，同样从删除节点的位置向上检查祖先节点的平衡因子。如果出现不平衡，通过一系列的旋转操作和节点调整来重新平衡树。

而且删除操作相对插入更复杂，因为可能需要多次旋转来恢复平衡。

查找：和普通二叉搜索树查找方式相同，从根节点开始，根据比较节点值的大小，决定向左子树或右子树继续查找，直到找到目标节点或者确定目标节点不存在，时间复杂度为 $O (l o g n)$

优缺比较：

优点：查找效率高且稳定，时间复杂度为 $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. 步骤

查找操作的步骤：

定义进行遍历节点的指针

使用while循环查找对应节点

情况1：当前遍历到的节点的键 < 要查找的键 —> “继续向当前节点的右子树中查找”

情况2：当前遍历到的节点的键 > 要查找的键 —> “继续向当前节点的左子树中查找”

情况3：当前遍历到的节点的键 = 要查找的键 —> “找到了要查找的键”

跳出了循环，说明没有找到的键为key的节点

2. 简述

查找操作的简述：

初始化：从根节点开始查找，定义一个指针curr指向根节点_root

比较与移动：在while循环中，不断将当前节点的键curr->_kv.first与要查找的键key进行比较：

如果curr->_kv.first < key，这意味着要查找的节点在当前节点的右子树中，所以将curr更新为curr->_right，继续在右子树中查找

如果curr->_kv.first > key，说明要查找的节点在当前节点的左子树中，将curr更新为curr->_left，继续在左子树中查找

如果curr->_kv.first == key，表示找到了要查找的节点，直接返回当前节点的指针curr

查找失败：当while循环结束，curr变为nullptr，这表明在整个 AVL 树中没有找到键为key的节点，此时返回nullptr

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

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

二、插入操作

1. 本质

插入操作的本质是：

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

2. 简述

插入操作的简述：

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

流程分 5 步：

空树处理：树为空时，新节点直接作为根

查找插入位置：从根出发，按二叉搜索树规则（小往左、大往右）找到新节点的父节点 parent，确定挂左还是挂右

挂载新节点：创建新节点，连接到 parent 的左 / 右子树，并维护 parent 指针

更新平衡因子：从新节点的父节点开始，向上更新路径上所有节点的平衡因子（_bf），反映子树高度变化

平衡修复：根据平衡因子判断是否失衡（绝对值 ≥ 2），若失衡则通过旋转操作（单旋 / 双旋）恢复平衡，同时更新旋转后节点的平衡因子

3. 步骤

插入操作的步骤：

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

创建一个遍历树的当前节点指针

创建当前遍历节点的父节点的指针

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

循环查找插入位置

情况1：当前遍历到的节点的键 < 要插入的键 —> “继续寻找”

情况2：当前遍历到的节点的键 > 要插入的键 —> “继续寻找”

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

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

创建要插入的节点

将新节点连接到二叉搜索树中

情况1：新节点的键 < 父节点的键

情况2：新节点的键 > 父节点的键

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

更新新插入节点的父节点

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

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为旋转中心）：

提升左子节点：将parent的左子节点subL提升为新的根节点。

处理"悬挂"子树：subL的右子树subLR需要重新挂接到parent的左子树。

更新父子关系：调整各节点的_parent指针，维护三叉链结构。

3. 步骤

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

记录parent的左子节点的“指针

记录parent的左子节点的右子节点的“指针

记录parent的父节点的“指针

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

调整parent和subLR的关系

调整parent和subL的关系

调整根节点或祖父节点的子树指向

情况1：parent节点是根节点 —> 调整根节点

情况2：parent节点不是根节点 —> 调整祖父节点的子树指向

更新平衡因子 —> 右单旋后subL和parent的平衡因子均为0

4. 图示

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

在这里插入图片描述

上图展示的是以 10 为根的树结构，其中 a、b、c 抽象为三棵高度为 $h （ h \geq 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为旋转中心）：

提升右子节点：将parent的右子节点subR提升为新的根节点。

处理"悬挂"子树：subR的左子树subRL需要重新挂接到parent的右子树。

更新父子关系：调整各节点的_parent指针，维护三叉链结构。

3. 步骤

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

记录parent的右子节点的“指针

记录parent的右子节点的左子节点的“指针”

记录parent的父节点的“指针”

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

调整parent和subRL的关系

调整parent和subR的关系

调整根节点或祖父节点的子树指向

情况1：parent节点是根节点 —> 调整根节点

情况2：parent节点不是根节点 —> 调整祖父节点的子树指向

更新平衡因子 —> 左单旋后subR和parent的平衡因子均为0

4. 图示

在这里插入图片描述

上面的图展示的是以 10 为根的树结构，其中 a、b、c 被抽象为三棵高度为 $h （ h \geq 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 (l o g n)$

2. 核心

左右双旋的核心操作：

对subL执行左单旋：

将subL的右子节点subLR提升为新根

subLR的左子树subLRL挂接到subL的右子树

对parent执行右单旋：

将subLR提升为整棵子树的根

subLR的原右子树subLRR挂接到parent的左子树

更新父子关系：

调整各节点的_parent指针，确保三叉链结构正确

更新平衡因子：

根据插入位置（subLR的左 / 右子树），分情况修正subLR、subL、parent的平衡因子为 0 或 ±1

3. 步骤

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

记录parent的右子节点的“指针”

记录parent的右子节点的左子节点的“指针”

记录parent的右子节点的左子节点的“平衡因子”

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

首先对当前的节点的右子树进行“右单旋”

然后对当前的节点进行“左单旋”

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

情况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 (l o g n)$

2. 核心

右左双旋的核心操作：

对subR执行右单旋：

将subR的左子节点subRL提升为新根

subRL的左子树subRLR挂接到subR的左子树

对parent执行左单旋：

将subRL提升为整棵子树的根

subRL的原左子树subRLL挂接到parent的右子树

更新父子关系：

调整各节点的_parent指针，确保三叉链结构正确

更新平衡因子：

根据插入位置（subRL的左 / 右子树），分情况修正subRL、subR、parent的平衡因子为 0 或 ±1

3. 步骤

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

记录parent的左子节点的“指针”

记录parent的左子节点的右子节点的“指针”

记录parent的左子节点的右子节点的“平衡因子”

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

首先对当前的节点的左子树进行“左单旋”

然后对当前的节点进行“右单旋”

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

情况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 (l o 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> ---> Node
    typedef 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> ---> Node
	typedef 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：新插入节点是左子节点 ---> 父节点的平衡因子 -1
			if (current == parent->_left)
			{
				parent->_bf--; // 插入到左子树，左子树高度+1，平衡因子-1
			}

			//位置2：新插入节点是右子节点 ---> 父节点的平衡因子 +1
			else
			{
				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的平衡因子均为0
		subL->_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的平衡因子均为0
		subR->_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;
}

运行结果：

在这里插入图片描述

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

【AVL树】目录

前言：

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

1. 什么是AVL树？

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

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

4. 什么是平衡因子？

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

一、查找操作

1. 步骤

2. 简述

二、插入操作

1. 本质

2. 简述

3. 步骤

4. 图示

三、删除操作

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

单旋

一、右单旋

1. 条件

2. 核心

3. 步骤

4. 图示

二、左单旋

1. 条件

2. 核心

3. 步骤

4. 图示

双旋

一、左右双旋

1. 条件

2. 核心

3. 步骤

4. 图示

二、右左双旋

1. 条件

2. 核心

3. 步骤

4. 图示

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

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

一、节点的存储结构

二、树的存储结构

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

头文件：AVLTree.h

测试文件：Test.cpp

运行结果：

网站公告

今日签到

热门文章

最新发布