浅析AVL树–AVL树的双旋转

浅析AVL树–AVL树的双旋转

接上篇博文:浅析AVL树–AVL树的概念及单旋转

AVL树如何恢复平衡之双旋转

首先假设我们有一颗已经处于平衡的AVL树:


上篇博文已经解决了LL和RR两种情况的平衡恢复解决方案—-单旋转。这篇博文来看双旋转情形。这时候我们插入结点7,我们可以发现这时这棵树并没有失去平衡:


但是,如果我们继续插入结点8,这棵树就会再次处于失衡状态:


我们首先可以发现结点9左右子树高度差2—这是第一个失衡的结点。
然后我们可以发现结点6左右子树高度差2—这是第二个失衡的结点。
最后发现根节点3也失衡了—它的左右子树高度同样差2。

我们首先从离插入的结点8最近的结点9开始处理。为了方便起见我们将结点9单独提出来考虑:

可以看到此时结点9失衡的原因是结点9的左儿子(L)的右子树(R)被插入了新结点8。如果我们这时候尝试单旋转对它进行修复,我们会发现这种修复方式无效:


但是,我们这样想:如果先将结点7和结点8执行RR单旋转,那么这棵树就变成了LL单旋转可修复情形了:

然后我们可以执行LL单旋转进行修复:


如上图所示,我们成功地将新插入结点8而造成的失衡成功通过两次单旋转修复,这种修复的方式我们称为LR双旋转(因为树的失衡原因是在结点9的左儿子的右子树插入了新结点)。有些童鞋可能会担心旋转之前结点8可能还会有左右儿子从而被覆盖丢失,其实无需担心,因为执行的两次单旋转里已经考虑到了这个问题而对结点8的左右儿子进行了挪动。
通过上面这个例子,我们可以总结LR双旋转的伪代码如下:

对当前结点的左儿子进行RR单旋转;
对当前结点进行LL单旋转;
返回旋转后结果;

执行完一次修复后此时整棵树如下:


我们发现这棵树再次平衡了–结点6和结点3也平衡了,这是因为本身这两个结点失衡的原因就是结点6、结点3的右子树高度改变了,修复之后,自然就平衡了。

对应的,假如上面失衡的情况是这样的:


这种情况称为RL失衡。我们可以通过进行RL双旋转来进行修复,即先对结点9和结点8进行一次LL单旋转,再对整棵树进行一次RR单旋转:


我们可以总结出RL双旋转的伪代码如下:

对当前结点的右儿子进行LL单旋转;
对当前结点进行RR单旋转;
返回旋转后结果;

关于AVL树的C++实现请看下篇博文:
浅析AVL树–AVL树的C++实现

One comment:

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

Protected with IP Blacklist CloudIP Blacklist Cloud

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据