浅析AVL树–AVL树的概念及单旋转

什么是AVL树?

目录:
浅析AVL树–AVL树的概念及单旋转(本文)
浅析AVL树–AVL树的双旋转
浅析AVL树–AVL树的C++实现
AVL树(平衡二叉树)是一种带有平衡条件的查找二叉树。一般来说,要求一棵AVL树的左右子树高度最多相差1。如下图所示,下面是一个平衡了的AVL树,它的每一个结点的左右子树高度最多相差1。

当我们插入了新结点1之后,这棵就不是平衡二叉树了,因为它的根节点左右子树高度相差2:

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

我们可以观察到之所以引起了不平衡是因为新插入的结点1破环了根节点的平衡性,使得根节点左右子树相差2。对于上述的情况,我们可以想办法使得根节点的左子树的高度减一,如下图所示,我们让结点3和结点6绕着旋转轴“旋转”一下,让已经不平衡的根节点的 左子树做为新的根节点,就可以让这棵二叉树重新平衡:


请注意,由于结点3的右子树在旋转完成后被结点6占用,因此结点3的原右子树–结点4在旋转完成之后做了结点6的左子树(结点6的左子树在旋转完成之后左子树空了出来)。这样旋转完成之后,我们发现整棵树在继续保持查找二叉树的性质的同时重新平衡了。

上面的旋转我们称之为LL单旋转—-LL的意思是原二叉树失衡的原因是因为在根节点的左儿子(L)的左子树(L)上插入了新结点。

根据上面的讨论,我们可以总结出执行LL单旋转的伪代码:

void LL单旋转(当前指向的结点指针) //对应于上图,目前指向的是已经失衡的根结点6
{
    备份当前结点指针的左子树指针;//对于于上图,备份的是上图的结点6指向结点3的指针
    将备份指针指向的结点的右子树指针赋给当前结点的左指针;//对应于上图,将结点4赋给结点6做左儿子
    将当前结点指针赋给备份指针的右指针;//对应于上图,对结点对3-6左旋转
    更新左右子树的高度信息;//由于结点结构改变,所以必须重新计算高度信息
    返回新的结点指针为备份的指针;//对应于上图,当前指针变为了原来结点的左儿子来维持平衡
}

在上述二叉树我们继续插入新结点9,我们发现这棵二叉树并没有失衡:

但是我们继续尝试插入结点10,我们发现这个二叉树再次去失平衡—-这次失去平衡的原因是在结点8的右儿子(R)(结点9)的右子树(R)插入的新结点10,导致结点8的左右子树高度相差2:


这时我们需要做一个RR单旋转让整个二叉树再次恢复平衡:


同样的,可以总结出执行RR单旋转的伪代码:

void RR单旋转(当前指向的结点指针) //对应于上面的结点8
{
    备份当前结点指针的右子树指针;//对于于上图,备份的是上图的结点8指向结点9的指针
    将备份指针指向的结点的左子树指针赋给当前结点的右指针;
    将当前结点指针赋给备份指针的左指针;//对应于上图,对结点对8-9右旋转
    更新左右子树的高度信息;//由于结点结构改变,所以必须重新计算高度信息
    返回新的结点指针为备份的指针;//对应于上图,当前指针变为了原来结点的右儿子来维持平衡
}

One comment:

发表评论

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

Protected with IP Blacklist CloudIP Blacklist Cloud

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