AVL：自平衡二叉查找树

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

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

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

1. 在相对较高的子树上进行插入操作，会导致失衡，但只要修复该情况，并不会导致失衡传播，所以复杂度为

2. 在相对较矮的子树上进行删除操作，会导致失衡，会有失衡传播的情况，所以需要遍历修复所有祖先节点，最坏的情况为

3. 可以按照v，p，g三个节点的位置，进行Zigzig,Zagzag,Zigzag,Zagzig操作，进而使树重平衡

4. 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树，所包含的最小节点数为。如下图所示：

1. 从AVL对平衡因子的约束可知: 。

2. 如果将等式两边同时 +1 ，

3. 定义，则 

大家对这个公式熟悉不？这不就是 「斐波那契数」 吗？如果你学习过动态规划，那这个公式一定是你的入门题。我们可以利用 「数学归纳法」 继续推导，可以推导出的结论为： * 一棵高度为h的AVL树，至少包含的节点数为

进而可知一棵AVL树，节点数的 「下界」 为斐波那契数，即。进而可知高度h的上届为。我们也可以称h在渐进意义上接近，达到了上面我们所说的 「适度平衡」 。

重平衡 - 插入操作

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

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

• 如果当前节点有孩子，并且插入的节点为与其对应的另一个位置，则此时v的高度不变。进而可知，整棵树的平衡性不会遭到破坏。

• 如果当前节点没有孩子，那么无论插入的位置是左孩子，还是右孩子的位置，都将导致v的高度加一：。我们下面会着重分下下这种情况，因为涉及到高度变化，可能会影响到整颗树的平衡性。

• ==所以在最高的子树中，进行插入操作，可能会使原本就比较高的子树，高度加一，进而导致失衡。==

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

• 「v」为当前节点

• 「p」为parent节点，即父节点

• 「g」为grandparent节点，即祖父节点

单旋 -- Zigzig/Zagzag

-w563

如上图所示，虚线框中的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

-w536

此时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)操作。如下图所示： 我们简单分析下旋转前的情况：

1. 原来g的左子树的高度为，或者，或者

2. 原来g的右子树的高度为, 由于T3的高度减了1导致失衡。

3. 所以g的平衡因子为

4. RC的在g的分支上的高度为

旋转后呢？

1. RC的子节点变为了p，

2. p的左子树的高度为，或者

3. p的右子树的高度为，或者

4. 失衡的g的节点高度由，变成了。可以看到以g的角度来看，由于T3到高度减少了1，旋转后g到T2的距离减少了1，所以重新平衡了。

5. 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的旋转有什么规律可循吗？

1. 都是Zig/Zag或者其组合形式。

2. 可以根据失衡节点的位置来判断具体要做什么操作。

3. 插入操作只需一次重平衡，

4. 删除操作最坏需要次重平衡操作。

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

3+4重构

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

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

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

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

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

-w706

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

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平衡因子绝对值不大于的设定，来保证整棵树高度在渐进意义下接近。同时通过ZigZag操作来实现重平衡操作。可能这些旋转对于我们来说很难记忆，但我们可以用3+4重构来理解其中的原理。

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

参考资料

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