AVL - 自平衡二叉查找树

今天我们来看一下BBST家族的第一成员AVL。来学习下它如何界定适度平衡的规则，以及如何做重平衡的操作。

网上有很多BBST、AVL这些东西的资料，但相信大家和我一样，看了很多，发现只能死记硬背其中的旋转规则，左旋一下，右旋一下，一会就旋懵了。其实所有的旋转都是有规律可循，而且是最简单的规律。包括上篇文章的Zig/Zag，其实原理就是以中序序列的角度看待整颗树，然后从中间节点，将整颗树拉起。

这里先抛一些结论，以免文章过长，找不到重点：

1. 在相对较高的子树上进行插入操作，会导致失衡，但只要修复该情况，并不会导致失衡传播，所以复杂度为#card=math&code=O%281%29)
2. 在相对较矮的子树上进行删除操作，会导致失衡，会有失衡传播的情况，所以需要遍历修复所有祖先节点，最坏的情况为)#card=math&code=O%28log%28n%29%29)
3. 可以按照v，p，g三个节点的位置，进行Zigzig,Zagzag,Zigzag,Zagzig操作，进而使树重平衡
4. Zigzig,Zagzag,Zigzag,Zagzig可以根据BST的顺序性，进一步优化为3+4重构，简化步骤以及逻辑复杂性。

定义

AVL是Adelson-Velsky and Landis首字母的简写，AVL是自平衡的二叉搜索树（self-balancing binary search tree）。AVL的规则入下：

• 一个节点的平衡因子是其右子树与左子树高度之差，公式：%3Dhight(RightSubtree(N))%20-%20hight(LeftSubtree(N))#card=math&code=balFun%28N%29%3Dhight%28RightSubtree%28N%29%29%20-%20hight%28LeftSubtree%28N%29%29)
• 一个节点的平衡因子只能是-1、0、1中的一个，即节点的平衡因子绝对值不大于1。公式：%20%5Cin%20%5C%7B-1%2C0%2C1%5C%7D#card=math&code=balFun%28N%29%20%5Cin%20%5C%7B-1%2C0%2C1%5C%7D)

注意：

树的高度为所有节点中的深度最大值，称作该树的高度#card=math&code=height%28h%29)。
节点的深度为所在层数。
所以以一个节点为根的子树的高度，可以理解为该子树，最深处的节点到该节点的最短距离。

如何界定适度平衡的标准？

如果我们定义一棵高度为h的AVL树，所包含的最小节点数为#card=math&code=S%28h%29)。如下图所示：

1. 从AVL对平衡因子的约束可知: %20%3D%20S(h-1)%20%2B%20S(h-2)%20%2B%201#card=math&code=S%28h%29%20%3D%20S%28h-1%29%20%2B%20S%28h-2%29%20%2B%201)。
2. 如果将等式两边同时+1，%20%2B%201%20%3D%20(S(h-1)%20%2B%201)%20%2B%20(S(h-2)%20%2B%201)#card=math&code=S%28h%29%20%2B%201%20%3D%20%28S%28h-1%29%20%2B%201%29%20%2B%20%28S%28h-2%29%20%2B%201%29)
3. 定义%20%3D%20S(h)%20%2B%201#card=math&code=T%28h%29%20%3D%20S%28h%29%20%2B%201)，则 %20%3D%20T(h-1)%20%2B%20T(h%20-%202)#card=math&code=T%28h%29%20%3D%20T%28h-1%29%20%2B%20T%28h%20-%202%29)

大家对%20%3D%20T(h-1)%20%2B%20T(h%20-%202)#card=math&code=T%28h%29%20%3D%20T%28h-1%29%20%2B%20T%28h%20-%202%29)这个公式熟悉不？这不就是斐波那契数吗？如果你学习过动态规划，那这个公式一定是你的入门题。我们可以利用数学归纳法继续推导，可以推导出的结论为：

• 一棵高度为h的AVL树，至少包含的节点数为%20%3D%20fib(h%20%2B%203)%20-%201#card=math&code=S%28h%29%20%3D%20fib%28h%20%2B%203%29%20-%201)

进而可知一棵AVL树，节点数的下界为斐波那契数，即$ n = \varOmega (\Phi ^ h) h = O(log(n))log(n)$，达到了上面我们所说的适度平衡。

重平衡 - 插入操作

插入操作的第一原则：插入操作一定是在叶节点进行的。因为AVL本身也是一颗BST，所以插入一个新节点时一定会先遍历到最深的叶节点处，才会进行插入操作。

如果我们在叶节点进行插入，有可能将这个叶节点的高度加1，也可能高度不变。如下图所示，叶节点为v，虚线节点为可能插入的节点位置，绿色节点为已有节点。

• 如果当前节点有孩子，并且插入的节点为与其对应的另一个位置，则此时v的高度不变。进而可知，整棵树的平衡性不会遭到破坏。
• 如果当前节点没有孩子，那么无论插入的位置是左孩子，还是右孩子的位置，都将导致v的高度加一：%20%2B%201#card=math&code=h%28v%29%20%2B%201)。我们下面会着重分下下这种情况，因为涉及到高度变化，可能会影响到整颗树的平衡性。
• 所以在最高的子树中，进行插入操作，可能会使原本就比较高的子树，高度加一，进而导致失衡。

下面我们分析下可能导致高度变化的插入行为，如何重平衡。以下所有示例中：

• v为当前节点
• p为parent节点，即父节点
• g为grandparent节点，即祖父节点

单旋 — Zigzig/Zagzag

注意，这种情况下，一定是%20%3D%20h(T2)%20%3D%20h(T3)#card=math&code=h%28T1%29%20%3D%20h%28T2%29%20%3D%20h%28T3%29)

• 如果%20%3E%20h(T3)#card=math&code=h%28T2%29%20%3E%20h%28T3%29)或者%20%3E%20h(T3)#card=math&code=h%28T2%29%20%3E%20h%28T3%29)，那么g在插入L，R之前已经失衡了, 因为%2C%20h(T3))%20%2B%202%20-%20h(T0)%20%3E%201#card=math&code=max%28h%28T2%29%2C%20h%28T3%29%29%20%2B%202%20-%20h%28T0%29%20%3E%201)
• 如果%20%3E%20h(T1)#card=math&code=h%28T2%29%20%3E%20h%28T1%29)或者%20%3E%20h(T1)#card=math&code=h%28T3%29%20%3E%20h%28T1%29)，那么g在插入L，R之前已经失衡了，因为%2C%20h(T3))%20%2B%202%20-%20h(T0)%20%3E%201#card=math&code=max%28h%28T2%29%2C%20h%28T3%29%29%20%2B%202%20-%20h%28T0%29%20%3E%201)
• 如果%20%5Cge%20h(T1)#card=math&code=h%28T0%29%20%5Cge%20h%28T1%29), 那么插入L，R之后，不会影响g的高度。
• 所以在最高的子树上进行插入可能会导致失衡现象

如上图所示，虚线框中的L和R代表可能插入的位置。由于原来%20%3D%20h(v)%20%2B%202%20-%20h(T0)#card=math&code=balFun%28g%29%20%3D%20h%28v%29%20%2B%202%20-%20h%28T0%29)，现在v的两颗子树中可能已经插入了节点，导致v的高度从L2转移到了L3，进而导致了g的高度失衡。这种情况我们定义为ZagZag（也有的称之为LL，g和p都在逆时针方向）。

要修复这种情况，也很简单。只需在失衡的g节点执行一次Zag操作就可以了。如图所示:

现在g的高度已经恢复到了%20-%20h(T0)#card=math&code=h%28T1%29%20-%20h%28T0%29)，已经重平衡了。经过这个操作后，g的祖宗节点会不会失衡呢？答案是否定的，不会。我们来分析下，图中的Rc代表g的上层节点：

• 平衡前：rc的高度为%20%3D%20h(v)%20%2B%203#card=math&code=h%28rc%29%20%3D%20h%28v%29%20%2B%203)，因为v和rc中间相隔了两个节点（p, g）。由于#card=math&code=h%28v%29)增加了1，#card=math&code=h%28rc%29)也增加了1。
• 平衡后：%20%3D%20h(T2)%20%2B%202#card=math&code=h%28rc%29%20%3D%20h%28T2%29%20%2B%202)，因为从v到rc只相隔一个节点p。所以由于#card=math&code=h%28v%29)增加了1，#card=math&code=h%28rc%29)不再变化。

Zigzig的情况和Zagzag差不多，只需要将zig(g)就可以重平衡。所以单旋的复杂度为#card=math&code=O%281%29)，因为只用修复一个节点。

双旋 — Zagzig/Zigzag

此时g的失衡是由于在v的左右子树下面插入R或者L，导致v的高度变化，进而导致g的变化。由于p在v的顺时针方向，g在p的逆时针方向，我们称这种情况为Zigzag。那么这种情况下，该如何重平衡呢？

首先，我们在p处进行一次Zig操作，如下图所示：

然后，在g处做一次zag操作，如下图所示：

我们可以分析下，重平衡前后节点的高度。
重平衡前：

• v的高度为%20%3D%20max(h(T0)%2C%20h(T1))%20%2B%201#card=math&code=h%28v%29%20%3D%20max%28h%28T0%29%2C%20h%28T1%29%29%20%2B%201)
• p的高度为%20%3D%20max(h(T0)%2B1%2C%20h(T1)%2B1%2C%20h(T3))%20%2B%201#card=math&code=h%28p%29%20%3D%20max%28h%28T0%29%2B1%2C%20h%28T1%29%2B1%2C%20h%28T3%29%29%20%2B%201)

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)操作。如下图所示：

我们简单分析下旋转前的情况：

1. 原来g的左子树的高度为%20%2B%203#card=math&code=h%28T0%29%20%2B%203)，或者%20%2B%203#card=math&code=h%28T1%29%20%2B%203)，或者%20%2B%202#card=math&code=h%28T2%29%20%2B%202)
2. 原来g的右子树的高度为#card=math&code=h%28T3%29), 由于T3的高度减了1导致失衡。
3. 所以g的平衡因子为%3Dmax(h(T0)%20%2B%203%2C%20h(T1)%20%2B%203%2C%20h(T2)%20%2B%202)%20-%20h(T3)#card=math&code=balFun%28g%29%3Dmax%28h%28T0%29%20%2B%203%2C%20h%28T1%29%20%2B%203%2C%20h%28T2%29%20%2B%202%29%20-%20h%28T3%29)
4. RC的在g的分支上的高度为%20%2B%203%2C%20h(T1)%20%2B%203%2C%20h(T2)%20%2B%202)%20%2B%201#card=math&code=max%28h%28T0%29%20%2B%203%2C%20h%28T1%29%20%2B%203%2C%20h%28T2%29%20%2B%202%29%20%2B%201)

旋转后呢？

1. RC的子节点变为了p，
2. p的左子树的高度为%20%2B%202#card=math&code=h%28T0%29%20%2B%202)，或者%20%2B%202#card=math&code=h%28T1%29%20%2B%202)
3. p的右子树的高度为%20%2B%201#card=math&code=h%28T2%29%20%2B%201)，或者#card=math&code=h%28T3%29)
4. 失衡的g的节点高度由%20%2B%203%2C%20h(T1)%20%2B%203%2C%20h(T2)%20%2B%202)%20-%20h(T3)#card=math&code=max%28h%28T0%29%20%2B%203%2C%20h%28T1%29%20%2B%203%2C%20h%28T2%29%20%2B%202%29%20-%20h%28T3%29)，变成了%20%2B%201)%20-%20h(T3)#card=math&code=max%28h%28T2%29%20%2B%201%29%20-%20h%28T3%29)。可以看到以g的角度来看，由于T3到高度减少了1，旋转后g到T2的距离减少了1，所以重新平衡了。
5. RC的在p的分支上的高度为%20%2B%202%2C%20h(T1)%20%2B%202%2C%20h(T2)%20%2B%202)%20%2B%201#card=math&code=max%28h%28T0%29%20%2B%202%2C%20h%28T1%29%20%2B%202%2C%20h%28T2%29%20%2B%202%29%20%2B%201)

g重平衡了，那么RC呢？
如果%3Dh(T1)%3Dh(T2)#card=math&code=h%28TO%29%3Dh%28T1%29%3Dh%28T2%29)，那RC的高度岂不是由%20%2B%203%20%2B%201#card=math&code=h%28T0%29%20%2B%203%20%2B%201)变成了%20%2B%202%20%2B%201#card=math&code=h%28T0%29%20%2B%202%20%2B%201)。如果当前分支，本来就是RC中相对矮的分支，RC又可能失衡？RC旋转后，RC的祖宗又可能失衡。

很尴尬的场景，当我们修复完一个节点后，这个失衡可能传播到其祖宗节点。如果修复一个节点的操作数为#card=math&code=O%281%29)，那修复整颗树，最坏情况下可能需要)#card=math&code=O%28log%28n%29%29)。

我们上面分析的是Zigzig的情况，Zagzag的情况和上面情况是相同的，无非是做zag操作。下面我们分析下双旋的情况。

双旋 — Zagzig/Zigzag

上图是双旋的Zagzig情况，p在v的逆时针方向，g在p的顺时针方向。灰色部分代表可能是最高的子树，T3下面的红色方块，代表T3是相对较矮的树，我们会在其中删除一个节点。可以看到如果T3中移除了一个节点，那么g将失衡。修复的方式很简单，同样是zag，zig操作。

可以理解第一次Zag操作，三个节点变成了单旋的情况，再单旋一次就可以重平衡了。我们同样分析下，经历Zagzig前后节点高度的变化。
双旋前：

• v的高度为%20%3D%20max(h(T1)%2C%20h(T2))%20%2B%201#card=math&code=h%28v%29%20%3D%20max%28h%28T1%29%2C%20h%28T2%29%29%20%2B%201),
• p的高度为%20%3D%20max(h(T0)%2C%20h(v))%20%2B%201#card=math&code=h%28p%29%20%3D%20max%28h%28T0%29%2C%20h%28v%29%29%20%2B%201)
• 进而可知g的左子树高度为%20%2B%202%2C%20h(T2)%20%2B%202%2C%20h(T0)%20%2B%201)#card=math&code=max%28h%28T1%29%20%2B%202%2C%20h%28T2%29%20%2B%202%2C%20h%28T0%29%20%2B%201%29)，因为原来是平衡的，当T3的高度减少1以后，%20%3D%202#card=math&code=balFun%28v%29%20%3D%202)，进而失衡。
• 此时RC的子树高度为%20%2B%201%2C%20h(T1)%20%2B%202%2C%20h(T2)%20%2B%202)#card=math&code=max%28h%28T0%29%20%2B%201%2C%20h%28T1%29%20%2B%202%2C%20h%28T2%29%20%2B%202%29)

双旋后：

• p的高度为%20%3D%20max(h(T0)%2C%20h(T1))%20%2B%201#card=math&code=h%28p%29%20%3D%20max%28h%28T0%29%2C%20h%28T1%29%29%20%2B%201)
• g的高度为%20%3D%20max(h(T2)%2C%20h(T3))%20%2B%201#card=math&code=h%28g%29%20%3D%20max%28h%28T2%29%2C%20h%28T3%29%29%20%2B%201)，所以尽管T3的高度减少了1，但是T2到g的距离也减少的1，进而g重新处于平衡状态。
• v的高度为%20%3D%20max(h(p)%2C%20h(g))%20%3D%20max(h(T0)%20%2B%201%2C%20h(T1)%20%2B%201%2C%20h(T2)%20%2B%201)#card=math&code=h%28v%29%20%3D%20max%28h%28p%29%2C%20h%28g%29%29%20%3D%20max%28h%28T0%29%20%2B%201%2C%20h%28T1%29%20%2B%201%2C%20h%28T2%29%20%2B%201%29)
• 此时RC的子树高度变为了%20%2B%201%2C%20h(T1)%20%2B%201%2C%20h(T2)%20%2B%201)#card=math&code=max%28h%28T0%29%20%2B%201%2C%20h%28T1%29%20%2B%201%2C%20h%28T2%29%20%2B%201%29)，可以对比原来RC子树的高度看到，RC的子树高度减少了1。如果此时该子树为相对较矮的子树，或者说RC节点的平衡因子正好是1，那经历旋转操作后RC又失衡了。

所以双旋操作也同样有失衡传播的情况，虽然双旋经历了两次操作，但是复杂度也是#card=math&code=O%281%29)，但整颗树重平衡的操作复杂度为)#card=math&code=O%28log%28n%29%29)

源码示例

和插入操作一样，以g的孙子节点v开始做旋转操作，调用rotateAt。但是并不是一次重平衡就跳出循环。而是要遍历当前节点的祖宗节点。

双旋以及单旋原理分析

我们学树相关的数据结构的时候，很容易弄混这些旋转操作。那AVL的旋转有什么规律可循吗？

1. 都是Zig/Zag或者其组合形式。
2. 可以根据失衡节点的位置来判断具体要做什么操作。
3. 插入操作只需一次重平衡，
4. 删除操作最坏需要#card=math&code=log%28n%29)次重平衡操作。

ZigZag的代码其实不难写，但还有没有优化的空间？这里还是要用到BST的顺序性的特点，来优化我们的Zig/Zag操作。

3+4重构

如果上面的每次旋转都是以修复一个物品的角度看待问题。那么3+4重构是一个把物品打散重构的角度。我们依然用上面的字母来代表树中的一些元素：

• 如果g为最低的失衡节点，考察祖孙三代：g ~ p ~ v

  • 按中序遍历序列，将其命名为：A、B、C三个节点。

• 三个节点，可能拥有的最大不相交子树为4个，例如我们上面分析用到的T0,T1,T2,T3

  • 按中序序列遍历，将其命名为：T0、T1、T2、T3

如上图所示，可以发现亮点：

1. 无论你上面的树是如何旋转，树的中序序列是不变的。
2. 每次旋转都无非是想将一个非对称的树，转为对称的平衡状态。因为这种情况下树的高度最低，即在不考虑T0,T1,T2,T3内部节点的情况下，这种对称的状态为高度最低，达到CMT的平衡。

那么我们能不能不用旋转，直接重构呢？答案是肯定的，当然可以。只要每次我们都将：

1. B为子树的树根
2. A为B的左节点
3. C为B的右节点
4. T0、T1为A的左右子树
5. T2、T3为B的左右子树

3 + 4 重构源码

可以看到代码很简单，是不是比旋转要简单的多呢？现在我们可以利用3+4重构实现rotateAt源码了。

rotateAt源码

所有的zigzag操作都变得极为简单。同样的，我们思考问题的角度也可以变得很简单。

总结

AVL平衡因子绝对值不大于的设定，来保证整棵树高度在渐进意义下接近#card=math&code=log%28n%29)。同时通过ZigZag操作来实现重平衡操作。可能这些旋转对于我们来说很难记忆，但我们可以用3+4重构来理解其中的原理。

后面我们会讲一些高级搜索树，预计在每个周末更新文章，如果大家喜欢的话，可以点波关注，或者收藏。

参考资料

1. 数据结构（下）-邓俊辉，学堂在线 http://www.xuetangx.com/courses/course-v1:TsinghuaX+30240184_2X+sp/courseware/06d6c305fca54193901007d83cd6e74e/6c692546abdf46f0becab46cf51bbce6/