基本框架五、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单旋的时候解决局部子树问题时总会忘记向上分配

一、前言

进行了简单的介绍在其文档介绍中发现这几个容器都有一个共同点其底层都是借助二叉搜索树来实现的。

但是二叉搜索树有其自身的缺陷假如往树中插入的元素有序或者接近有序二叉搜索树就会退化成为单支树时间复杂度会退化成

O(N)

等关联式容器的底层结构是对二叉树进行了平衡处理即采用平衡树来实现。

那么今天就让我们对

set

二叉搜索树虽然可以缩短查找的效率但是如果数据有序或者接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率就会变得低下。

G.M.Adelson-Velskii

年发明了一种解决上述问题的方法当向二叉搜索树中插入新节点后如果能保证每个节点的左右子树高度之差的绝对值不超过

需要对树中的结点进行旋转后续会讲也被叫做动手术即可降低树的高度从而减少平均搜索长度。

AVL

factor的图其中比节点大的放在右边比节点小的放在左边平衡因子的计算是通过右子树的高度-左子树的高度

AVL

O(log2^n)。

平衡二叉搜索树中平衡并不是说要让平衡因子始终保持

0。

二叉搜索树在实际中基本不太可能实现完全平衡但是理论上可以即满二叉树。

后面我们学的多叉平衡搜索树在现实中可以做到完全平衡。

我们接下来就准备手撕

V()):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}pairK,

_left

在AVL树中有很多的节点需要封装而且对于没有值的节点一定要置空将来我们单旋的时候有一个小插曲

if(SUbL)

如果我们初始化的时候没有置空的话这个条件的书写很明显就是不对的

为什么引入parent节点

使AVL树变成三叉链是为了方便将来沿着路径一直向上更新当然有利有弊往回找的时候方便了修改的时候麻烦了除了修改孩子还得修改双亲

templateclass

nullptr;};我们把上面结构体定义出来的AVLTreeNodeK,

V重新命名成

正常来说应该先写插入再写旋转但是由于插入代码中更新平衡因子的时候需要调用旋转的接口在不同的情况有不同的旋转方式但是我们还不了解旋转所以我书写的时候先书写的是旋转

子树左右高度不超过1旋转过程中必须保持它是搜索树更新调整孩子节点的平衡因子降低这颗子树的高度

这个原则必须牢记于心这样的话更有利于帮助我们理解后续的四种旋转

动图中我们的abc分别代表子树并不是节点所以接下来我们举俩个具体的abc例子以及抽象图的总结

例一h0

由于我们上方说到我们的旋转都是满足我们的旋转四大原则的杭哥在讲这个例子的时候说b也就是45放在30的右边是正好满足二叉搜索树但是我想难道60左边放25不可以吗

后来我想了想发现60的左侧的数字一定是3060而不是060所以b一定放在30右侧满足旋转规则这个问题告一段落

例三抽象图

等学到后期看抽象图的困难程度就会大大降低在本图中我们有很多变量都是为了和接下来的代码进行匹配

ppNode担心旋转树为子树从而旋转时丢失根与上方联系所创造出来的节点

以上如此多节点的设置正是为了保证节点的丢失以及三叉链中不光更新孩子还得更新父亲的特性

代码讲解

subR-_left;parent-_rightsubRL;subR-_leftparent;

}这段代码是我自己在没理解旋转之前写的天花板代码但是还有很多问题我并没有考虑

AVL

根据抽象图我们可以看出b的_parent节点变成了parent也就是30parent

_parent

subR;这个时候小插曲来了我们的b是一个子树如果子树b为空它还有双亲节点吗所以我们得用if条件判断一下

实则在抽象图中就可以明白为什么赋予这俩个变量30和60就是说明parent和SubR不可为空否则旋转问题无法继续讨论

(subRLnullptr)

由于我们的parent节点在旋转的过程中已经不是该树的根了所以一开始初始化的时候记得记录30的双亲节点

void

ppNodeparent-_parent;//这里parent-_rightsubRL;subR-_leftparent;//双亲if

subR;

节点置空如果是局部子树若为ppNode左子树就让其left连接SubR若为ppNode右子树就让其right连接SubR

需要在parent被修改之前

写出ppNodeif(ppNodenullptr){//说明是完整的树_rootsubR;_root-_parentnullptr;}else{if(ppNode-_leftparent)//虽然parent被旋转了

现在的我自己解决了{ppNode-_leftsubR;}else{ppNode-_rightsubR;}//这里还有一句话}这个时候else语句中还是只有向下分配所以别忘了加上subR-_parent

ppNode;

30和60的平衡因子全部为0也就是parent和SubR的_bf为0

parent-_bf

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-_leftsubR;}else{ppNode-_rightsubR;}subR-_parent

ppNode;}//4.更新平衡因子parent-_bfsubR-_bf0;//更新平衡因子

}代码总结俩孩子三双亲

我们在写AVL旋转的时候一定要格局打开我们在旋转树内的节点的时候殊不知根节点已经岌岌可危所以这就是局部子树的问题而且向下分配完了别忘了向上分配三叉链使得往上找轻松了但也使得旋转时维护树的成本变高了

AVL的代码逻辑可以理解成俩个孩子三个双亲因为我们的局部子树其实也是双亲问题

else

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-_leftsubL;}else{ppNode-_rightsubL;}subL-_parent

ppNode;//局部子树else总会忘记向上分配}//4.更新平衡因子parent-_bfsubL-_bf0;//更新平衡因子}5.3左右双旋新节点插入较高左子树的右侧—左右先左单旋再右单旋

为什么我们需要引入左右单旋这个场景呢我们的普通单旋为什么解决不了问题了请看以下这些情况

例一h0

subLRsubL-_right;RotateL(parent-_left);RotateR(parent);}但是非常遗憾的是我们的抽象图看似汇集了所有情况实则只有60节点左侧插入的情况但是左右双旋的平衡因子更新本质上是有三种情况的

因为旋转完之后我们很难考察是哪个位置插入了节点所以在旋转之前记录bf

void

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

subRL-_bf;RotateR(parent-_right);RotateL(parent);if

(bf

0;}else{assert(false);}}六、AVL树的插入

按照二叉搜索树的插入方法找到待插入位置。

找到待插入位置后将待插入结点插入到树中。

更新平衡因子如果出现不平衡则需要进行旋转。

因为AVL树本身就是一棵二叉搜索树因此寻找结点的插入位置是非常简单的按照二叉搜索树的插入规则

待插入结点的key值比当前结点小就插入到该结点的左子树。

待插入结点的key值比当前结点大就插入到该结点的右子树。

待插入结点的key值与当前结点的key值相等就插入失败。

如此进行下去直到找到与待插入结点的key值相同的结点判定为插入失败或者最终走到空树位置进行结点插入。

bool

}以上这段代码只是单纯的插入代码如果我们不更新平衡因子的话那么AVL存在的意义也就没有了所以我们得更新平衡因子

与二叉搜索树插入结点不同的是AVL树插入结点后需要更新树中结点的平衡因子因为插入新结点后可能会影响树中某些结点的平衡因子。

由于一个结点的平衡因子是否需要更新是取决于该结点的左右子树的高度是否发生了变化因此插入一个结点后该结点的祖先结点的平衡因子可能需要更新。

每更新完一个结点的平衡因子后都需要进行以下判断注这里的parent不是最上面那个节点新增节点的祖先是parent

如果parent的平衡因子等于-1或者1表明还需要继续往上更新平衡因子。

如果parent的平衡因子等于0表明无需继续往上更新平衡因子了。

如果parent的平衡因子等于-2或者2表明此时以parent结点为根结点的子树已经不平衡了需要进行旋转处理。

得动手术

判断理由说明

操作后会变成-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的平衡因子为-2/2时cur的平衡因子必定是-1/1而不会是0。

理由如下

若cur的平衡因子是0那么cur一定是新增结点而不是上一次更新平衡因子时的parent否则在上一次更新平衡因子时会因为parent的平衡因子为0而停止继续往上更新。

如果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

parent-_left){parent-_bf--;}else{parent-_bf;}//

1、parent-_bf

说明之前parent一边高一边低这次插入填上矮的那边parent所在子树高度不变不需要继续往上更新//

2、parent-_bf

-1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}return

AVL

验证其为二叉搜索树。

如果中序遍历可以得到一个有序的序列就说明为二叉搜索树。

验证其为平衡树。

每个结点左右子树高度差的绝对值不超过

public://中序void

nullptr){return;}_Inorder(root-_left);cout

root-_kv.first

;_Inorder(root-_right);return;}//求树的高度int

Height(Node*

public:/*----------------------------------------------插入------------------------------------------------*/bool

Insert(const

parent-_left){parent-_bf--;}else{parent-_bf;}//

1、parent-_bf

说明之前parent一边高一边低这次插入填上矮的那边parent所在子树高度不变不需要继续往上更新//

2、parent-_bf

-1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}return

true;}

/*----------------------------------------------旋转------------------------------------------------*/void

RotateL(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-_leftsubR;}else{ppNode-_rightsubR;}subR-_parent

ppNode;}//4.更新平衡因子parent-_bfsubR-_bf0;//更新平衡因子}void

RotateR(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-_leftsubL;}else{ppNode-_rightsubL;}subL-_parent

ppNode;}//4.更新平衡因子parent-_bfsubL-_bf0;//更新平衡因子}void

RotateLR(Node*

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*

subRL-_bf;RotateR(parent-_right);RotateL(parent);if

(bf

Inorder(){_Inorder(_root);}void

_Inorder(Node*

nullptr)return;_Inorder(root-_left);cout

root-_kv.first

endl;_Inorder(root-_right);}int

Height(Node*

IsBalance(root-_right);}private:Node*

_root

子树左右高度不超过1旋转过程中必须保持它是搜索树更新调整孩子节点的平衡因子降低这颗子树的高度

因为旋转后树的高度变为插入之前了即树的高度没有发生变化也就不会影响其父结点的平衡因子了

不要把这个较高给忽略掉

对于单旋利用俩孩子三双亲原则对于双旋难点在于平衡因子更新得画出插入前和旋转后的图分析平衡因子三种情况

双旋得提前记录subLR或者subRL的bf旋转完了都找不到了

单旋得提前记录parent的_parent也就是代码中的ppNode

希望给大家带来帮助