-
【C++】AVL树（动图详解）
一、前言
在上一篇文章中对 set、multiset、map、multimap 进行了简单的介绍，在其文档介绍中发现，这几个容器都有一个共同点：其底层都是借助二叉搜索树来实现的。但是==二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成为单支树==，时间复杂度会退化成 O(N) ，因此 set、map 等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。那么今天就让我们对 set 和 map 的底层结构一探究竟。
二、AVL树的概念（引入bf）
二叉搜索树虽然可以缩短查找的效率，但是如果数据有序或者接近有序，二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率就会变得低下。
因此，两位俄罗斯的数学家 G.M.Adelson-Velskii 和E.M.Landis 在 1962 年发明了一种解决上述问题的方法：当向二叉搜索树中插入新节点后，如果能保证每个节点的左右子树高度之差的绝对值不超过 1（超过 1 需要对树中的结点进行旋转，后续会讲，也被叫做动手术），即可降低树的高度，从而减少平均搜索长度。
一颗 AVL 树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是 AVL 树。
- 左右子树高度之差（简称平衡因子）的绝对值不超过 1（-1、0、1）。
下面是一个AVL树加上平衡因子（balance factor）的图，其中比节点大的放在右边，比节点小的放在左边，平衡因子的计算是通过右子树的高度-左子树的高度：
小Tips：如果一颗二叉搜索树是高度平均的，它就是 AVL 树。如果它有 n 个结点，其高度可保持在 O(log2^n)，搜索时间复杂度为 O(log2^n)。平衡二叉搜索树中平衡并不是说要让平衡因子始终保持 0，这是做不到的，以两个结点为例，根节点的平衡因子只可能是 1 或者 -1，不可能是 0。二叉搜索树在实际中基本不太可能实现完全平衡，但是理论上可以，即满二叉树。后面我们学的多叉平衡搜索树在现实中可以做到完全平衡。
三、AVL节点树的定义
我们接下来就准备手撕 AVL 树了，关键点在于俩个地方：
- 二叉搜索树的插入
- 更新平衡因子
template<class K, class V> struct AVLTreeNode { AVLTreeNode(const pair<K, V>& kv = pair<K, V>()) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) {} pair<K, V> _kv;//存储key和value AVLTreeNode<K, V>* _left = nullptr;//指向左孩子 AVLTreeNode<K, V>* _right = nullptr;//指向右孩子 AVLTreeNode<K, V>* _parent = nullptr;//指向父亲结点 int _bf = 0;//平衡因子 };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
节点为什么置空？
在AVL树中有很多的节点需要封装，而且对于没有值的节点一定要置空，将来我们单旋的时候有一个小插曲 if(SUbL) 如果我们初始化的时候没有置空的话，这个条件的书写很明显就是不对的
为什么引入parent节点？
使AVL树变成三叉链，是为了方便将来沿着路径一直向上更新，当然有利有弊：往回找的时候方便了，修改的时候麻烦了，除了修改孩子，还得修改双亲
平衡因子的引入：
最重要的还是平衡因子的封装加入AVL树节点定义的大家庭
四、AVL树的基本框架
template<class K, class V> class AVLTree { typedef AVLTreeNode<K, V> Node; private: Node* _root = nullptr; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
我们把上面结构体定义出来的AVLTreeNode
私有变量是我们的根节点 _root
五、AVL树的旋转
正常来说，应该先写插入再写旋转，但是由于插入代码中，更新平衡因子的时候需要调用旋转的接口，在不同的情况有不同的旋转方式，但是我们还不了解旋转，所以我书写的时候先书写的是旋转
首先，凡事皆有原则，我们的旋转也不例外：
- 子树左右高度不超过1
- 旋转过程中必须保持它是搜索树
- 更新调整孩子节点的平衡因子
- 降低这颗子树的高度
这个原则必须牢记于心，这样的话更有利于帮助我们理解后续的四种旋转
5.1左单旋（新节点插入较高右子树的右侧—右右：左单旋）
左单旋的定义：新节点插入较高右子树的右侧—右右：左单旋
动图中，我们的a，b，c分别代表==子树==，并不是节点，所以接下来我们举俩个具体的a，b，c例子，以及抽象图的总结
例一（h==0）
例二（h==1）
由于我们上方说到，我们的旋转都是满足我们的旋转四大原则的，杭哥在讲这个例子的时候说：b（也就是45）放在30的右边是正好满足二叉搜索树，但是我想难道60左边放25不可以吗？
后来我想了想，发现60的左侧的数字，一定是（30，60），而不是（0，60），所以b一定放在30右侧满足旋转规则这个问题告一段落
例三（抽象图）
等学到后期，看抽象图的困难程度就会大大降低，在本图中，我们有很多变量，都是为了和接下来的代码进行匹配
ppNode：担心旋转树为子树，从而旋转时丢失根与上方联系所创造出来的节点
parent：是旋转的函数参数，也是这个子树（或者树）旋转前的根
SubR：parent的右侧
SubRL：parent的右侧的左侧
以上如此多节点的设置，正是为了保证节点的丢失，以及三叉链中不光更新孩子，还得更新父亲的特性
代码讲解
根据上方小羊精美的图，我们不难写出以下代码：
void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right=subRL; subR->_left=parent; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
这段代码是我自己在没理解旋转之前写的天花板代码，但是还有很多问题我并没有考虑：
1. 我只更新了孩子节点，也就是说我只做了向下分配
2. 我的parent节点已经丢失，所以也得向上分配（这里有个小插曲）
3. 如果这个树是局部子树怎么办？
4. AVL 树最根本的平衡因子更新没有体现
根据以上问题，我们还得继续写出代码
1.更新双亲节点
根据抽象图，我们可以看出：b的_parent节点变成了parent也就是30，parent 的 _parent 节点变成了 SUbR ，也就是30的双亲变成了60
subRL->_parent = parent; parent->_parent = subR;- 1
- 2
这个时候小插曲来了：我们的b是一个子树，如果子树b为空，它还有双亲节点吗？所以我们得用if条件判断一下
但是为什么parent不用判断是否为空？ 实则在抽象图中就可以明白，为什么赋予这俩个变量30和60，就是说明parent和SubR不可为空，否则旋转问题无法继续讨论
if (subRL！=nullptr) { subRL->_parent = parent; } parent->_parent = subR;- 1
- 2
- 3
- 4
- 5
2.处理局部子树问题
由于我们的parent节点在旋转的过程中已经不是该树的根了，所以一开始初始化的时候，记得记录30的双亲节点
void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; Node* ppNode=parent->_parent;//这里 parent->_right=subRL; subR->_left=parent; //双亲 if (subRL！=nullptr) { subRL->_parent = parent; } parent->_parent = subR; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
这里分俩种情况：
- 是独立子树，那么就更新_root节点，并且将其 _parent 节点置空
- 如果是局部子树，若为ppNode左子树，就让其left连接SubR；若为ppNode右子树，就让其right连接SubR
//判断是否为局部子树 需要在parent被修改之前 写出ppNode if(ppNode==nullptr) { //说明是完整的树 _root=subR; _root->_parent=nullptr; } else { if(ppNode->_left==parent)//虽然parent被旋转了 但是上层的ppNode还是连着parent节点 哈哈 当年的自己提出这个问题 现在的我自己解决了 { ppNode->_left=subR; } else { ppNode->_right=subR; } //这里还有一句话 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
这个时候，else语句中还是只有向下分配，所以别忘了加上subR->_parent = ppNode;
3.更新平衡因子
30和60的平衡因子全部为0，也就是parent和SubR的_bf为0
parent->_bf = subR->_bf = 0;- 1
4.代码汇总
void RotateL(Node* parent) { //俩个孩子 三个双亲 好好品这句话 //1.更新孩子节点（向下分配） Node* subR = parent->_right; Node* subRL = subR->_left; Node* ppNode=parent->_parent;//为了避免是局部子树 parent->_right=subRL; subR->_left=parent; //2.更新双亲节点（往回分配） if(subRL!=nullptr)//往回分配的小插曲 空节点没有双亲节点 { subRL->_parent=parent; } parent->_parent=subR; //3.判断是否为局部子树 需要在parent被修改之前 写出ppNode if(ppNode==nullptr) { //说明是完整的树 _root=subR; _root->_parent=nullptr; } else { if(ppNode->_left==parent)//虽然parent被旋转了 但是上层的ppNode还是连着parent节点 { ppNode->_left=subR; } else { ppNode->_right=subR; } subR->_parent = ppNode; } //4.更新平衡因子 parent->_bf=subR->_bf=0;//更新平衡因子 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
代码总结（俩孩子三双亲）
我们在写AVL旋转的时候，一定要格局打开：我们在旋转树内的节点的时候，殊不知根节点已经岌岌可危，所以这就是局部子树的问题，而且向下分配完了别忘了向上分配，三叉链使得往上找轻松了，但也使得旋转时维护树的成本变高了
AVL的代码逻辑可以理解成俩个孩子三个双亲：因为我们的局部子树其实也是双亲问题
同时别忘了b子树的小插曲，而且局部子树 else 的时候也容易忘记向上分配，同时最后也别忘了平衡因子的更新
5.2左单旋（新节点插入较高左子树的左侧—左左：右单旋）
例一（h==0）
例二（h==1）
例三（抽象图）
代码总结（代码解释见左单旋）
void RotateR(Node* parent) { //俩个孩子 三个双亲 好好品这句话 //1.更新孩子节点（向下分配） Node* subL=parent->_left; Node* subLR=subL->_right; Node* ppNode=parent->_parent;//为了避免是局部子树 parent->_left=subLR; subL->_right=parent; //2.更新双亲节点（往回分配） if(subLR!=nullptr)//往回分配的小插曲 空节点没有双亲节点 { subLR->_parent=parent; } parent->_parent=subL; //3.判断是否为局部子树 需要在parent被修改之前 写出ppNode if(ppNode==nullptr) { //说明是完整的树 _root=subL; _root->_parent=nullptr; } else { if(ppNode->_left==parent)//虽然parent被旋转了 但是上层的ppNode还是连着parent节点 哈哈 当年的自己提出这个问题 现在的我自己解决了 { ppNode->_left=subL; } else { ppNode->_right=subL; } subL->_parent = ppNode;//局部子树else总会忘记向上分配 } //4.更新平衡因子 parent->_bf=subL->_bf=0;//更新平衡因子 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
5.3左右双旋（新节点插入较高左子树的右侧—左右：先左单旋再右单旋）
先说结论：我们需要对parent->left进行左单旋 再对parent进行右单旋即可
为什么我们需要引入左右单旋这个场景呢？我们的普通单旋为什么解决不了问题了，请看以下这些情况
例一（h==0）
先把弯的缕直，再进行单旋
例二（h==1）
例三（抽象图）
代码讲解
此时我们可以基本写出以下代码：
void RotateLR(Node* parent) { // Node* subL=parent->_left; // Node* subLR=subL->_right; RotateL(parent->_left); RotateR(parent); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
但是非常遗憾的是：我们的抽象图看似汇集了所有情况，实则只有60节点左侧插入的情况，但是左右双旋的平衡因子更新本质上是有三种情况的：
- 60的左节点插入
- 60的右节点插入
- 60本身就是插入节点
我们将这个状态的SubLR的平衡因子记录下来为bf 因为旋转完之后，我们很难考察是哪个位置插入了节点，所以在旋转之前记录bf
从以上情况分析平衡因子就不再吃力了，完整代码如下：
void RotateLR(Node* parent) { Node* subL=parent->_left; Node* subLR=subL->_right; int bf=subLR->_bf;//为了判读平衡因子改变的三种情况 RotateL(parent->_left); RotateR(parent); if(bf==-1)//subLR左子树插入 { subL->_bf=0; subLR->_bf=0; parent->_bf=1; } if(bf==1)//subLR右子树插入 { subL->_bf=-1; subLR->_bf=0; parent->_bf=0; } if(bf==0)//本身就是新节点被插入 { subL->_bf=0; subLR->_bf=0; parent->_bf=0; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
总结：分析平衡因子的时候，应该同时对照着插入前和插入俩次旋转完成后的图像去判断平衡因子的大小
5.4右左双旋（新节点插入较高右子树的左侧—右左：先右单旋再左单旋）
先对parent的right进行右单旋，再对parent进行左单旋即可
在这个例子中，我们只绘出抽象图，以方便对照着写出代码，不在举出详细例子
抽象图
接着，我们需要讨论出旋转之前的以及插入到60的左，60的右，包括60是新节点的三种情况的平衡因子，这里不再赘述，类似左右双旋
void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(parent->_right); RotateL(parent); 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 if (bf == 0) { subR->_bf = 0; subRL->_bf = 0; parent->_bf = 0; } else { assert(false); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
六、AVL树的插入
AVL树插入结点时有以下三个步骤：
- 按照二叉搜索树的插入方法，找到待插入位置。
- 找到待插入位置后，将待插入结点插入到树中。
- 更新平衡因子，如果出现不平衡，则需要进行旋转。
因为AVL树本身就是一棵二叉搜索树，因此寻找结点的插入位置是非常简单的，按照二叉搜索树的插入规则：
- 待插入结点的key值比当前结点小就插入到该结点的左子树。
- 待插入结点的key值比当前结点大就插入到该结点的右子树。
- 待插入结点的key值与当前结点的key值相等就插入失败。
如此进行下去，直到找到与待插入结点的key值相同的结点判定为插入失败，或者最终走到空树位置进行结点插入。
bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(kv); if (parent->_kv.first < kv.first) { parent->_right = cur; cur->_parent = parent; } else { parent->_left = cur; cur->_parent = parent; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
以上这段代码只是单纯的插入代码，如果我们不更新平衡因子的话，那么AVL存在的意义也就没有了，所以我们得更新平衡因子
与二叉搜索树插入结点不同的是，AVL树插入结点后需要更新树中结点的平衡因子，因为插入新结点后可能会影响树中某些结点的平衡因子。
由于一个结点的平衡因子是否需要更新，是取决于该结点的左右子树的高度是否发生了变化，因此插入一个结点后，该结点的祖先结点的平衡因子可能需要更新。
所以我们插入结点后需要倒着往上更新平衡因子，更新规则如下：
- 新增结点在parent的右边，parent的平衡因子 ++
- 新增结点在parent的左边，parent的平衡因子 --。
每更新完一个结点的平衡因子后，都需要进行以下判断：（注：这里的parent不是最上面那个节点，新增节点的祖先是parent）
- 如果parent的平衡因子等于-1或者1，表明还需要继续往上更新平衡因子。
- 如果parent的平衡因子等于0，表明无需继续往上更新平衡因子了。
- 如果parent的平衡因子等于-2或者2，表明此时以parent结点为根结点的子树已经不平衡了，需要进行旋转处理。（得动手术）
判断理由说明：
parent更新后的平衡因子 分析 -1或1 只有0经过 ++或-- 操作后会变成-1/1，说明新结点的插入使得parent的左子树或右子树增高了，即改变了以parent为根结点的子树的高度，从而会影响parent的父结点的平衡因子，因此需要继续往上更新平衡因子。 0（恰好插入较矮的那边） 只有-1/1经过 ++或-- 操作后会变成0，说明新结点插入到了parent左右子树当中高度较矮的一棵子树，插入后使得parent左右子树的高度相等了，此操作并没有改变以parent为根结点的子树的高度，从而不会影响parent的父结点的平衡因子，因此无需继续往上更新平衡因子。 -2或2 此时parent结点的左右子树高度之差的绝对值已经超过1了，不满足AVL树的要求，因此需要进行旋转处理。 注意： parent的平衡因子在插入更新之前只可能是-1/0/1（AVL树中每个结点的左右子树高度之差的绝对值不超过1）。 而在最坏情况下，我们更新平衡因子时会一路更新到根结点。例如下面这种情况：（所以我们的代码得写成while(parent)）
三叉链结构的优势体现： 由于我们插入结点后需要倒着往上进行平衡因子的更新，所以我们将AVL树结点的结构设置为了三叉链结构，这样我们就可以通过父指针找到其父结点，进而对其平衡因子进行更新。当然，我们也可以不用三叉链结构，可以在插入结点时将路径上的结点存储到一个栈当中，当我们更新平衡因子时也可以通过这个栈来更新祖先结点的平衡因子，但是相对较麻烦。
若是在更新平衡因子的过程当中，出现了平衡因子为-2/2的结点，这时我们需要对以该结点为根结点的树进行旋转处理，而旋转处理分为四种，在进行分类之前我们首先需要进行以下分析：
我们将插入结点称为cur，将其父结点称为parent，那么我们更新平衡因子时第一个更新的就是parent结点的平衡因子，更新完parent结点的平衡因子后，若是需要继续往上进行平衡因子的更新，那么我们必定要执行以下逻辑：
cur = parent; parent = parent->_parent;- 1
- 2
这里我想说明的是：当parent的平衡因子为-2/2时，cur的平衡因子必定是-1/1而不会是0。
理由如下：
若cur的平衡因子是0，那么cur一定是新增结点，而不是上一次更新平衡因子时的parent，否则在上一次更新平衡因子时，会因为parent的平衡因子为0而停止继续往上更新。
那么我们按照cur是新增节点来进行推导，就会发现有bug：
如果cur是新增结点的话，其父结点的平衡因子更新后一定是-1/0/1，而不可能是-2/2，因为新增结点最终会插入到一个空树当中，在新增结点插入前，其父结点的状态有以下两种可能：
- 其父结点是一个左右子树均为空的叶子结点，其平衡因子是0，新增结点插入后其平衡因子更新为-1/1。
- 其父结点是一个左子树或右子树为空的结点，其平衡因子是-1/1，新增结点插入到其父结点的空子树当中，使得其父结点左右子树当中较矮的一棵子树增高了，新增结点后其平衡因子更新为0。
综上所述，当parent的平衡因子为-2/2时，cur的平衡因子必定是-1/1而不会是0。
根据此结论，我们可以将旋转处理分为以下四类：
- 当parent的平衡因子为-2，cur的平衡因子为-1时，进行右单旋。（左左）
- 当parent的平衡因子为-2，cur的平衡因子为1时，进行左右双旋。（左子树右侧）
- 当parent的平衡因子为2，cur的平衡因子为-1时，进行右左双旋。（右子树左侧）
- 当parent的平衡因子为2，cur的平衡因子为1时，进行左单旋。（右右）
并且，在进行旋转处理后就无需继续往上更新平衡因子了，因为旋转后树的高度变为插入之前了，即树的高度没有发生变化，也就不会影响其父结点的平衡因子了。
加上更新平衡因子后的插入完整代码：
bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(kv); if (parent->_kv.first < kv.first) { parent->_right = cur; cur->_parent = parent; } else { parent->_left = cur; cur->_parent = parent; } // 1、更新平衡因子 while (parent) // parent为空，也就更新到根 { // 新增在右，parent->bf++; // 新增在左，parent->bf--; if (cur == parent->_left) { parent->_bf--; } else { parent->_bf++; } // 是否继续更新依据：子树的高度是否变化 // 1、parent->_bf == 0说明之前parent->_bf是 1 或者 -1 // 说明之前parent一边高一边低，这次插入填上矮的那边，parent所在子树高度不变，不需要继续往上更新 // 2、parent->_bf == 1 或 -1 说明之前是parent->_bf == 0，两边一样高，现在插入一边更高了， // parent所在子树高度变了，继续往上更新 // 3、parent->_bf == 2 或 -2，说明之前parent->_bf == 1 或者 -1，现在插入严重不平衡，违反规则 // 就地处理--旋转 // 旋转： // 1、让这颗子树左右高度不超过1 // 2、旋转过程中继续保持他是搜索树 // 3、更新调整孩子节点的平衡因子 // 4、让这颗子树的高度跟插入前保持一致 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 && cur->_bf == 1) { RotateL(parent); } else if (parent->_bf == -2 && cur->_bf == -1) { RotateR(parent); } else if (parent->_bf == -2 && cur->_bf == 1) { RotateLR(parent); } else if (parent->_bf == 2 && cur->_bf == -1) { RotateRL(parent); } else { assert(false); } break; } else { assert(false); } } return true; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
七、AVL树相关的一些测试
AVL 树是在二叉搜索树的基础上加入了平衡的限制，因此要验证 AVL 树，可以分为两步：
- 验证其为二叉搜索树。如果中序遍历可以得到一个有序的序列，就说明为二叉搜索树。
- 验证其为平衡树。每个结点左右子树高度差的绝对值不超过 1 。其次检查结点的平衡因子是否计算正确。
public: //中序 void Inorder() { return _Inorder(_root); } //检测平衡因子 bool IsBlance() { return _IsBalance(_root); } private: //中序 void _Inorder(Node* root) { if (root == nullptr) { return; } _Inorder(root->_left); cout << root->_kv.first << ' '; _Inorder(root->_right); return; } //求树的高度 int Height(Node* root) { if (root == nullptr) { return 0; } int leftHeight = Height(root->_left); int rightHeight = Height(root->_right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } //检测平衡因子 bool _IsBalance(Node* root) { if (root == nullptr) { return true; } int leftHeight = Height(root->_left); int rightHeight = Height(root->_right); if (rightHeight - leftHeight != root->_bf) { cout << "平衡因子异常:" << root->_bf << endl; return false; } return abs(leftHeight - rightHeight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
/*test.c*/ int main() { int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; wcy::AVLTree<int, int> t; for (auto e : a) { t.Insert(make_pair(e, e)); t.Inorder(); cout << endl; if (t.IsBlance()) { cout << "成功插入:" << e << endl; } else { cout << e << "插入失败" << endl; } } return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
八、完整代码
AVL.h
#include#include #include #include 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; int _bf; // balance factor AVLTreeNode(const pair<K, V>& kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) {} }; template<class K, class V> struct AVLTree { typedef AVLTreeNode<K, V> Node; public: /*----------------------------------------------插入------------------------------------------------*/ bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(kv); if (parent->_kv.first < kv.first) { parent->_right = cur; cur->_parent = parent; } else { parent->_left = cur; cur->_parent = parent; } // 1、更新平衡因子 while (parent) // parent为空，也就更新到根 { // 新增在右，parent->bf++; // 新增在左，parent->bf--; if (cur == parent->_left) { parent->_bf--; } else { parent->_bf++; } // 是否继续更新依据：子树的高度是否变化 // 1、parent->_bf == 0说明之前parent->_bf是 1 或者 -1 // 说明之前parent一边高一边低，这次插入填上矮的那边，parent所在子树高度不变，不需要继续往上更新 // 2、parent->_bf == 1 或 -1 说明之前是parent->_bf == 0，两边一样高，现在插入一边更高了， // parent所在子树高度变了，继续往上更新 // 3、parent->_bf == 2 或 -2，说明之前parent->_bf == 1 或者 -1，现在插入严重不平衡，违反规则 // 就地处理--旋转 // 旋转： // 1、让这颗子树左右高度不超过1 // 2、旋转过程中继续保持他是搜索树 // 3、更新调整孩子节点的平衡因子 // 4、让这颗子树的高度跟插入前保持一致 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 && cur->_bf == 1) { RotateL(parent); } else if (parent->_bf == -2 && cur->_bf == -1) { RotateR(parent); } else if (parent->_bf == -2 && cur->_bf == 1) { RotateLR(parent); } else if (parent->_bf == 2 && cur->_bf == -1) { RotateRL(parent); } else { assert(false); } break; } else { assert(false); } } return true; } /*----------------------------------------------旋转------------------------------------------------*/ void RotateL(Node* parent) { //俩个孩子 三个双亲 好好品这句话 //1.更新孩子节点（向下分配） Node* subR = parent->_right; Node* subRL = subR->_left; Node* ppNode=parent->_parent;//为了避免是局部子树 parent->_right=subRL; subR->_left=parent; //2.更新双亲节点（往回分配） if(subRL!=nullptr)//往回分配的小插曲 空节点没有双亲节点 { subRL->_parent=parent; } parent->_parent=subR; //3.判断是否为局部子树 需要在parent被修改之前 写出ppNode if(ppNode==nullptr) { //说明是完整的树 _root=subR; _root->_parent=nullptr; } else { if(ppNode->_left==parent)//虽然parent被旋转了 但是上层的ppNode还是连着parent节点 { ppNode->_left=subR; } else { ppNode->_right=subR; } subR->_parent = ppNode; } //4.更新平衡因子 parent->_bf=subR->_bf=0;//更新平衡因子 } void RotateR(Node* parent) { //俩个孩子 三个双亲 好好品这句话 //1.更新孩子节点（向下分配） Node* subL=parent->_left; Node* subLR=subL->_right; Node* ppNode=parent->_parent;//为了避免是局部子树 parent->_left=subLR; subL->_right=parent; //2.更新双亲节点（往回分配） if(subLR!=nullptr)//往回分配的小插曲 空节点没有双亲节点 { subLR->_parent=parent; } parent->_parent=subL; //3.判断是否为局部子树 需要在parent被修改之前 写出ppNode if(ppNode==nullptr) { //说明是完整的树 _root=subL; _root->_parent=nullptr; } else { if(ppNode->_left==parent)//虽然parent被旋转了 但是上层的ppNode还是连着parent节点 哈哈 当年的自己提出这个问题 现在的我自己解决了 { ppNode->_left=subL; } else { ppNode->_right=subL; } subL->_parent = ppNode; } //4.更新平衡因子 parent->_bf=subL->_bf=0;//更新平衡因子 } void RotateLR(Node* parent) { Node* subL=parent->_left; Node* subLR=subL->_right; int bf=subLR->_bf;//为了判读平衡因子改变的三种情况 RotateL(parent->_left); RotateR(parent); if(bf==-1)//subLR左子树插入 { subL->_bf=0; subLR->_bf=0; parent->_bf=1; } if(bf==1)//subLR右子树插入 { subL->_bf=-1; subLR->_bf=0; parent->_bf=0; } if(bf==0)//本身就是新节点被插入 { subL->_bf=0; subLR->_bf=0; parent->_bf=0; } } void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(parent->_right); RotateL(parent); 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 if (bf == 0) { subR->_bf = 0; subRL->_bf = 0; parent->_bf = 0; } else { assert(false); } } void Inorder() { _Inorder(_root); } void _Inorder(Node* root) { if (root == nullptr) return; _Inorder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _Inorder(root->_right); } int Height(Node* root) { if (root == nullptr) return 0; int lh = Height(root->_left); int rh = Height(root->_right); return lh > rh ? lh + 1 : rh + 1; } bool IsBalance() { return IsBalance(_root); } bool IsBalance(Node* root) { if (root == nullptr) { return true; } int leftHeight = Height(root->_left); int rightHeight = Height(root->_right); if (rightHeight - leftHeight != root->_bf) { cout <<root->_kv.first<<"平衡因子异常" << endl; return false; } return abs(rightHeight - leftHeight) < 2 && IsBalance(root->_left) && IsBalance(root->_right); } private: Node* _root = nullptr; }; //void TestAVLTree() //{ // //int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 }; // //int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; // //int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; // AVLTree - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287
- 288
- 289
- 290
- 291
- 292
- 293
- 294
- 295
- 296
- 297
- 298
- 299
- 300
- 301
- 302
- 303
- 304
- 305
- 306
- 307
- 308
- 309
- 310
- 311
- 312
- 313
- 314
- 315
- 316
- 317
- 318
- 319
- 320
- 321
- 322
- 323
- 324
- 325
- 326
- 327
- 328
- 329
- 330
- 331
- 332
- 333
- 334
- 335
- 336
- 337
- 338
- 339
- 340
- 341
- 342
- 343
- 344
- 345
- 346
- 347
- 348
- 349
- 350
- 351
- 352
- 353
- 354
- 355
- 356
- 357
- 358
- 359
- 360
- 361
- 362
- 363
- 364
- 365
- 366
- 367
- 368
- 369
AVL.cpp
#include"AVL.h" #include#include using namespace std; /*test.c*/ int main() { int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; AVLTree<int, int> t; for (auto e : a) { t.Insert(make_pair(e, e)); t.Inorder(); cout << endl; if(t.IsBalance()) { cout << "成功插入:" << e << endl; } else { cout << e << "插入失败" << endl; } } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
九、难点总结
旋转的四个原则
- 子树左右高度不超过1
- 旋转过程中必须保持它是搜索树
- 更新调整孩子节点的平衡因子
- 降低这颗子树的高度
在进行旋转处理后就无需继续往上更新平衡因子了
因为旋转后树的高度变为插入之前了，即树的高度没有发生变化，也就不会影响其父结点的平衡因子了
旋转口诀是插入较高… 不要把这个较高给忽略掉
写代码的时候，头脑要清楚，不要忘了回溯parent的值（向上分配）
插入代码更新平衡因子的条件是while（parent）
对于单旋，利用俩孩子三双亲原则；对于双旋，难点在于平衡因子更新，得画出插入前和旋转后的图分析平衡因子（三种情况）
双旋得提前记录subLR或者subRL的bf（旋转完了都找不到了）
单旋得提前记录parent的_parent，也就是代码中的ppNode
单旋的时候，解决局部子树问题时，总会忘记向上分配
希望给大家带来帮助！！
-
相关阅读:
File 类和 IO 流
Windows 遇到 taskkill 删除某个进程后，该进程显示timewait，导致会有一个类似缓存的问题，无法及时更新应用
MySQL学习笔记：模型2
测试用例设计方法之等效类，边界值
知识付费系统源码，【开源版】免费知识付费平台搭建部署
华清远见上海中心22071班
SpringBoot学习小结之分库分表、读写分离利器Shardingsphere
vue的指令和插值总结
[ue5]建模场景学习笔记（1）——混合材质
ArrayList与顺序表（2）
- 原文地址：https://blog.csdn.net/weixin_62985813/article/details/134459529
