网站备案 多久,做自己的网站流量怎么,装修图库大全图片,柯城建设局网站Hello#xff0c;大家好#xff0c;这一篇博客我们来讲解一下数据结构中的AVL树这一部分的内容#xff0c;AVL树属于是数据结构的一部分#xff0c;顾名思义#xff0c;AVL树是一棵特殊的搜索二叉树#xff0c;我们接下来要讲的这篇博客是建立在了解搜索二叉树这个知识点… Hello大家好这一篇博客我们来讲解一下数据结构中的AVL树这一部分的内容AVL树属于是数据结构的一部分顾名思义AVL树是一棵特殊的搜索二叉树我们接下来要讲的这篇博客是建立在了解搜索二叉树这个知识点的基础之上的因此我在这里建议大家可以先去看看我之前写过的那片有关搜索二叉树内容的博客为了方便大家寻找链接就放到下面了 搜索二叉树效率的进一步upgrate-CSDN博客文章浏览阅读2k次点赞171次收藏116次。Hello大家好我们关于C的大部分语法知识就可以宣告结束了不知道聪明的你有没有掌握扎实呢好了不管各位掌握的情况如何我们从这一篇博客开始就要进入下一个阶段了这个阶段就是大家期待已久的高阶数据结构的部分对于数据结构这个 东西 想必大家对它定是又爱又恨哈哈哈但是不要担心相信大家在看过这一篇博客之后定然会明白的。https://blog.csdn.net/2301_81390458/article/details/143648002?spm1001.2014.3001.5502https://blog.csdn.net/2301_81390458/article/details/143648002?spm1001.2014.3001.5502
目录
1 AVL树的概念
2 AVL树的实现 2.1 AVL树的结构 2.2 AVL树的插入 2.2.1 AVL树插入值的具体过程 2.2.2 平衡因子的更新 2.2.2.1 更新原则 2.2.2.2 更新停止条件 2.2.2.3 插入节点及更换平衡因子的代码实现 2.3 右旋转 2.3.1 旋转的原则 2.3.2 右单旋 2.3.3 代码实现右单旋 2.4 左旋转(左单旋) 2.4.1 代码实现左单旋 2.5 左右双旋 2.5.1 前情提要 2.5.2 深度解析 2.5.3 代码实现左右双旋 2.6 右左双旋 2.6.1 旋转方法 2.6.2 代码实现右左双旋 2.7 AVL树的查找 2.8 AVL树的删除 1 AVL树的概念 1.AVL树是最先发明的自平衡二叉查找树AVL是一棵空树或者是具备下列性质的二叉搜索树它的左右子树均为AVL树且左右子树的高度差的绝对值不超过1。AVL树是一棵高度平衡的二叉搜索树。 2.AVL树得名于它的发明者G.M.Adelson-Velsky和E.M.Landis是两个前苏联的科学家他们在1962年的论文中发表了它。 3.为了更好地去了解AVL树的实现我们这里还需引入一个平衡因子的概念每个节点都有一个平衡因子任何节点的平衡因子等于右子树的高度减去左子树的高度右 - 左也就是说任何节点的平衡因子等于 0 / -1 / 1 AVL树并不是需要平衡因子但是这里有了平衡因子的话就可以更方便我们去观察和控制树是否平衡就像一个风向标一样。 4.思考一下为什么AVL树是高度平衡的搜索二叉树要求高度不超过1而不是高度差是0呢0不是更好地平衡吗其实通过下面地两幅图我们就不难发现不是我们不想这样设计而是在有些情况下是做不到高度差为0的比如说当有一棵树是2个节点4个节点等情况下高度差最好就是1无法作为高度差是0的这种情况。 5.AVL树整体节点的数量和分布和完全二叉树类似高度可以控制在log2 ( N ) 相比于二叉搜索树有了本质的提升。
2 AVL树的实现 2.1 AVL树的结构 通过我们前面的学习可知AVL树它其实就是一棵二叉搜索树只不过相较于一棵普通的二叉搜索树而言AVL树它的左右子树高度差的绝对值不会超过1是一棵自平衡二叉树且它是一个个独立的节点构成的各个节点之间是由指针连接起来的所以我们首先来看AVL树各个节点的结构
templateclass K,class V
struct AVLTreeNode//这里我们之所以选用struct类是因为我们在实现后面的各个操作时(如插入删除查找等)都要通过节点内部的各个指针才可以完成因此这里选用struct因为它默认的访问权限是public当然也可以使用class但是必须加public才可以。
{pairK, V _kv;//AVL树中的每个节点中都是要存放元素的_kv变量就是用来存放元素的AVL树它也是一棵二叉搜索树通过我们前面所学的二叉搜索树的两种key和key/value类型这里AVL树就相当于是key/value类型因为这个类型更好key/value可以充当key类型去用而key不可以充当key/value去用因此AVL树的元素为pairK,V类型的变量。AVLTreeNodeK, v* _left;AVLTreeNodeK, v* _right;//因为是二叉树所以每个节点中都必须含有两个指针一个指向左子树而另一个指向右子树。AVLTreeNodeK, v* _parent;//AVL树中还需要有一个_parent指针指向当前节点的父节点后续进行更新平衡因子这一操作时我们就会用到这个指针的用法我们后面再说这里先跳过。int _bf;//balance factor(平衡因子)用来判断以这个节点为根节点的那棵树是否平衡了。AVLTreeNode(const pairK, V kv)//拷贝构造函数:_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){ }//这里的默认构造和析构函数我们使用编译器自己生成的就足够我们使用了。
};
AVL树的框架
templateclass K,class V
class AVLTree//AVL树的结构(部分)
{typedef AVLTreeNodeK, v node;
public://......;主体函数部分这里先不写后面会慢慢地去进行补充。
private:node* root nullptr;//指向根节点地指针。
}; 2.2 AVL树的插入 2.2.1 AVL树插入值的具体过程 1.插入一个值按二叉搜索树的规则去进行插入操作。 2.新增节点以后只会影响祖先节点的高度也就是可能会影响部分祖先节点的平衡因子所以更新的是从当前这个新增节点到根节点路径上的平衡因子实际中最坏的情况下是必须要更新到根有些情况就只需要更新到中间就可以停止了具体情况我们下面再做详细的分析。 3.更新平衡因子后平衡因子符合0/-1/1就说明插入结束。 4.更新平衡因子过程中出现不平衡对不平衡子树进行旋转操作旋转这一步操作本质上是降低了子树的高度不会再影响上一层所以插入结束。后面会讲 2.2.2 平衡因子的更新 2.2.2.1 更新原则 1.平衡因子右子树的高度-左子树的高度。 2.只有子树高度变化才会影响当前节点的平衡因子。 3.插入一个节点会增加高度所以新增节点在parent的右子树上时parent的平衡因子新增节点在parent的左子树上时parent的平衡因子--。 4.parent所在子树的高度是否变化决定了是否会继续往上更新。 2.2.2.2 更新停止条件 1.更新后如果parent的平衡因子等于0更新中parent的平衡因子变化为1-0或者-1-0通过这个平衡因子的变化我们就可以知道更新前parent的子树是一边高一边低新增的节点被插入在了低的那边插入后parent所在的子树的高度不会变不会影响parent的父亲节点的平衡因子因此更新结束。 2.更新后parent节点的平衡因子等于1或者是-1更新时parent节点的平衡因子变化为0--1或者是0--1这里我们需要注意的是这个变化它是有一个前提的那就是必须要保证要插入的这棵树它必须是一棵AVL树既然是AVL树那么就说明这棵树中的所有的节点中的平衡因子的绝对值都是2的因此只有我们这里所说的这两种情况说明在插入之前以parent节点为根节点的那棵树的子树就会一边高一边低虽然子树一边高一边低但是以parent为根节点的这棵树它也符合AVL树的要求且高度增加了1但是以parent节点的父亲节点为根节点的这棵子树就不符合AVL树的要求了因为高度增加了1会影响parent节点的父亲节点的平衡因子因此要继续向上更新祖宗节点的平衡因子才可以。 3.更新后parent的平衡因子等于2或-2更新时平衡因子的变化为1-2或者是-1--2说明更新前以parent为根节点的树的子树一边高一边低新插入的那个节点被插在了高的那一边这样就会使parent所在的子树高的那边会变得更高进而破坏了平衡因而parent所在的子树就会不符合平衡的要求需要进行旋转处理旋转的目标有2个1.把parent子树旋转平衡。2.降低parent子树的高度。所以旋转后也不需要进行往上更新插入结束。 2.2.2.3 插入节点及更换平衡因子的代码实现
bool Insert(const pairK, V kv)
{if (_root nullptr){_root new node(kv);return true;}node* parent nullptr;//指向cur节点的父亲节点的指针。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;}else{parent-_left cur;}//以上所有的代码的解释均和前二叉搜索树那一篇博客中的插入部分所讲的内容是一样的大家如果有忘了的可以回忆一下。cur-_parent parent;//通过我们前面对AVL树的节点结构的仔细剖析我们可以得知其中的一个成员变量_parent指向的是当前这个节点的父亲节点是为了更新平衡因子所准备的而parent指针恰好就指向当前节点(要插入节点)的父亲节点因此让插入的新节点的_parent指针指向parent节点即可。//当程序进行到这里时就说明插入成功了接下来就该更新这个节点的各个指针节点的平衡因子了。while (parent ! nullptr)//要想更新这个节点的各个祖宗节点的平衡因子就只能按照来时的路一步步往回走(也就是通过节点中的_parent指针往回走)按照更新原则和更新停止条件走我们在进行更新平衡因子的操作时最坏的一个情况就是会一直更新到整棵AVL树的根节点(也就是_root指针指向的那个节点)按照我们的逻辑走的话更新完某一个节点的平衡因子后就要让parent指向这个节点中_parent成员变量所指向的那个节点......当parent指向_root时我们更新_root的平衡因子后parent就指向为空了此时就足以证明我们将从刚刚插入的那个节点开始的所有祖宗节点的平衡因子全部都更新完了相当于是插入完成了可以结束了因此这里以parent!nullptr这一条件结束更新平衡因子。{//更新平衡因子if (cur parent-_left)//如果新插入的节点在左边的话那么就说明新插入的这个节点的父亲节点的平衡因子要-1。{parent-_bf--;}else//(cur parent-_right);新插入的节点在右边那么就说明新插入的这个节点的父亲节点的平衡因子要1。{parent-_bf;}//根据我们前面所讲到的更新原则和更新停止条件的相关知识并不是插入的新节点的所有祖宗都需要更新平衡因子当更新后的平衡因子达到某个条件后就不需要再去更新父亲节点的平衡因子了更新就可以结束了那接下来我们就来看一下。if (parent-_bf 0)//就说明插入节点后让以parent这个节点为根节点的这棵树的左右子树平衡了(原来是一高一低不平衡)因此它的高度时没有变化的通过更新停止条件可知当parent-_bf为0时更新就可以结束了。{break;}else if (parent-_bf -1 || parent-_bf 1)//通过更新停止条件2可知这种情况下是导致了以parent为根的那棵树的左右子树高度发生了变化需要继续向上更新祖宗节点的平衡因子。{cur parent;parent parent-_parent;}else if (parent-_bf -2 || parent-_bf 2)//通过更新停止条件3可知这种情况下就需要旋转来解决了且旋转过后会恢复到插入节点以前的高度就和更新停止条件1差不多了因此操作过后就不用继续向上更新了插入结束。{//旋转处理还没学后面会讲。(通过我们后面的讲解学习之后我们可以知道旋转分为4种方式不同的插入方式对应不同的旋转方式因此我们应该还要判断一下它应用哪种旋转方式。)//......break;}else//防止要进行插入节点的这棵树本身就不是AVL树的情况{assert(false);//直接终止程序报错。}}//出了循环之后就说明要么是parent指向nullptr了要么是平衡因子更新完成了也就是插入完成了。return true;
} 2.3 右旋转 2.3.1 旋转的原则 1.保持二叉搜索树的规则。 2.让旋转的树从不平衡变为平衡其次会降低树的高度旋转分为4种左单旋 / 右单旋 / 左右双旋 / 右左双旋在我们接下来对旋转的讲解中会画图进行讲解在下面的图中有些节点我们这里给的是具体的值比如10和5等等一些节点用10和5是为了在这里能够更加方便地去进行讲解实际中是什么值其实都可以只要大小关系符合二叉搜索树的规则就可以了。 2.3.2 右单旋 1.下图中的第一幅图展示的是10为根节点的树由a/b/c抽象为三棵高度为h的子树h0a/b/c这三棵子树且均符合AVL树的要求。10这个节点可能是整棵树的根也可能是以整棵树中某个局部的子树的根。这里a/b/c是高度为h的子树是一种概括且抽象的表示它代表了所有右单旋的场景实际单旋形态由很多具体后面会进行一个详细的描述。 2.在a子树中插入一个新的节点就会导致a子树的高度从 h 变成了 h1 就要不断地到上面去更新平衡因子进而导致10的平衡因子从-1变成了-110为根节点的树左右高度差超过了1违反了平衡规则。10为根节点的树的左子树的高度太高了需要往右边旋转从而控制两棵树的平衡。 3.旋转的核心步骤因为5b子树的根节点的值10将b变成10的左子树10变成5的右子树而5这个节点则变成这棵树新的根这样一来新形成的子树也就符合了搜索树的规则控制了平衡同时还将这棵树的高度恢复到了插入之前的h2符合旋转规则。如果插入之前的10这棵树是一个局部子树的话旋转过后就不会再影响上一层了因此插入就结束了。 OK以上图中的过程就是我们旋转的比较具体的一个过程接下来我们来对a,b,c这三棵子树是什么来做一个简单的解答。 情况1插入前a/b/c的高度h0图中包含10和5这两个节点 情况2插入前a/b/c的高度h1 情况3插入前a/b/c高度h2 通过我们前面所学习的知识可知高度h2的子树分为了3种情况
上述所讲的过程中所说的b和c子树可以是x/y/z中的任意一种但是a只能是x假如a是y/z的话那么在插入一个新的节点后按照要求它y/z自己就要进行旋转操作大家在这里可以自已去画画图这样就有回到情况1中去了我们这里是想让10这个节点为旋转点进行右单旋操作由此观之只有a是x时插入后节点高度为h1a不用旋转此刻会引发以10这个节点旋转既然a是x那么插入的方式就有4种而b/c又是x/y/z将他们组合一下得出的结论是若插入前a/b/c的高度h2时总共有3*3*436种场景。 情况4插入前a/b/c高度h3AVL子树 通过情况4我们可以得知b和c可以是x/y-c中任意的一种情况一共有15*15种组合a的情况在这里和情况3中比较相似要确保在插入新的节点后a自身不会旋转这样的话a的最后一层叶节点的个数必须要大于等于3小于等于4这里要分情况考虑若为3最后一列有4种组合情况总计有4*4种插入情况大家可以自行画图这里就不做过多的解释了若是4总计有8种插入情况将它们全部组合一下得出的结论是若插入前a/b/c的高度h3时总计有15*15(84*4)5400种场景。 综上所述a/b/c的情况是什么其实有无数种情况还有许多场景h4h5...它们的解释说到底其实还是和上面的解释是差不多的因此就不多解释了如果大家有兴趣的话可以自行尝试去画一画。 2.3.3 代码实现右单旋
void RotateR(node* parent)//parent指针指向的是更新后的平衡因子为-2的那个节点并且parent的左子树的那个根节点的平衡因子为-1否则的话无法保证是左边高要进行右单旋操作若parent的左子树的那个根节点的平衡因子为1那么就是b高a低应该是去进行左单旋操作。
{//通过我们前面的讲解可知我们可以知道右单旋主要变换的就是parent(更新后平衡因子为-2的节点)parent的左子树的那个根节点(更新后平衡因子为-1的节点)以及b子树既让如此那么首先要先得到指向它们的指针。node* subL parent-_left;//parent的左子树的那个根节点。node* subLR subL-_right;//b子树的根节点。node* pParent parent-_parent;//这里我们暂时先对这句话代码做一个标记后面的代码分析会用到这句代码。parent-_left subLR;//先让parent的左指针指向b子树我们前面有分析到连接好后还要注意要连接一下_parent成员变量。if (subLR ! nullptr)//如果b子树为空的话就不需要连接_parent成员变量了因为空树没有节点。{subLR-_parent parent;//parent节点成为了b子树的新的父亲节点这里之所以要再判断一下subLR是否为空是为了让b子树重新认父亲因此需要访问subLR中的_parent成员变量若不判断的话如果在b子树是空树进行这一步操作时系统就会报错。}subL-_right parent;//根据前面的分析我们可知连接完b子树后接下来该subL了让subL节点为parent新的父亲节点。parent-_parent subL;//调整parent中的_parent成员变量。//OK,按道理说当程序走到这里时就已经旋转完成了但是事实上并没有完通过我们前面的分析可知parent节点可能是这棵AVL树的根节点但是也有极大的可能它是一棵局部的子树如果它是整棵AVL树的根节点的话让_root指向subL就可以结束了假如是一棵局部子树还要连接一下subL节点让它成为这棵AVL树新的根并且与旋转前parent的父节点连接。if (pParent ! nullptr)//在第6行代码中我们保留了旋转前parent的父节点的指针它的作用就体现在了这里。{_root subL;subL-_parent nullptr;//整棵AVL树最终的那个根节点的_parent成员变量是空的。}else//说明旋转之前parent树只是一个局部子树要和上一层连接。{if (pParent-_left parent)//因为我们这里暂时还未将subL作为这颗子树新的根因此parent此时还是和上一层连接着由此观之还是要靠parent指针去判断subL应该插在上一层的左边还是右边。{pParent-_left subL;}else{pParent-_right subL;}subL-_parent pParent;//更新一下subL的_parent成员变量。}subL-_bf parent-_bf 0;//通过我们前面的解析可知无论是那种情况最后subL和parent的平衡因子都会变为0因为高度恢复且两边最终都会回归平衡。
} 2.4 左旋转(左单旋) 1.下图中展示的是10为根的AVL树有a/b/c抽象为三颗高度为h的子树h0a/b/c均符合AVL树的要求。10可能会是整棵树的根也可能是一个整棵树中一棵局部子树的根。这里a/b/c指的是高度为h的子树是一种概括抽象的表示他代表了所有的左单旋的场景实际左单旋形态有很多种具体跟上面的右单旋的4中情况是类似的。 2.在a子树中插入一个新的节点导致a子树的高度由h变成了h1不断向上更新平衡因子就导致了10这个节点的平衡因子从1变成了2以10为根节点的这棵树的左右高度差超过了1因此需要往左边旋转从而控制两棵树的平衡。 3.旋转核心步骤因为10b子树的根的值15将b子树变成10节点的右子树10变成15的左子树15变成这棵树新的根符合搜索树的规则控制了平衡并同时将这棵树的高度恢复到了插入之前的h2符合旋转的原则如果插入之前10是整棵树的一个局部子树的话那么旋转之后就不会再影响上一层了这样插入就结束了。 2.4.1 代码实现左单旋
void RotateL(node* parent)//parent在这里的解释其实和右单旋中的解释一样它也指向的是更新后平衡因子为2的那个节点这里有一点我们需要注意一下就是只有当parent指向的那个节点的平衡因子为2且cur指向的那个节点的平衡因子为1才可以进行左单旋操作。
{node* subR parent-_right;node* subRL subR-_left;node* pParent parent-_parent;//上面这三行代码的解释和在有单旋中的解释相同方便起见这里就不再多写了。if (subRL ! nullptr)//与右单旋中的解释一样。{subRL-_parent parent;}subR-_left parent;//将parent连接到subR的左子树上。parent-_parent subR;//subR节点成为parent节点新的父亲节点。if (pParent ! nullptr){_root subR;//如果pParent为空的话就说明在旋转之前parent节点就是整棵树的根因此根据我们前面所讲的逻辑可知需要更换subR为新的根让_root指向subR就可以了。subR-_parent nullptr;}else{if (pParent-_left parent){pParent-_left subR;}else{pParent-_right subR;}subR-_parent pParent;}parent-_bf subR-_bf 0;
} 2.5 左右双旋 2.5.1 前情提要 我们在前面讲解的2种单旋方式它们的场景全部都是纯粹的一边高也就是说只有插入节点在5这个节点的左子树上或者插入节点在15这个节点的右子树上时我们使用单旋就可以使子树平衡其余情况下若只是使用单旋就不会平衡就如上图所示那样。 2.5.2 深度解析 1.通过上图我们可以看到在左边高时如果插入的位置不是在a子树而是在b子树中插入b子树的高度就会从h变成h1从而引发旋转按照我们的前面所讲的来看的话左边太高应该往右边旋转可是我们通过上图来看的话右旋之后无法解决问题我们的树它依然是不平衡的右单旋解决的是纯粹的左边高这种情况也就是说插入的新节点不仅属于以5这个节点为根节点的子树的左子树更是属于以10这个节点为根节点的左子树这才是纯粹的一边高但是插入在b子树中以10这个节点为根节点的子树不再是单纯的左边高对于以10这个节点为根节点的子树来说是左边高而对于以5这个节点为根节点的子树来说则是右边高对于这样的插入情况我们就需要用两次旋转才能解决首先以5节点为旋转点进行一个左单旋操作旋转完后再以10这个节点为旋转点进行一个右单旋操作这样这棵树就会平衡了。 从10这个节点的角度来看的话新插入的这个节点相当于是插入在b子树中但是以5这个节点为旋转点来看的话8这个节点就不算是在b子树中 2.上图为左右双旋中h0场景的分析下面我们将a/b/c子树抽象为高度h的AVL子树进行分析另外画图另外我们还需要把b子树的细节再进一步展开为8和左子树高度为h-1的e和f子树因为我们要以b的父亲节点5为旋转点进行左单旋操作而左单旋需要动b子树中的左子树。b子树中新增节点的位置又有不同平衡因子更新的细节也因为这个新增节点的位置不同而不同通过观察8这个节点的平衡因子的不同这里我们还要分为三个场景去分析 场景1h1时新增节点在e子树中 h1时新增节点插入在8节点的左子树e子树e子树的高度从h-1变为h并不断更新8-5-10的各个节点的平衡因子会引发旋转其中8的平衡因子为-1旋转后8和5的平衡因子变为010的平衡因子为-1。 场景2h1时新增节点在f子树中 h1时新增节点插入在f子树中使得f子树的高度从h-1变为了h并且会不断更新8-5-10节点的平衡因子引发了旋转其中8的平衡因子为1旋转后8和10的平衡因子为05的平衡因子为-1。 场景3h0时a/b/c三棵子树均为空树 h0时a//b/c三棵子树均为空树b子树自己就是一个新增节点不断更新5-10节点的平衡因子引发旋转。 OK通过我们对上述3种情况的分析我们可以得知当我们将节点新插入到b子树上时我们此时若使用单旋的话就无法产生我们想要的结果无法使子树平衡因此在这里我们要进行的使双旋操作。通过我们双旋具体的旋转方法可知我们这里要将b子树展开要用到b子树的根节点由于将b子树展开之后形成e和f两棵子树而e和f这两棵子树上都可以用来插入新的节点这样就会生出情况1和情况2两种插入方式通过图中展示出来的旋转后的结果来看虽然最后的结果都是让子树重新归于平衡了但是子树中不同位置插入的节点的平衡因子更新后的结果也是不同的当然了还有情况3之所以会出现情况3这种情况是因为旋转发生的前提一定使插入节点之后如果子树不平衡的话才会发生的而情况3的8节点刚好插入在了要进行双旋的位置上这样的话就会使得无法精准地判断处平衡因子的大小基于这种情况需要我们分开讨论。 2.5.3 代码实现左右双旋
void RotateLR(node* parent)//parent指向更新后平衡因子变为-2的那个节点。
{node* subL parent-_left;//通过去前面的解释可知我们进行左右双旋的1时候是嫌疑parent的_left节点为旋转点进行一次左单旋操作因此我们这里定义一个指针让它去指向parent的_left指向的节点。node* subLR subL-_right;//旋转完后要修改此时的这个subL的_right指针指向的那个节点的平衡因子由于进行一次左右双旋之后它里面所有的节点的位置会进行一次大整改旋转完后的subL节点的右子树可能就不是我们想要的了因此这里在旋转之前必须要定义一个指针来指向那个节点。int bf subLR-_bf;//这里我们需要定义一个int类型的变量bf来存放subLR这个指针指向的那个节点的平衡因子(插入节点之后)这里之所以要这么做是因为通过前面我们在这里所分析的那3种情况如果我们仔细观察的话不难发现之所以会出现这3种情况因为就在于新插入的节点是在e子树还是f子树上或者插入的那个节点就是b子树的根由于插入的位置不同才导致了最后我们要进行重新修整一下平衡因子的操作而插入的节点的位置最直接影响的就是subLR节点的平衡因子三个位置-三种情况-三个平衡因子因此我们就可以通过旋转前b子树的根节点(也就是subLR指向的那个节点的平衡因子来判断它属于哪一种情况由此精准对应并修改它们旋转之后的平衡因子。)RotateL(subL);//以subL这个节点为旋转点(也就是上图中的5这个节点)进行左单旋操作。RotateR(parent);//进行完左单旋操作后我们接下来就要以parent(也就是上图中的10这个节点)为旋转点去进行右单旋操作。//我们此时再去看一下我们前面写的那两个单旋的代码我们可以得知在进行完前面的两步代码之后所有参与旋转的节点的平衡因子全部变成了0但是前面的3种情况中个别节点的平衡因子明显不是0由此需要我们去分情况讨论修改各个节点的平衡因子。if (bf 0)//对应的是情况3{subL-_bf 0;subLR-_bf 0;parent-_bf 0;}else if (bf -1)//对应的是情况1{subL-_bf 0;subLR-_bf 0;parent-_bf 1;}else if (bf 1)//对应的是情况2{subL-_bf -1;subLR-_bf 0;parent-_bf 0;}else//就说明旋转之前这棵树它本身就不是一棵AVL树。{assert(false);//报错}
} 2.6 右左双旋 2.6.1 旋转方法 1.跟左右双旋类似下面我们将a/b/c子树抽象为高度为h的AVL子树进行分析另外我们还需要把b子树的细节进一步展开为12节点和高度为h-1的e/f这两棵子树因为我们要对b节点的父亲节点15为旋转点进行右单旋操作右单旋需要动b子树中的右子树。由于插入的位置不确定插入的位置可能是e子树/f子树或者插入的节点它就是b子树的根节点从而使得平衡因子更新的细节也不同通过观察12的平衡因子的不同这里也要分3种情况讨论。 场景1h1时新增节点在e子树中 h1时新增节点插入在e子树上e子树的高度从h-1变为h并不断更新12-15-10这些节点的平衡因子引发旋转其中12的平衡因子为-1旋转后12和10的平衡因子为015的平衡因子为1。 场景2h1新增节点在f子树中 h1时新插入的节点插入在f子树上f子树的高度从h-1变成h并会不断更新12-15-10这些节点的平衡因子引发旋转其中12的平衡因子为1旋转后12和15的平衡因子均为010的平衡因子为1。 场景3h0时a/b/c三棵子树均为空树 h0时a/b/c三棵子树均为空树b自己就是一个新增节点不断更新15-10这些节点的平衡因子引发旋转其中12的平衡因子为0旋转后12和10和15节点的平衡因子均为0。 2.6.2 代码实现右左双旋
void RotateRL(node* parent)//parent指向的是更新后平衡因子因为2的那个节点
{node* subR parent-_right;//要以parent-_right节点为旋转点去进行一次右单旋操作。node* subRL subR-_left;//通过左右双旋的相关代码的解释可知这里我们可以知道后面要以旋转之前subR-_left的这个节点的平衡因子为条件去判断插入节点是属于上面3种情况的哪一种而且在旋转后要去修改此时的subR-_left这个节点的平衡因子由于旋转后它们的关系全部都错乱了如果旋转后再通过subR-_left去找节点的话就找不到我们想要的那个节点了因此这里我们必须在旋转前指定一个指针指向旋转前的subR-_left这个指针指向的那个节点。以方便后续去更新平衡因子。int bf subRL-_bf;//通过我们前面所学的可以得知我们在正式旋转之前(也就是插入节点之后更新节点的平衡因子遇到2时)三种情况的平衡因子唯一不同的就是subRL这个节点的平衡因子旋转前这个节点的3种情况分别对应3个不同的平衡因子由于是在旋转前才有的因此需要提前将它存储起来。RotateR(subR);//以subR这个节点为旋转点进行右旋操作。RotateL(parent);//以parent这个节点为旋转点进行左旋操作。if (bf 0)//对应的是情况3{subR-_bf 0;subRL-_bf 0;parent-_bf 0;}else if (bf -1)//对应的是情况1{subL-_bf 0;subRL-_bf 0;subR-_bf 1;}else if (bf 1)//对应的是情况2{parent-_bf -1;subR-_bf 0;subRL-_bf 0;}else//就说明旋转之前这棵树它本身就不是一棵AVL树。{assert(false);//报错}
} 2.7 AVL树的查找 用二叉搜索树的逻辑实现即可搜索效率为O(log2N)。
node* Find(const K key)
{node* cur _root;//让cur指针指向_root节点cur去遍历二叉搜索树去找到相对应的节点。while (cur)//若cur为空则说明没找到。{if (cur-_kv.first key)//在右子树{cur cur-_right;}else if (cur-_kv.first key)//在左子树{cur cur-_left;}else//cur-_kv.first key;找到了{return cur;}}return nullptr;//若处循环的话则说明cur指向空未找到。
} 2.8 AVL树的删除 AVL树的删除这一部分有点麻烦本章节不做讲解如果大家对这部分感兴趣的话可以直接去尝试着去实现。 OK今天我们就先讲到这里了那么我们下一篇再见谢谢大家的支持
