建设银行网站怎么修改手机号码吗,网站模板如何使用 如何修改吗,张北网站seo,好用的wordpress编辑器文章目录 一、前言二、AVL树的概念#xff08;引入bf#xff09;三、AVL节点树的定义四、AVL树的基本框架五、AVL树的旋转5.1左单旋#xff08;新节点插入较高右子树的右侧---右右#xff1a;左单旋#xff09;例一#xff08;h0#xff09;例二#xff08;h1#xff… 文章目录 一、前言二、AVL树的概念引入bf三、AVL节点树的定义四、AVL树的基本框架五、AVL树的旋转5.1左单旋新节点插入较高右子树的右侧---右右左单旋例一h0例二h1例三抽象图代码讲解1.更新双亲节点2.处理局部子树问题3.更新平衡因子4.代码汇总 代码总结俩孩子三双亲 5.2左单旋新节点插入较高左子树的左侧---左左右单旋例一h0例二h1例三抽象图代码总结代码解释见左单旋 5.3左右双旋新节点插入较高左子树的右侧---左右先左单旋再右单旋例一h0例二h1例三抽象图代码讲解 5.4右左双旋新节点插入较高右子树的左侧---右左先右单旋再左单旋抽象图 六、AVL树的插入七、AVL树相关的一些测试八、完整代码AVL.hAVL.cpp 九、难点总结旋转的四个原则在进行旋转处理后就无需继续往上更新平衡因子了旋转口诀是插入较高... 不要把这个较高给忽略掉写代码的时候头脑要清楚不要忘了回溯parent的值向上分配插入代码更新平衡因子的条件是whileparent对于单旋利用俩孩子三双亲原则对于双旋难点在于平衡因子更新得画出插入前和旋转后的图分析平衡因子三种情况双旋得提前记录subLR或者subRL的bf旋转完了都找不到了单旋得提前记录parent的_parent也就是代码中的ppNode单旋的时候解决局部子树问题时总会忘记向上分配 一、前言
在上一篇文章中对 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 树了关键点在于俩个地方 二叉搜索树的插入更新平衡因子 templateclass K, class V
struct AVLTreeNode
{AVLTreeNode(const pairK, V kv pairK, V()):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}pairK, V _kv;//存储key和valueAVLTreeNodeK, V* _left nullptr;//指向左孩子AVLTreeNodeK, V* _right nullptr;//指向右孩子AVLTreeNodeK, V* _parent nullptr;//指向父亲结点int _bf 0;//平衡因子
};节点为什么置空
在AVL树中有很多的节点需要封装而且对于没有值的节点一定要置空将来我们单旋的时候有一个小插曲 if(SUbL) 如果我们初始化的时候没有置空的话这个条件的书写很明显就是不对的
为什么引入parent节点
使AVL树变成三叉链是为了方便将来沿着路径一直向上更新当然有利有弊往回找的时候方便了修改的时候麻烦了除了修改孩子还得修改双亲
平衡因子的引入
最重要的还是平衡因子的封装加入AVL树节点定义的大家庭 四、AVL树的基本框架
templateclass K, class Vclass AVLTree{typedef AVLTreeNodeK, V Node;private:Node* _root nullptr;};我们把上面结构体定义出来的AVLTreeNodeK, V重新命名成 Node 方便之后命名轻松
私有变量是我们的根节点 _root 五、AVL树的旋转
正常来说应该先写插入再写旋转但是由于插入代码中更新平衡因子的时候需要调用旋转的接口在不同的情况有不同的旋转方式但是我们还不了解旋转所以我书写的时候先书写的是旋转
首先凡事皆有原则我们的旋转也不例外 子树左右高度不超过1旋转过程中必须保持它是搜索树更新调整孩子节点的平衡因子降低这颗子树的高度 这个原则必须牢记于心这样的话更有利于帮助我们理解后续的四种旋转
5.1左单旋新节点插入较高右子树的右侧—右右左单旋 左单旋的定义新节点插入较高右子树的右侧—右右左单旋
动图中我们的abc分别代表子树并不是节点所以接下来我们举俩个具体的abc例子以及抽象图的总结
例一h0 例二h1 由于我们上方说到我们的旋转都是满足我们的旋转四大原则的杭哥在讲这个例子的时候说b也就是45放在30的右边是正好满足二叉搜索树但是我想难道60左边放25不可以吗 后来我想了想发现60的左侧的数字一定是3060而不是060所以b一定放在30右侧满足旋转规则这个问题告一段落
例三抽象图 等学到后期看抽象图的困难程度就会大大降低在本图中我们有很多变量都是为了和接下来的代码进行匹配
ppNode担心旋转树为子树从而旋转时丢失根与上方联系所创造出来的节点
parent是旋转的函数参数也是这个子树或者树旋转前的根
SubRparent的右侧
SubRLparent的右侧的左侧
以上如此多节点的设置正是为了保证节点的丢失以及三叉链中不光更新孩子还得更新父亲的特性
代码讲解
根据上方小羊精美的图我们不难写出以下代码
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;parent-_rightsubRL;subR-_leftparent;
}这段代码是我自己在没理解旋转之前写的天花板代码但是还有很多问题我并没有考虑
1. 我只更新了孩子节点也就是说我只做了向下分配
2. 我的parent节点已经丢失所以也得向上分配这里有个小插曲
3. 如果这个树是局部子树怎么办
4. AVL 树最根本的平衡因子更新没有体现
根据以上问题我们还得继续写出代码 1.更新双亲节点
根据抽象图我们可以看出b的_parent节点变成了parent也就是30parent 的 _parent 节点变成了 SUbR 也就是30的双亲变成了60
subRL-_parent parent;
parent-_parent subR;这个时候小插曲来了我们的b是一个子树如果子树b为空它还有双亲节点吗所以我们得用if条件判断一下
但是为什么parent不用判断是否为空 实则在抽象图中就可以明白为什么赋予这俩个变量30和60就是说明parent和SubR不可为空否则旋转问题无法继续讨论
if (subRLnullptr)
{subRL-_parent parent;
}
parent-_parent subR;2.处理局部子树问题
由于我们的parent节点在旋转的过程中已经不是该树的根了所以一开始初始化的时候记得记录30的双亲节点
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;Node* ppNodeparent-_parent;//这里parent-_rightsubRL;subR-_leftparent;//双亲if (subRLnullptr){subRL-_parent parent;}parent-_parent subR;
}这里分俩种情况
是独立子树那么就更新_root节点并且将其 _parent 节点置空如果是局部子树若为ppNode左子树就让其left连接SubR若为ppNode右子树就让其right连接SubR //判断是否为局部子树 需要在parent被修改之前 写出ppNodeif(ppNodenullptr){//说明是完整的树_rootsubR;_root-_parentnullptr;}else{if(ppNode-_leftparent)//虽然parent被旋转了 但是上层的ppNode还是连着parent节点 哈哈 当年的自己提出这个问题 现在的我自己解决了{ppNode-_leftsubR;}else{ppNode-_rightsubR;}//这里还有一句话}这个时候else语句中还是只有向下分配所以别忘了加上subR-_parent ppNode;
3.更新平衡因子
30和60的平衡因子全部为0也就是parent和SubR的_bf为0
parent-_bf subR-_bf 0;4.代码汇总
void RotateL(Node* parent)
{//俩个孩子 三个双亲 好好品这句话//1.更新孩子节点向下分配Node* subR parent-_right;Node* subRL subR-_left;Node* ppNodeparent-_parent;//为了避免是局部子树parent-_rightsubRL;subR-_leftparent;//2.更新双亲节点往回分配if(subRL!nullptr)//往回分配的小插曲 空节点没有双亲节点{subRL-_parentparent;}parent-_parentsubR;//3.判断是否为局部子树 需要在parent被修改之前 写出ppNodeif(ppNodenullptr){//说明是完整的树_rootsubR;_root-_parentnullptr;}else{if(ppNode-_leftparent)//虽然parent被旋转了 但是上层的ppNode还是连着parent节点 {ppNode-_leftsubR;}else{ppNode-_rightsubR;}subR-_parent ppNode;}//4.更新平衡因子parent-_bfsubR-_bf0;//更新平衡因子
}代码总结俩孩子三双亲
我们在写AVL旋转的时候一定要格局打开我们在旋转树内的节点的时候殊不知根节点已经岌岌可危所以这就是局部子树的问题而且向下分配完了别忘了向上分配三叉链使得往上找轻松了但也使得旋转时维护树的成本变高了
AVL的代码逻辑可以理解成俩个孩子三个双亲因为我们的局部子树其实也是双亲问题 同时别忘了b子树的小插曲而且局部子树 else 的时候也容易忘记向上分配同时最后也别忘了平衡因子的更新
5.2左单旋新节点插入较高左子树的左侧—左左右单旋 例一h0 例二h1 例三抽象图 代码总结代码解释见左单旋 void RotateR(Node* parent){//俩个孩子 三个双亲 好好品这句话//1.更新孩子节点向下分配Node* subLparent-_left;Node* subLRsubL-_right;Node* ppNodeparent-_parent;//为了避免是局部子树parent-_leftsubLR;subL-_rightparent;//2.更新双亲节点往回分配if(subLR!nullptr)//往回分配的小插曲 空节点没有双亲节点{subLR-_parentparent;}parent-_parentsubL;//3.判断是否为局部子树 需要在parent被修改之前 写出ppNodeif(ppNodenullptr){//说明是完整的树_rootsubL;_root-_parentnullptr;}else{if(ppNode-_leftparent)//虽然parent被旋转了 但是上层的ppNode还是连着parent节点 哈哈 当年的自己提出这个问题 现在的我自己解决了{ppNode-_leftsubL;}else{ppNode-_rightsubL;}subL-_parent ppNode;//局部子树else总会忘记向上分配}//4.更新平衡因子parent-_bfsubL-_bf0;//更新平衡因子}5.3左右双旋新节点插入较高左子树的右侧—左右先左单旋再右单旋 先说结论我们需要对parent-left进行左单旋 再对parent进行右单旋即可
为什么我们需要引入左右单旋这个场景呢我们的普通单旋为什么解决不了问题了请看以下这些情况 例一h0
先把弯的缕直再进行单旋 例二h1 例三抽象图 代码讲解
此时我们可以基本写出以下代码
void RotateLR(Node* parent){// Node* subLparent-_left;// Node* subLRsubL-_right;RotateL(parent-_left);RotateR(parent);}但是非常遗憾的是我们的抽象图看似汇集了所有情况实则只有60节点左侧插入的情况但是左右双旋的平衡因子更新本质上是有三种情况的
60的左节点插入60的右节点插入60本身就是插入节点
我们将这个状态的SubLR的平衡因子记录下来为bf 因为旋转完之后我们很难考察是哪个位置插入了节点所以在旋转之前记录bf 从以上情况分析平衡因子就不再吃力了完整代码如下
void RotateLR(Node* parent){Node* subLparent-_left;Node* subLRsubL-_right;int bfsubLR-_bf;//为了判读平衡因子改变的三种情况RotateL(parent-_left);RotateR(parent);if(bf-1)//subLR左子树插入{subL-_bf0;subLR-_bf0;parent-_bf1;}if(bf1)//subLR右子树插入{subL-_bf-1;subLR-_bf0;parent-_bf0;}if(bf0)//本身就是新节点被插入{subL-_bf0;subLR-_bf0;parent-_bf0;}}总结分析平衡因子的时候应该同时对照着插入前和插入俩次旋转完成后的图像去判断平衡因子的大小 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);}}六、AVL树的插入
AVL树插入结点时有以下三个步骤
按照二叉搜索树的插入方法找到待插入位置。找到待插入位置后将待插入结点插入到树中。更新平衡因子如果出现不平衡则需要进行旋转。
因为AVL树本身就是一棵二叉搜索树因此寻找结点的插入位置是非常简单的按照二叉搜索树的插入规则
待插入结点的key值比当前结点小就插入到该结点的左子树。待插入结点的key值比当前结点大就插入到该结点的右子树。待插入结点的key值与当前结点的key值相等就插入失败。
如此进行下去直到找到与待插入结点的key值相同的结点判定为插入失败或者最终走到空树位置进行结点插入。
bool Insert(const pairK, 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;}
}以上这段代码只是单纯的插入代码如果我们不更新平衡因子的话那么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/1AVL树中每个结点的左右子树高度之差的绝对值不超过1。
而在最坏情况下我们更新平衡因子时会一路更新到根结点。例如下面这种情况所以我们的代码得写成while(parent) 三叉链结构的优势体现 由于我们插入结点后需要倒着往上进行平衡因子的更新所以我们将AVL树结点的结构设置为了三叉链结构这样我们就可以通过父指针找到其父结点进而对其平衡因子进行更新。当然我们也可以不用三叉链结构可以在插入结点时将路径上的结点存储到一个栈当中当我们更新平衡因子时也可以通过这个栈来更新祖先结点的平衡因子但是相对较麻烦。 若是在更新平衡因子的过程当中出现了平衡因子为-2/2的结点这时我们需要对以该结点为根结点的树进行旋转处理而旋转处理分为四种在进行分类之前我们首先需要进行以下分析 我们将插入结点称为cur将其父结点称为parent那么我们更新平衡因子时第一个更新的就是parent结点的平衡因子更新完parent结点的平衡因子后若是需要继续往上进行平衡因子的更新那么我们必定要执行以下逻辑
cur parent;
parent parent-_parent;这里我想说明的是当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的平衡因子为-2cur的平衡因子为-1时进行右单旋。左左当parent的平衡因子为-2cur的平衡因子为1时进行左右双旋。左子树右侧当parent的平衡因子为2cur的平衡因子为-1时进行右左双旋。右子树左侧当parent的平衡因子为2cur的平衡因子为1时进行左单旋。右右
并且在进行旋转处理后就无需继续往上更新平衡因子了因为旋转后树的高度变为插入之前了即树的高度没有发生变化也就不会影响其父结点的平衡因子了。
加上更新平衡因子后的插入完整代码 bool Insert(const pairK, 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;}七、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);}
/*test.c*/
int main()
{int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };wcy::AVLTreeint, 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;
} 八、完整代码
AVL.h
#include assert.h
#include time.h
#includealgorithm
#includeiostream
using namespace std;
templateclass K, class V
struct AVLTreeNode
{pairK, V _kv;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf; // balance factorAVLTreeNode(const pairK, V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};templateclass K, class V
struct AVLTree
{typedef AVLTreeNodeK, V Node;
public:/*----------------------------------------------插入------------------------------------------------*/bool Insert(const pairK, 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* ppNodeparent-_parent;//为了避免是局部子树parent-_rightsubRL;subR-_leftparent;//2.更新双亲节点往回分配if(subRL!nullptr)//往回分配的小插曲 空节点没有双亲节点{subRL-_parentparent;}parent-_parentsubR;//3.判断是否为局部子树 需要在parent被修改之前 写出ppNodeif(ppNodenullptr){//说明是完整的树_rootsubR;_root-_parentnullptr;}else{if(ppNode-_leftparent)//虽然parent被旋转了 但是上层的ppNode还是连着parent节点 {ppNode-_leftsubR;}else{ppNode-_rightsubR;}subR-_parent ppNode;}//4.更新平衡因子parent-_bfsubR-_bf0;//更新平衡因子}void RotateR(Node* parent){//俩个孩子 三个双亲 好好品这句话//1.更新孩子节点向下分配Node* subLparent-_left;Node* subLRsubL-_right;Node* ppNodeparent-_parent;//为了避免是局部子树parent-_leftsubLR;subL-_rightparent;//2.更新双亲节点往回分配if(subLR!nullptr)//往回分配的小插曲 空节点没有双亲节点{subLR-_parentparent;}parent-_parentsubL;//3.判断是否为局部子树 需要在parent被修改之前 写出ppNodeif(ppNodenullptr){//说明是完整的树_rootsubL;_root-_parentnullptr;}else{if(ppNode-_leftparent)//虽然parent被旋转了 但是上层的ppNode还是连着parent节点 哈哈 当年的自己提出这个问题 现在的我自己解决了{ppNode-_leftsubL;}else{ppNode-_rightsubL;}subL-_parent ppNode;}//4.更新平衡因子parent-_bfsubL-_bf0;//更新平衡因子}void RotateLR(Node* parent){Node* subLparent-_left;Node* subLRsubL-_right;int bfsubLR-_bf;//为了判读平衡因子改变的三种情况RotateL(parent-_left);RotateR(parent);if(bf-1)//subLR左子树插入{subL-_bf0;subLR-_bf0;parent-_bf1;}if(bf1)//subLR右子树插入{subL-_bf-1;subLR-_bf0;parent-_bf0;}if(bf0)//本身就是新节点被插入{subL-_bf0;subLR-_bf0;parent-_bf0;}}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 };
// AVLTreeint, int t;
// for (auto e : a)
// {
// t.Insert(make_pair(e, e));
// }
//
// t.Inorder();
//
// cout t.IsBalance() endl;
//}void TestAVLTree()
{srand(time(0));const size_t N 10000;AVLTreeint, int t;for (size_t i 0; i N; i){size_t x rand();t.Insert(make_pair(x, x));//cout t.IsBalance() endl;}//t.Inorder();cout t.IsBalance() endl;
}
AVL.cpp
#includeAVL.h
#includeiostream
#includealgorithm
using namespace std;
/*test.c*/
int main()
{int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTreeint, 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旋转过程中必须保持它是搜索树更新调整孩子节点的平衡因子降低这颗子树的高度
在进行旋转处理后就无需继续往上更新平衡因子了
因为旋转后树的高度变为插入之前了即树的高度没有发生变化也就不会影响其父结点的平衡因子了
旋转口诀是插入较高… 不要把这个较高给忽略掉
写代码的时候头脑要清楚不要忘了回溯parent的值向上分配
插入代码更新平衡因子的条件是whileparent
对于单旋利用俩孩子三双亲原则对于双旋难点在于平衡因子更新得画出插入前和旋转后的图分析平衡因子三种情况
双旋得提前记录subLR或者subRL的bf旋转完了都找不到了
单旋得提前记录parent的_parent也就是代码中的ppNode
单旋的时候解决局部子树问题时总会忘记向上分配
希望给大家带来帮助
