摘要:如果我们定义一棵高度为h的AVL树,所包含的最小节点数为。可以按照v,p,g三个节点的位置,进行Zigzig,Zagzag,Zigzag,Zagzig操作,进而使树重平衡。
今天我们来看一下BBST家族的第一成员AVL。来学习下它如何界定适度平衡的规则,以及如何做重平衡的操作。
网上有很多BBST、AVL这些东西的资料,但相信大家和我一样,看了很多,发现只能死记硬背其中的旋转规则,左旋一下,右旋一下,一会就旋懵了。其实所有的旋转都是有规律可循,而且是最简单的规律。包括上篇文章的Zig/Zag,其实原理就是以中序序列的角度看待整颗树,然后从中间节点,将整颗树拉起。
这里先抛一些结论,以免文章过长,找不到重点:
-
在相对较高的子树上进行插入操作,会导致失衡,但只要修复该情况,并不会导致失衡传播,所以复杂度为
-
在相对较矮的子树上进行删除操作,会导致失衡,会有失衡传播的情况,所以需要遍历修复所有祖先节点,最坏的情况为
-
可以按照v,p,g三个节点的位置,进行Zigzig,Zagzag,Zigzag,Zagzig操作,进而使树重平衡
-
Zigzig,Zagzag,Zigzag,Zagzig可以根据BST的顺序性,进一步优化为3+4重构,简化步骤以及逻辑复杂性。
目录:
-
定义
-
如何界定适度平衡的标准?
-
重平衡 - 插入操作
-
单旋 -- Zigzig/Zagzag
-
双旋 -- Zagzig/Zigzag
-
源码示例
-
重平衡 - 删除操作
-
单旋 - Zigzig/Zagzag
-
双旋 -- Zagzig/Zigzag
-
源码示例
-
双旋以及单旋原理分析
-
3+4重构
-
3 + 4 重构源码
-
`rotateAt`源码
-
总结
-
参考资料
定义
AVL是==A==delson-==V==elsky and ==L==andis首字母的简写,AVL是自平衡的二叉搜索树(self-balancing binary search tree)。AVL的规则入下:
-
一个节点的平衡因子是其右子树与左子树高度之差,公式:
-
一个节点的平衡因子只能是-1、0、1中的一个,即节点的平衡因子 「绝对值不大于1」 。公式:
注意:
❝
树的高度为所有节点中的深度最大值,称作该树的高度。 节点的深度为所在层数。 所以以一个节点为根的子树的高度,可以理解为该子树,最深处的节点到该节点的最短距离。
❞
如何界定适度平衡的标准?
如果我们定义一棵高度为h的AVL树,所包含的最小节点数为。如下图所示:
-
从AVL对平衡因子的约束可知: 。
-
如果将等式两边同时
+1
, -
定义,则
大家对这个公式熟悉不?这不就是 「斐波那契数」 吗?如果你学习过动态规划,那这个公式一定是你的入门题。我们可以利用 「数学归纳法」 继续推导,可以推导出的结论为: * 一棵高度为h的AVL树,至少包含的节点数为
进而可知一棵AVL树,节点数的 「下界」 为斐波那契数,即。进而可知高度h的上届为。我们也可以称h在渐进意义上接近,达到了上面我们所说的 「适度平衡」 。
重平衡 - 插入操作
插入操作的第一原则: 「插入操作一定是在叶节点进行的」 。因为AVL本身也是一颗BST,所以插入一个新节点时一定会先遍历到最深的叶节点处,才会进行插入操作。
如果我们在叶节点进行插入,有可能将这个叶节点的高度加1,也可能高度不变。如下图所示,叶节点为v,虚线节点为可能插入的节点位置,绿色节点为已有节点。
-
如果当前节点有孩子,并且插入的节点为与其对应的另一个位置,则此时v的高度不变。进而可知,整棵树的平衡性不会遭到破坏。
-
如果当前节点没有孩子,那么无论插入的位置是左孩子,还是右孩子的位置,都将导致v的高度加一:。我们下面会着重分下下这种情况,因为涉及到高度变化,可能会影响到整颗树的平衡性。
-
==所以在最高的子树中,进行插入操作,可能会使原本就比较高的子树,高度加一,进而导致失衡。==
下面我们分析下可能导致高度变化的插入行为,如何重平衡。以下所有示例中:
-
「v」为当前节点
-
「p」为parent节点,即父节点
-
「g」为grandparent节点,即祖父节点
单旋 -- Zigzig/Zagzag
❝
注意,这种情况下,一定是
-
如果或者,那么g在插入L,R之前已经失衡了, 因为
-
如果或者,那么g在插入L,R之前已经失衡了,因为
-
如果, 那么插入L,R之后,不会影响g的高度。
-
所以在最高的子树上进行插入可能会导致失衡现象
❞
如上图所示,虚线框中的L和R代表可能插入的位置。由于原来,现在v的两颗子树中可能已经插入了节点,导致v的高度从L2转移到了L3,进而导致了g的高度失衡。这种情况我们定义为 「ZagZag」 (也有的称之为LL,g和p都在逆时针方向)。
要修复这种情况,也很简单。只需在失衡的g节点执行一次 「Zag」 操作就可以了。如图所示: 现在g的高度已经恢复到了,已经重平衡了。经过这个操作后, 「g的祖宗节点会不会失衡呢」 ?答案是否定的, 「不会」 。我们来分析下,图中的Rc代表g的上层节点:
-
平衡前:rc的高度为,因为v和rc中间相隔了 「两个节点(p, g)」 。由于增加了1,也增加了1。
-
平衡后:,因为从v到rc只相隔一个节点 「p」 。所以由于增加了1,不再变化。
Zigzig的情况和Zagzag差不多,只需要将**zig(g)**就可以重平衡。所以单旋的复杂度为,因为只用修复一个节点。
双旋 -- Zagzig/Zigzag
此时g的失衡是由于在v的左右子树下面插入R或者L,导致v的高度变化,进而导致g的变化。由于p在v的顺时针方向,g在p的逆时针方向,我们称这种情况为 「Zigzag」 。那么这种情况下,该如何重平衡呢?
首先,我们在p处进行一次Zig操作,如下图所示: 然后,在g处做一次zag操作,如下图所示:
我们可以分析下,重平衡前后节点的高度。 重平衡前:
-
v的高度为
-
p的高度为
ZagZig与ZigZag的操作正好是相反的。我相信到这里,你可能已经转蒙了,脑子里全是zig,zag。那么为什么我们要这么旋转呢?
源码示例
上图截取自学堂在线,邓俊辉教授的数据结构(下)。其中部分内容:
-
FromPartentTo
是修改当前节点的父节点的引用,例如g的父亲是rc,此时是将rc -> g的指向更改为=号右侧的结果,即rc ->rotateAt(tallerChild(tallerChild(g)))
-
tallerChild
表示当前节点子节点中,高度最高的 -
rotateAt
是具体的ZigZag的逻辑,我们后面会详细分析该函数
重平衡 - 删除操作
删除操作和插入操作差不多,删除操作的根本原因是:
-
在原本相对较矮,或者最矮的子树上进行删除操作,导致失衡 我们还是按照单旋和双旋分析。
单旋 - Zigzig/Zagzag
如上图,v,p,g三个节点以Zigzig的方式排列。灰色节点代表可能的更高的树的位置,例如,T0、T1、T2,目前都比T3高。现在T3是最矮的树,如果此时我们在T3上删除一个元素,导致T3比原来矮了。那么整个树将失衡。g节点从**-1 「变为」 -2**。
如何修复这种失衡呢?只需要进行一次Zig(g)操作。如下图所示: 我们简单分析下旋转前的情况:
-
原来g的左子树的高度为,或者,或者
-
原来g的右子树的高度为, 由于T3的高度减了1导致失衡。
-
所以g的平衡因子为
-
RC的在g的分支上的高度为
旋转后呢?
-
RC的子节点变为了p,
-
p的左子树的高度为,或者
-
p的右子树的高度为,或者
-
失衡的g的节点高度由,变成了。可以看到以g的角度来看,由于T3到高度减少了1,旋转后g到T2的距离减少了1,所以重新平衡了。
-
RC的在p的分支上的高度为
g重平衡了,那么RC呢? 如果,那RC的高度岂不是由变成了。如果当前分支,本来就是RC中相对矮的分支,RC又可能失衡?RC旋转后,RC的祖宗又可能失衡。
很尴尬的场景,当我们修复完一个节点后,这个失衡可能传播到其祖宗节点。如果修复一个节点的操作数为,那修复整颗树,最坏情况下可能需要。
我们上面分析的是Zigzig的情况,Zagzag的情况和上面情况是相同的,无非是做zag操作。下面我们分析下双旋的情况。
双旋 -- Zagzig/Zigzag
上图是双旋的Zagzig情况,p在v的逆时针方向,g在p的顺时针方向。灰色部分代表可能是最高的子树,T3下面的红色方块,代表T3是相对较矮的树,我们会在其中删除一个节点。可以看到如果T3中移除了一个节点,那么g将失衡。修复的方式很简单,同样是zag,zig操作。
可以理解第一次Zag操作,三个节点变成了单旋的情况,再单旋一次就可以重平衡了。我们同样分析下,经历Zagzig前后节点高度的变化。 双旋前:
-
v的高度为,
-
p的高度为
-
进而可知g的左子树高度为,因为原来是平衡的,当T3的高度减少1以后,,进而失衡。
-
此时RC的子树高度为
双旋后:
-
p的高度为
-
g的高度为,所以尽管T3的高度减少了1,但是T2到g的距离也减少的1,进而g重新处于平衡状态。
-
v的高度为
-
此时RC的子树高度变为了,可以对比原来RC子树的高度看到,RC的子树高度减少了1。如果此时该子树为相对较矮的子树,或者说RC节点的平衡因子正好是1,那经历旋转操作后RC又失衡了。
所以双旋操作也同样有失衡传播的情况,虽然双旋经历了两次操作,但是复杂度也是,但整颗树重平衡的操作复杂度为
源码示例
和插入操作一样,以g的孙子节点v开始做旋转操作,调用 rotateAt
。但是并不是一次重平衡就跳出循环。而是要遍历当前节点的祖宗节点。
双旋以及单旋原理分析
我们学树相关的数据结构的时候,很容易弄混这些旋转操作。那AVL的旋转有什么规律可循吗?
-
都是Zig/Zag或者其组合形式。
-
可以根据失衡节点的位置来判断具体要做什么操作。
-
插入操作只需一次重平衡,
-
删除操作最坏需要次重平衡操作。
ZigZag的代码其实不难写,但还有没有优化的空间?这里还是要用到BST的顺序性的特点,来优化我们的Zig/Zag操作。
3+4重构
如果上面的每次旋转都是以 「修复」 一个物品的角度看待问题。那么3+4重构是一个把物品打散重构的角度。我们依然用上面的字母来代表树中的一些元素:
-
如果g为最低的失衡节点,考察祖孙三代:g ~ p ~ v
-
按中序遍历序列,将其命名为:A、B、C三个节点。
-
三个节点,可能拥有的最大不相交子树为4个,例如我们上面分析用到的T0,T1,T2,T3
-
按中序序列遍历,将其命名为:T0、T1、T2、T3
如上图所示,可以发现亮点:
-
无论你上面的树是如何旋转,树的中序序列是不变的。
-
每次旋转都无非是想将一个非对称的树,转为对称的平衡状态。因为这种情况下树的高度最低,即 「在不考虑T0,T1,T2,T3内部节点」 的情况下,这种对称的状态为高度最低,达到CMT的平衡。
那么我们能不能不用旋转,直接重构呢?答案是肯定的,当然可以。只要每次我们都将:
-
B为子树的树根
-
A为B的左节点
-
C为B的右节点
-
T0、T1为A的左右子树
-
T2、T3为B的左右子树
3 + 4 重构源码
可以看到代码很简单,是不是比旋转要简单的多呢?现在我们可以利用 「3+4重构」 实现rotateAt源码了。
rotateAt
源码
所有的zigzag操作都变得极为简单。同样的,我们思考问题的角度也可以变得很简单。
总结
AVL平衡因子绝对值不大于的设定,来保证整棵树高度在渐进意义下接近。同时通过ZigZag操作来实现重平衡操作。可能这些旋转对于我们来说很难记忆,但我们可以用3+4重构来理解其中的原理。
后面我们会讲一些高级搜索树,预计在每个周末更新文章,如果大家喜欢的话,可以点波关注,或者收藏。
参考资料
-
数据结构(下)-邓俊辉,学堂在线 http://www.xuetangx.com/courses/course-v1:TsinghuaX+30240184_2X+sp/courseware/06d6c305fca54193901007d83cd6e74e/6c692546abdf46f0becab46cf51bbce6/