⭐️博主此生决int-CSDN博客速胜派就是最大的投降派热门专栏深入理解 C 系列算法系列快速复习系列Java 速通系列文章目录上期回顾AVL树AVL树简介1AVL树概念AVL树的实现AVL树的结构insert插入函数的实现⭐️⭐️⭐️⭐️⭐️平衡因子的维护平衡因子的几种情况插入后平衡因子为2和-2时右单旋左单旋左右双旋情况1插入subLR的左子树情况2插入subLR的右子树与情况一差不多情况3特殊情况h0即subLR就是插入节点右左双旋同理会了左右就会右左情况1情况2情况3特殊情况h0insert完整实现代码左单旋代码右左双旋代码IsBalanceTree判断一颗树是不是AVL树总结下期预告红黑树结语上期回顾上一篇我们主要学习了如何使用map和set了解了他们相关的接口做了相关的一些算法题那么今天我们就来看看怎么保证二叉搜索树的高度不会太高达到logN的效率的呢那要我们学完今天的AVL树就知道了AVL树AVL树简介1AVL树概念简单来说就是二叉搜索树里面任何一颗子树的左右子树高度差不超过1名字由来得名于它的发明者G. M. Adelson-Velsky和E. M. Landis是两个前苏联的科学家AVL树的实现AVL树的结构相比与我们之前实现的二叉搜索树AVL树新增了1指向父母的指针parent2平衡因子——bf左右子树高度差我们这里用右减左templateclassK,classVstructAVLTreeNode{// 需要parent指针后续更新平衡因子可以看到pairK,V_kv;AVLTreeNodeK,V*_left;AVLTreeNodeK,V*_right;AVLTreeNodeK,V*_parent;int_bf;// balance factor};我们可以发现AVL树的每颗子树的平衡因子只能为1-10insert插入函数的实现⭐️⭐️⭐️⭐️⭐️插入的过程很简单首先还是跟二叉搜索树一样先找到插入位置代码和之前二叉搜索树时的一样boolInsert(constpairK,Vkv){//插入已经有的值就会返回falseif(_rootnullptr){_rootnewNode(kv);returntrue;}Node*cur_root;Node*parentnullptr;while(cur){if(kv.firstcur-_kv.first){parentcur;curcur-_right;}elseif(kv.firstcur-_kv.first){parentcur;curcur-_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情况比较多要通过旋转来解决我们先把前两种情况的代码写出来curnewNode(kv);if(kv.firstparent-_kv.first){parent-_rightcur;parent-_bf;}elseif(kv.firstparent-_kv.first){parent-_leftcur;parent-_bf--;}else{assert(false);//防御性编程理论上不可能走到这里}cur-_parentparent;cur-_bf0;//更新平衡因子// 根据父母的平衡因子来移动//0,不用动//1-1不管是1还是-1肯定是0变过来的然后肯定该子树的高度1了所以看父母是父母的左孩子还是右孩子while(parent){if(parent-_bf0)break;elseif(parent-_bf1||parent-_bf-1){curparent;parentparent-_parent;if(parentnullptr)break;//爷爷为空那么就是到根节点了直接breakif(parent-_leftcur){parent-_bf--;}elseif(parent-_rightcur){parent-_bf;}elseassert(false);}插入后平衡因子为2和-2时这里会分为四种情况对应四种旋转方式分别是左单旋右单旋左右双旋右左双旋其中后面两个双旋就是上面两个单旋的组合所以一定要先搞懂单选再去看多选。搞懂单旋之后双旋就会比较简单。右单旋当一棵树它的左子树特别高(bf-2)的时候它就会采用右单旋下面这张图非常的关键单从结果上来理解代码实现//所有旋转的情景是元素已经插入然后超级不平衡即parent的平衡因子2/-2// 右单旋voidRotateR(Node*parent){//注意为空的几种情况// pParent为空// subLR 为空//Node*pParentparent-_parent;Node*subparent;Node*subLsub-_left;Node*subLRsubL-_right;sub-_leftsubLR;if(subLR)//subLR可能为空要特判subLR-_parentsub;subL-_rightsub;sub-_parentsubL;if(pParentnullptr){_rootsubL;//parent也要更新subL-_parentnullptr;}elseif(pParent-_leftsub){pParent-_leftsubL;subL-_parentpParent;//别忘了更新parent}elseif(pParent-_rightsub){pParent-_rightsubL;subL-_parentpParent;}elseassert(false);//平衡因子更新subL-_bf0;sub-_bf0;}左单旋与右单旋刚好相反它的右子树特别高bf2所以要进行左单旋。理解了右单旋左单旋就很好理解了。依旧是把 parent 的右孩子作为新的根。然后parent 右孩子的左孩子裁剪下来作为parent的右孩子最后原来的 parent 作为新节点的左孩子。左右双旋顾名思义“左右双旋”就是先进行一次左旋再进行一次右旋那么我们就先来分析一下到底是什么情况下要用单旋什么情况下要用双旋。其他两个同理左右单旋具体是怎么实现的呢简单来讲呢双旋分为三种情况情况1插入subLR的左子树单从结果的角度来讲就是情况2插入subLR的右子树与情况一差不多情况3特殊情况h0即subLR就是插入节点代码// 左右双旋即先左旋在右旋voidRotateLR(Node*parent){Node*subparent;Node*subLparent-_left;Node*subLRsubL-_right;intbfsubLR-_bf;//先存储一下RotateL(subL);RotateR(sub);//更新平衡因子//subLR-_bf 0;//这个节点成为新的根了那么肯定是0//其他两个要根据插入节点是subLR的左右节点来判断//不能再rotate后根据平衡因子判断因为这里已经变了// if (subLR-_bf -1)//也就是插入图示里面的e也就是8的左边if(bf-1)//也就是插入图示里面的e也就是8的左边{sub-_bf1;subL-_bf0;}elseif(bf1){sub-_bf0;subL-_bf-1;}elseif(bf0){sub-_bf0;subL-_bf0;}elseassert(false);subLR-_bf0;//因为要以它为依据判断所以后更新}右左双旋同理会了左右就会右左情况1情况2情况3特殊情况h0insert完整实现代码// 插入boolInsert(constpairK,Vkv){//插入已经有的值就会返回falseif(_rootnullptr){_rootnewNode(kv);returntrue;}Node*cur_root;Node*parentnullptr;while(cur){if(kv.firstcur-_kv.first){parentcur;curcur-_right;}elseif(kv.firstcur-_kv.first){parentcur;curcur-_left;}else{returnfalse;}}curnewNode(kv);if(kv.firstparent-_kv.first){parent-_rightcur;parent-_bf;}elseif(kv.firstparent-_kv.first){parent-_leftcur;parent-_bf--;}else{assert(false);//防御性编程理论上不可能走到这里}cur-_parentparent;cur-_bf0;//更新平衡因子// 根据父母的平衡因子来移动//0,不用动//1-1不管是1还是-1肯定是0变过来的然后肯定该子树的高度1了所以看父母是父母的左孩子还是右孩子while(parent){if(parent-_bf0)break;elseif(parent-_bf1||parent-_bf-1){curparent;parentparent-_parent;if(parentnullptr)break;//爷爷为空那么就是到根节点了直接breakif(parent-_leftcur){parent-_bf--;}elseif(parent-_rightcur){parent-_bf;}elseassert(false);}elseif(parent-_bf2||parent-_bf-2){//旋转if(parent-_bf-2cur-_bf-1){RotateR(parent);//旋转后不用向上更新了break;}elseif(parent-_bf-2cur-_bf1){RotateLR(parent);break;}elseif(parent-_bf2cur-_bf1){RotateL(parent);break;}elseif(parent-_bf2cur-_bf-1){RotateRL(parent);break;}elseassert(false);}elseassert(false);}returntrue;}左单旋代码// 左单旋voidRotateL(Node*parent){Node*pparentparent-_parent;Node*subRparent-_right;Node*subRLsubR-_left;parent-_rightsubRL;if(subRL)subRL-_parentparent;subR-_leftparent;parent-_parentsubR;if(pparentnullptr){_rootsubR;//parent也要更新subR-_parentnullptr;}elseif(pparent-_leftparent){pparent-_leftsubR;subR-_parentpparent;}elseif(pparent-_rightparent){pparent-_rightsubR;subR-_parentpparent;}elseassert(false);//更新平衡因子parent-_bf0;subR-_bf0;}右左双旋代码voidRotateRL(Node*sub){Node*subRsub-_right;Node*subRLsubR-_left;intbfsubRL-_bf;RotateR(subR);RotateL(sub);// 更新平衡因子if(bf0){sub-_bf0;subR-_bf0;}elseif(bf1)// 新节点插入在 subRL 的右边{sub-_bf-1;// sub 变成了左子树没有右孩子subR-_bf0;// subR 左右平衡}elseif(bf-1)// 新节点插入在 subRL 的左边{sub-_bf0;// sub 左右平衡subR-_bf1;// subR 只有右孩子}elseassert(false);subRL-_bf0;}IsBalanceTree判断一颗树是不是AVL树计算右子树高度计算左子树高度然后相减。判断差值的绝对值是否小于 2以及该差值是否等于平衡因子 BF即可。代码// 平衡检测辅助函数bool_IsBalanceTree(Node*root){if(rootnullptr)returntrue;intleft_height_Height(root-_left);intright_height_Height(root-_right);intbfright_height-left_height;if(_IsBalanceTree(root-_left)_IsBalanceTree(root-_right)bf2bf-2){//还要判断平衡因子if(root-_bf!bf){cout平衡因子错误endl;returnfalse;}returntrue;}returnfalse;}高度函数怎么求以前学过就是递归先递归左子树的高度再递归右子树的高度然后再加 1总结全是重点下期预告红黑树结语本文到此结束感谢大家的阅读如果觉得本文对你有所帮助欢迎点赞、收藏、关注也欢迎在评论区一起交流讨论。也欢迎订阅我的深入理解 C系列从语法入门到底层原理系统掌握现代 C算法系列从入门到精通蓝桥杯、ACM、LeetCode 与面试算法全路线快速复习系列知识梳理、查漏补缺考前冲刺必备Java 速通系列已学 C 语言快速上手 Java轻松备战期末考试愿每一次敲下键盘都比昨天更进一步愿每一行代码落下都让未来多一种可能