当前位置：首页 > article >正文

C++进阶：AVL树

article 2025/1/7 19:09:54

一：AVL树的介绍

AVL树（Adelson-Velsky and Landis树）是一种自平衡的二叉搜索树（BST），它通过在每个节点维护一个平衡因子，确保树的高度差不超过1，从而使得树的操作（如查找、插入和删除）的时间复杂度保持在 O(log⁡n) 的水平。

因为我们在普通的二叉树插入的时候，也许会出现下图这种极端的情况：

那么如果此时搜索5或4的时候时间复杂度就为O(N)。那么为了解决这种情况苏联的两位数学家就发明了AVL树。

在AVL树树中有个关键的概念，那就是平衡因子。在二叉树中的每个节点都拥有一个平衡因子。对于每个节点，平衡因子定义为该节点左子树的高度减去右子树的高度。AVL树要求每个节点的平衡因子值只能是 -1、0 或 1，若平衡因子的绝对值超过 1，说明该节点失去平衡，需要进行旋转操作。

二：C++中的AVL树的使用

在C++中有这样两个容器：map与set。

set：

set是一个只存储key的容器，每个key在 set 中必须是唯一的，并且 set 会根据key的大小自动排序（当使用中序打印的时候是升序排序）。set 用于需要存储唯一key并快速查找的场景，如果有多个相同key存储set中，set只会存储第一个相同的key。

下图是官方文档的set的构造函数：

空容器构造函数（默认构造函数）
构造一个空的容器，容器内没有任何元素。
范围构造函数
使用范围 [first, last) 中的元素构造容器，容器中的每个元素都是根据该范围中的相应元素来构造的。
拷贝构造函数
通过拷贝另一个 set 容器 x 来构造当前容器。

要注意的是set是一个类模板，在进行实例化的时候需要添加实例化参数。

以上是set的库函数，可以看到与set的库函数与list，vector的库函数基本类似，并且使用也是类似的。所以如果list与vector使用熟练那么set也同样能熟练使用。以下是set的简单示例

map：

map与set的区别在于，map在key的基础上增加了一个val，也就是说map是一个<key,val>的模型。而map在用于存储key，val的值中，并不是直接在类里定义了一个key和一个val值。而是用pair容器进行存储key，val,而map里面存有一个pair。

pair：是一个模板类，定义在 <utility> 头文件中。它包含两个元素（成员变量），分别是 first 和 second，这两个成员变量可以是任何类型。first用于存储第一个值，second用于存储第二个值

map的使用方法与set类似，所以小编在这里就不过多的展开诉说，但map与set不同的一点是map是支持"[ ]"重载。

通过上图示例，我们可以简单了解一下map的[ ]的重载：

首先看这段代码ms["apple"] = "苹果"; 其中"apple" 可以理解为key值，"苹果"可以理解为val值。那么这段代码的意思可以先理解为先在ms里查找有无"apple"的节点。如果有就将"apple"节点里的val值修改为"苹果"。如果没有就插入"apple"节点，并将val初始化为"苹果"。后面的代码代码也是同理。并且通过打印也能证明这一说法。

三：模拟实现AVL树

上图我们将AVL树的框架搭建出来，在TreeNode中除了我们熟知的left和right，还新增加了一个parent的指针，用于找到父亲节点，以及一个平衡因子(当然这并不是必须的)。在AVLTree类里只有一个根节点 r_oot 。

上图是一个AVL树的插入函数，当传入一个pair的时候我们就进行比较，如果_root为空那么直接new一个根节点。如果不是根节点就定义cur与parent的结点指针。接着通过while循环，如果传进 kv 的 first 比当前 cur 的 first 大，cur就往右边走，反之。parent用于保存当前节点的父亲节点。

当cur为null的时说明当前此树没有重复的节点，就可以new一个新的kv节点，到这步还没有结束，现在节点有了,就需要将父子节点进行链接，如果 parent 的 first 大于 cur 的 first 那么此时 cur就在 parent 的左边，将 parent 的左边链接 cur ，反之。最后不要忘记 cur 的 parent 指针指向 parent 节点。

那么当节点插入完成后就要开始更新平衡因子，如果cur是在parent的左边插入就将平衡因子--，如果是在右边插入就++。当更新完平衡因子时就检查当前平衡因子的值，如果为0则表示当前子树绝对平衡不需要旋转，直接退出循环即可。如果为1或-1，那么则表明当前子树的高度差为1需要在向上更新平衡因子。如果当前平衡因子为2或-2就表明当前高度差为|2|需要发生旋转。

1：右单旋

就像上图一样我们插入-1节点后，开始通过父亲指针向上进行更新平衡节点。如果平衡节点为1或-1，此时可以理解为节点正处于亚健康状态，需要向上更新，当更新到此节点的平衡因子为0的时候就证明是绝对平衡，健康的状态，直接停止更新。当发现平衡因子会-2的时候此时是绝对的左边高所以就需要向右旋转。

向右旋转可以抽象的理解为吧右边的节点往下摁

现在我们将平衡因子为-2的节点定义为parent，将parent的左节点定义为subL，将subL的右节点定义为subLR。接下来重点来了

1.将parent的左指向subLR

2.将subL的右指向parent

3.旋转完成后我们可以看到此时subL与parent的的树已经绝对平衡了，subL成为新的头节点。并更新他们的平衡因子为0。

我们将右旋写成一个函数，并parent传入。为了方便旋转我们先定义出subL与subLR指针。

首先先将parent节点的left指向subLR,subL节点的right指针指向parent。接着需要先判断subLR是否为空，因为可能出现下图情况。

如果为空我们将subLR的父节点指向parent的时候就会报错。接着我们定义出pParent指针用于指向parent的parent。并将parent节点里的_parent指针指向subL。

接下来，判断pParent节点，如果节点为NULL则表面parent为根节点，那么直接更新_root节点为subL，并将subL的parent节点置为NULL。

如果parent节点不为NULL，那么就去链接pParent节点与subL节点之间的关系，并将subL的parent节点指向pParent。

2：左单旋

当绝对的右边高的时候就需要发生左旋。而左旋的概念与右旋基本类似，就不过多的赘述。

当旋转完成后，parent子树与subR子树的将绝对平衡，最后更新他们的平衡因子为0。

3：左右双旋

左右双旋是什么情况呢？其实就是当节点并不是存粹的左边高，而是有分叉的情况，如果我们直接使用右旋转就会发生下图的情况：

所以此时必须需要先进行一次左旋，使子树变成绝对的左边高，再进行一次右旋，才能变成平衡树。

当然到这里还没有结束，我们还需要搞清楚一个问题，我们一开始在subLR插入新增节点的时候还需要搞清楚一个问题，这个新增节点是在subLR的左边插入还是在右边插入，就比如上图，新增节点为4，是在subLR的左边插入，所以当旋转完成后新增节点会在subL的右边，我们会发现parent的平衡因子是为1的。