深入理解C++系列（15）——AVL树

⭐️博主：此生决int-@CSDN博客

速胜派就是最大的投降派！！！

🔥热门专栏🔥

深入理解 C++ 系列｜算法系列

快速复习系列｜Java 速通系列

上期回顾

上一篇我们主要学习了如何使用map和set，了解了他们相关的接口，做了相关的一些算法题，那么今天，我们就来看看，怎么保证二叉搜索树的高度不会太高，达到logN的效率的呢？那要我们学完今天的AVL树就知道了！，

AVL树

AVL树简介

1，AVL树概念：

简单来说就是，二叉搜索树里面任何一颗子树的左右子树高度差不超过1
名字由来：得名于它的发明者G. M. Adelson-Velsky和E. M. Landis是两个前苏联的科学家，

AVL树的实现

AVL树的结构

相比与我们之前实现的二叉搜索树，AVL树新增了：
1，指向父母的指针parent
2，平衡因子——bf（左右子树高度差，我们这里用右减左）

template<classK,classV>structAVLTreeNode{// 需要parent指针，后续更新平衡因子可以看到pair<K,V>_kv;AVLTreeNode<K,V>*_left;AVLTreeNode<K,V>*_right;AVLTreeNode<K,V>*_parent;int_bf;// balance factor};

我们可以发现，AVL树的每颗子树的平衡因子只能为1，-1，0

insert插入函数的实现⭐️⭐️⭐️⭐️⭐️

插入的过程很简单：首先还是跟二叉搜索树一样，先找到插入位置；
代码：和之前二叉搜索树时的一样

boolInsert(constpair<K,V>&kv){//插入已经有的值就会返回falseif(_root==nullptr){_root=newNode(kv);returntrue;}Node*cur=_root;Node*parent=nullptr;while(cur){if(kv.first>cur->_kv.first){parent=cur;cur=cur->_right;}elseif(kv.first<cur->_kv.first){parent=cur;cur=cur->_left;}else{returnfalse;}}

然后我们会发现，插入后会形成两种情况。

情况一是插入之后，它仍然是 AVL 树。
例如，在刚刚那副图里再插入一个11，仍然是AVV树

情况二是插入之后，它不满足 AVL 树的性质，这时候我们就要做出调整。
例如，插入13

好，我们一种情况一种情况来分析：
我们首先来想一下，我们要维护哪些东西：首先肯定是新增的那个平衡因子，还有父节点（parent），左右孩子，还有储存的值 kv。其中，这个平衡因子是比较难维护的。我们来单独看一下平衡因子怎么维护。

平衡因子的维护

首先，平衡因子是由右子树的高度减去左子树的高度得到的。

所以，如果一棵树在插入一个节点之后，它的左右子树高度都不变，那么它的平衡因子也不会改变。所以，平衡因子肯定跟高度有关。所以，在插入一个节点之后，该节点所有祖先节点的平衡因子都有可能受到影响，我们都需要进行更新。
但是，我们观察可以得出一个结论：
如果插入之后，有一棵子树它的根节点的平衡因子变为了 0，那么它的所有祖先节点的平衡因子都不用继续更新了
证明：
插入之后，它的平衡因子变为了 0。那么，插入之前，它的平衡因子肯定是1或者 -1。在是一和 -1 的时候，肯定是左右两边有一边多了一个，新增的那个元素就插入在了少的那一边，抹平了那个差距，但整体它的树的高度是没有变的
所以，那棵子树的高度是没有变的。即：插入之后平衡因子变为 0 的那棵子树，它的高度肯定是不会变的。
那么，对于插入节点之后，父母的平衡因子变为 1 或 -1 的这种情况：
我们知道：它插入之前肯定是 0，插入后变为 1 或 -1，那么它的高度肯定是增加了 1。

那么，接下来我们只需要看它是它父母的左子树还是右子树，根据它是它父母的左子树还是右子树来更新它父母的平衡因子。
第三种情况：插入之后，一直往上更新的时候，父节点的平衡因子变为了 2 或者 -2。那么这个情况比较复杂，就要利用到旋转来解决
好，那么我们就可以把插入之后的平衡因子进行归纳分类：

平衡因子的几种情况：

1，插入后是0：
不用继续向上更新
2，插入后是1，-1
根据是父母的左子树还是右子树，来更新父母的平衡因子
3，插入后是2，-2
情况比较多，要通过旋转来解决
我们先把前两种情况的代码写出来：

cur=newNode(kv);if(kv.first>parent->_kv.first){parent->_right=cur;parent->_bf++;}elseif(kv.first<parent->_kv.first){parent->_left=cur;parent->_bf--;}else{assert(false);//防御性编程，理论上不可能走到这里}cur->_parent=parent;cur->_bf=0;//更新平衡因子// 根据父母的平衡因子来移动//0,不用动//1，-1，不管是1还是-1，肯定是0变过来的，然后，肯定该子树的高度+1了，所以，看父母是父母的左孩子还是右孩子while(parent){if(parent->_bf==0)break;elseif(parent->_bf==1||parent->_bf==-1){cur=parent;parent=parent->_parent;if(parent==nullptr)break;//爷爷为空，那么就是到根节点了，直接breakif(parent->_left==cur){parent->_bf--;}elseif(parent->_right==cur){parent->_bf++;}elseassert(false);}

插入后，平衡因子为2和-2时

这里会分为四种情况，对应四种旋转方式，分别是：

1. 左单旋
2. 右单旋
3. 左右双旋
4. 右左双旋
   其中后面两个双旋就是上面两个单旋的组合，所以一定要先搞懂单选，再去看多选。搞懂单旋之后，双旋就会比较简单。

右单旋

当一棵树它的左子树特别高(bf=-2)的时候，它就会采用右单旋
下面这张图非常的关键！！

单从结果上来理解：

代码实现：

//所有旋转的情景是，元素已经插入，然后，超级不平衡，即parent的平衡因子=2/-2// 右单旋voidRotateR(Node*parent){//注意为空的几种情况// pParent为空// subLR 为空//Node*pParent=parent->_parent;Node*sub=parent;Node*subL=sub->_left;Node*subLR=subL->_right;sub->_left=subLR;if(subLR)//subLR可能为空，要特判subLR->_parent=sub;subL->_right=sub;sub->_parent=subL;if(pParent==nullptr){_root=subL;//parent也要更新！！！subL->_parent=nullptr;}elseif(pParent->_left==sub){pParent->_left=subL;subL->_parent=pParent;//别忘了更新parent}elseif(pParent->_right==sub){pParent->_right=subL;subL->_parent=pParent;}elseassert(false);//平衡因子更新subL->_bf=0;sub->_bf=0;}

左单旋

与右单旋刚好相反，它的右子树特别高（bf=2），所以要进行左单旋。理解了右单旋，左单旋就很好理解了。

依旧是：把 parent 的右孩子作为新的根。

然后，parent 右孩子的左孩子裁剪下来，作为parent的右孩子，

最后，原来的 parent 作为新节点的左孩子。

左右双旋

顾名思义，“左右双旋”就是先进行一次左旋，再进行一次右旋
那么，我们就先来分析一下，到底是什么情况下要用单旋，什么情况下要用双旋。

其他两个同理：
左右单旋具体是怎么实现的呢？

简单来讲呢，双旋分为三种情况：

情况1：插入subLR的左子树

单从结果的角度来讲就是：

情况2：插入subLR的右子树（与情况一差不多）

情况3，特殊情况，h=0，即subLR就是插入节点

代码：

// 左右双旋，即先左旋在右旋voidRotateLR(Node*parent){Node*sub=parent;Node*subL=parent->_left;Node*subLR=subL->_right;intbf=subLR->_bf;//先存储一下，RotateL(subL);RotateR(sub);//更新平衡因子//subLR->_bf = 0;//这个节点成为新的根了，那么，肯定是0//其他两个，要根据插入节点是subLR的左右节点来判断//不能再rotate后根据平衡因子判断，因为这里已经变了！！！！！！！！// if (subLR->_bf == -1)//也就是插入图示里面的e，也就是8的左边if(bf==-1)//也就是插入图示里面的e，也就是8的左边{sub->_bf=1;subL->_bf=0;}elseif(bf==1){sub->_bf=0;subL->_bf=-1;}elseif(bf==0){sub->_bf=0;subL->_bf=0;}elseassert(false);subLR->_bf=0;//因为要以它为依据判断，所以，后更新}

右左双旋（同理，会了左右就会右左）

情况1

情况2

情况3，特殊情况，h=0

insert完整实现代码

// 插入boolInsert(constpair<K,V>&kv){//插入已经有的值就会返回falseif(_root==nullptr){_root=newNode(kv);returntrue;}Node*cur=_root;Node*parent=nullptr;while(cur){if(kv.first>cur->_kv.first){parent=cur;cur=cur->_right;}elseif(kv.first<cur->_kv.first){parent=cur;cur=cur->_left;}else{returnfalse;}}cur=newNode(kv);if(kv.first>parent->_kv.first){parent->_right=cur;parent->_bf++;}elseif(kv.first<parent->_kv.first){parent->_left=cur;parent->_bf--;}else{assert(false);//防御性编程，理论上不可能走到这里}cur->_parent=parent;cur->_bf=0;//更新平衡因子// 根据父母的平衡因子来移动//0,不用动//1，-1，不管是1还是-1，肯定是0变过来的，然后，肯定该子树的高度+1了，所以，看父母是父母的左孩子还是右孩子while(parent){if(parent->_bf==0)break;elseif(parent->_bf==1||parent->_bf==-1){cur=parent;parent=parent->_parent;if(parent==nullptr)break;//爷爷为空，那么就是到根节点了，直接breakif(parent->_left==cur){parent->_bf--;}elseif(parent->_right==cur){parent->_bf++;}elseassert(false);}elseif(parent->_bf==2||parent->_bf==-2){//旋转if(parent->_bf==-2&&cur->_bf==-1){RotateR(parent);//旋转后，不用向上更新了，break;}elseif(parent->_bf==-2&&cur->_bf==1){RotateLR(parent);break;}elseif(parent->_bf==2&&cur->_bf==1){RotateL(parent);break;}elseif(parent->_bf==2&&cur->_bf==-1){RotateRL(parent);break;}elseassert(false);}elseassert(false);}returntrue;}

左单旋代码

// 左单旋voidRotateL(Node*parent){Node*pparent=parent->_parent;Node*subR=parent->_right;Node*subRL=subR->_left;parent->_right=subRL;if(subRL)subRL->_parent=parent;subR->_left=parent;parent->_parent=subR;if(pparent==nullptr){_root=subR;//parent也要更新！！！subR->_parent=nullptr;}elseif(pparent->_left==parent){pparent->_left=subR;subR->_parent=pparent;}elseif(pparent->_right==parent){pparent->_right=subR;subR->_parent=pparent;}elseassert(false);//更新平衡因子parent->_bf=0;subR->_bf=0;}

右左双旋代码

voidRotateRL(Node*sub){Node*subR=sub->_right;Node*subRL=subR->_left;intbf=subRL->_bf;RotateR(subR);RotateL(sub);// 更新平衡因子if(bf==0){sub->_bf=0;subR->_bf=0;}elseif(bf==1)// 新节点插入在 subRL 的右边{sub->_bf=-1;// sub 变成了左子树，没有右孩子subR->_bf=0;// subR 左右平衡}elseif(bf==-1)// 新节点插入在 subRL 的左边{sub->_bf=0;// sub 左右平衡subR->_bf=1;// subR 只有右孩子}elseassert(false);subRL->_bf=0;}

IsBalanceTree判断一颗树是不是AVL树

计算右子树高度，计算左子树高度，然后相减。

判断差值的绝对值是否小于 2，以及该差值是否等于平衡因子 BF即可。
代码：

// 平衡检测辅助函数bool_IsBalanceTree(Node*root){if(root==nullptr)returntrue;intleft_height=_Height(root->_left);intright_height=_Height(root->_right);intbf=right_height-left_height;if(_IsBalanceTree(root->_left)&&_IsBalanceTree(root->_right)&&bf<2&&bf>-2){//还要判断平衡因子if(root->_bf!=bf){cout<<"平衡因子错误："<<endl;returnfalse;}returntrue;}returnfalse;}

高度函数怎么求？

以前学过，就是递归：先递归左子树的高度，再递归右子树的高度，然后再加 1

总结：

全是重点！

下期预告

红黑树

结语

本文到此结束，感谢大家的阅读！如果觉得本文对你有所帮助，欢迎点赞、收藏、关注，也欢迎在评论区一起交流讨论。
也欢迎订阅我的
深入理解 C++系列：从语法入门到底层原理，系统掌握现代 C++
算法系列：从入门到精通，蓝桥杯、ACM、LeetCode 与面试算法全路线
快速复习系列：知识梳理、查漏补缺，考前冲刺必备
Java 速通系列：已学 C 语言，快速上手 Java，轻松备战期末考试