2代码实现2.左单旋的情况以及具体操作抽象图代码实现3.右左双旋的情况以及具体操作抽象图h

23.左右双旋的情况以及具体操作抽象图5.总结6.完整实现代码7.验证概念主程序代码8.性能总结前言

前面我们介绍了STL中的关联式容器map/set/multimap/mutiset等我们可以发现它们的底层都是按照二叉搜索树来实现的但是二叉搜索树自身有一些缺陷当往二叉搜索树中插入的元素有序或者接近有序二叉搜索树就会退化为单支其检索的时间复杂度就会退化为O(n)。

因此map、set等关联式容器的底层结构是对搜索二叉树进行平衡处理的平衡二叉搜索树。

一、概念

普通的搜索二叉树一旦数据有序或者接近有序就会造成二叉搜索树退化为单支两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法

**当向二叉搜索树中插入新结点后如果能保证每个节点的左右子树高度之差不超过1需要对树中结点进行调整**即可降低树的高度从而减少平均搜索长度。

该树如果是空树那么它是AVL树它的左右子树是AVL树左右子树的高度差命名为平衡因子的绝对值不超过1可以是1/0/-1

上图的红色标识的是该结点的平衡因子这里的平衡因子使用右子树的高度减左子树的高度计算的。

假设该树有n个结点其高度应保持在O(log2n)O(log_2

n)O(log2​n)搜索时间复杂度为O(log2nlog_2

templateclass

实际上AVL树就是在二叉搜索树的基础上增加了平衡因子因此AVL树的插入可以分为两步

bool

kv){//1.按照二叉搜索树的规则将节点插入到AVL树中node*

newnode

nullptr)//如果该树为空树直接插入新节点此时新节点是该树的根节点{_root

newnode;return

newnode;//2.对结点的平衡因子进行更新并检测新插入的结点是否破坏了AVL树的平衡性//调节平衡因子在插入新结点前pparent的平衡因子有以下三种情况-1,

1//如果cur插在pparent的左边给pparent的结点的平衡因子-1//如果cur插在pparent的右边给pparent的结点的平衡因子1//此时pparent的平衡因子有以下三种情况0±1±2//pparent平衡因子为0说明新插入结点不影响该子树的高度满足AVL树的性质不再进行调整//pparent平衡因子为±1说明插入前pparent的平衡因子为0此时以pparent为根的子树的高度加1需要继续向上更新平衡因子//pparent平衡因子为±2说明插入前pparent的平衡因子为±1此时pparent的平衡因子违反了AVL树的性质需要进行旋转操作while

(pParent)//当pParent为空时pParent就是根节点的父节点就不需要再进行调整了{//更新父节点的平衡因子if

(cur

pParent-_pleft){pParent-_bf--;}else

(cur

pParent-_pright){pParent-_bf;}//检测更新后的平衡因子if

pParent-_bf)//该子树的高度没变化不用调整{break;}else

pParent-_bf

pParent-_bf)//该子树的高度增加了1因此要继续向上调整平衡因子{cur

pParent;pParent

pParent-_pparent;}//3.破坏了AVL树的平衡性我们就要对以pparent为根的子树就地旋转处理//旋转的目的//1)让这棵子树的左右高度差不超过1//2旋转过程中保持它是搜索树//3更新旋转后的平衡因子//4让这棵树的高度与插入前保持一致不会继续影响上层不用继续向上调整else

pParent-_bf

pParent-_bf){//右单旋//我的平衡因子为-1父节点的平衡因子为-2.if

(-2

cur-_bf){RotateR(pParent);//更新平衡因子cur-_bf

0;pParent-_bf

cur-_bf){RotateL(pParent);//更新平衡因子cur-_bf

0;pParent-_bf

cur-_pright;RotateL(cur);RotateR(pParent);//更新平衡因子//新增结点就是SubRif

(SubR

-1;}else{assert(false);}}//右左双旋else

pParent-_bf

cur-_pleft;RotateR(cur);RotateL(pParent);//更新平衡因子//新增结点就是SubLif

(SubL-_bf

-1;}else{assert(false);}}return

true;}else//如果以上的程序哪里出现问题就会直接报错{assert(false);}}return

抽象图

图中a,b,c是高度为h的子树红色数字是插入前该节点的平衡因子。

新增结点导致要向上更新平衡因子如果父节点的平衡因子为-2且当前结点的平衡因子为-1时我们就要进行右单旋。

要由具体的解决方法推出抽象的解决方法因此下面我们具体分析当h分别为0/1/2时我们的解决方法

如图当h

0时在a处新增节点按照图中步骤使用右单旋对该子树进行调整最后更新平衡因子即可。

如图当h

1时在a结点的左右子结点任意一个位置新增节点按照图中步骤使用右单旋对该子树进行调整最后更新平衡因子即可。

如图当h

2时在a子树的i/j/m/n等四个位置的任意一个位置新增节点按照图中步骤使用右单旋对该子树进行调整最后更新平衡因子即可。

总结根据以上三种情况我们可以得出新增节点向上调整平衡因子的过程中如果出现父节点的平衡因子为-2当前结点的平衡因子为-1的情况就以父节点为轴进行右单旋之后更新父节点和当前结点的平衡因子为0即可。

代码实现

parent-_pparent;//祖父parent-_pright

SubRL;if

图中a,b,c是高度为h的子树红色数字是插入前该节点的平衡因子。

新增结点导致要向上更新平衡因子如果父节点的平衡因子为2且当前结点的平衡因子为1时我们就要进行左单旋。

0时在c位置新增结点

可以看出当父节点为2且当前结点为1时需要以父节点为轴进行左单旋最后更新平衡因子。

代码实现

parent-_pparent;//祖父parent-_pparent

SubL;SubL-_pright

我们设定结点值为30的结点是parent结点值为90的结点是pR,结点值为60的结点是pRL起名字后方便操作

抽象图

右左双旋的抽象图其中a/d是高度为h的子树b/c是高度为h-1的子树

先以pR结点为轴进行右单旋再以parent结点为轴进行左单旋最后更新平衡因子即可。

我们设定结点值为90的结点是parent结点值为30的结点是pL,结点值为60的结点是pLR起名字后方便操作

抽象图

先以pL结点为轴进行左单旋再以parent结点为轴进行右单旋最后更新平衡因子即可。

5.总结

假如以parent为根的子树不平衡即parent的平衡因子为2/-2有以下几种情况

parent的平衡因子为2说明parent的右子树高设parent的右子树的根节点为pR

当pR的平衡因子为1时执行左单旋当pR的平衡因子为-1时执行右左双旋。

parent的平衡因子为-2说明parent的左子树高设parent的左子树的根节点为pL

当pL的平衡因子为-1执行右单旋当pL的平衡因子为1执行左右双旋。

旋转结束后原parent为根的子树高度已平衡不需要再向上更新。

6.完整实现代码

node;AVLTree():_root(nullptr){}//左单旋(父节点平衡因子为2右孩子平衡因子为1void

RotateL(node*

parent-_pparent;//祖父parent-_pright

SubRL;if

SubR;}}}//右单旋(父节点平衡因子为-2左孩子平衡因子为-1void

RotateR(node*

parent-_pparent;//祖父parent-_pparent

SubL;SubL-_pright

kv){//1.按照二叉搜索树的规则将节点插入到AVL树中node*

newnode

nullptr)//如果该树为空树直接插入新节点此时新节点是该树的根节点{_root

newnode;return

newnode;//2.对结点的平衡因子进行更新并检测新插入的结点是否破坏了AVL树的平衡性//调节平衡因子在插入新结点前pparent的平衡因子有以下三种情况-1,

1//如果cur插在pparent的左边给pparent的结点的平衡因子-1//如果cur插在pparent的右边给pparent的结点的平衡因子1//此时pparent的平衡因子有以下三种情况0±1±2//pparent平衡因子为0说明新插入结点不影响该子树的高度满足AVL树的性质不再进行调整//pparent平衡因子为±1说明插入前pparent的平衡因子为0此时以pparent为根的子树的高度加1需要继续向上更新平衡因子//pparent平衡因子为±2说明插入前pparent的平衡因子为±1此时pparent的平衡因子违反了AVL树的性质需要进行旋转操作while

(pParent)//当pParent为空时pParent就是根节点的父节点就不需要再进行调整了{//更新父节点的平衡因子if

(cur

pParent-_pleft){pParent-_bf--;}else

(cur

pParent-_pright){pParent-_bf;}//检测更新后的平衡因子if

pParent-_bf)//该子树的高度没变化不用调整{break;}else

pParent-_bf

pParent-_bf)//该子树的高度增加了1因此要继续向上调整平衡因子{cur

pParent;pParent

pParent-_pparent;}//3.破坏了AVL树的平衡性我们就要对以pparent为根的子树就地旋转处理//旋转的目的//1)让这棵子树的左右高度差不超过1//2旋转过程中保持它是搜索树//3更新旋转后的平衡因子//4让这棵树的高度与插入前保持一致不会继续影响上层不用继续向上调整else

pParent-_bf

pParent-_bf){//右单旋//我的平衡因子为-1父节点的平衡因子为-2.if

(-2

cur-_bf){RotateR(pParent);//更新平衡因子cur-_bf

0;pParent-_bf

cur-_bf){RotateL(pParent);//更新平衡因子cur-_bf

0;pParent-_bf

cur-_pright;RotateL(cur);RotateR(pParent);//更新平衡因子//新增结点就是SubRif

(SubR

-1;}else{assert(false);}}//右左双旋else

pParent-_bf

cur-_pleft;RotateR(cur);RotateL(pParent);//更新平衡因子//新增结点就是SubLif

(SubL-_bf

-1;}else{assert(false);}}return

true;}else//如果以上的程序哪里出现问题就会直接报错{assert(false);}}return

true;}//获取根节点node*

AVL树是在搜索二叉树的基础上加入了平衡因子的限制因此要验证AVL树可以分为以下两个步骤

每个结点子树高度差的绝对值不超过1判断结点中的平衡因子计算是否正确

验证用例

下面是测试用的主程序代码大家可以用它来检验AVL树实现代码的正确性

#define

_Height(Jinger::AVLnodeint,int*

{if

_IsBalanceTree(Jinger::AVLnodeint,int*

pRoot)

计算pRoot节点的平衡因子即pRoot左右子树的高度差int

leftHeight

如果计算出的平衡因子与pRoot的平衡因子不相等或者pRoot平衡因子的绝对值超过1则一定不是AVL树if

(diff

pRoot的左和右如果都是AVL树则该树一定是AVL树return

_IsBalanceTree(pRoot

;tree.insert(make_pair(it,it));}int

0;bool

_IsBalanceTree(tree.Getroot());if

(ret

AVL树是一棵绝对平衡的搜索二叉树它要求每个结点的左右子树的高度差的绝对值不超过1这样可以保证查询时的时间复杂度log2(N)log_2(N)log2​(N))。

但是如果对AVL树做一些结构修改的操作它的性能就会比较低下例如插入元素时要维护其绝对平衡的性质旋转的次数会比较多。

其中删除的效果最差有可能让旋转一直持续到根节点。

因此如果需要一种查询高效且有序的数据结构并且数据结构的个数为静态的不会发生改变可以考虑使用AVL树但是如果该结构需要经常被修改AVL树就不太适合了。

以上就是今天要讲的内容本文介绍了C中的AVL树的相关概念。

本文作者目前也是正在学习C相关的知识如果文章中的内容有错误或者不严谨的部分欢迎大家在评论区指出也欢迎大家在评论区提问、交流。