ITEEDU

AVLT自平衡二叉查找树

AVL树定义

在计算机科学中,AVL树是最先发明的自平衡二叉查找树(Balanced Binary Search Tree,BBST)。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis,他们在1962年的论文《An algorithm for the organization of information》中发表了它。

节点的平衡因子是它的右子树的高度减去它的左子树的高度。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的,并需要重新平衡这个树。平衡因子可以直接存储在每个节点中,或从可能存储在节点中的子树高度计算出来。

关键问题

AVL树的操作中异于普通二叉查找树的地方是插入和删除过程。

插入

插入过程可能会导致不平衡的情况出现,这样我们就需要对这些情况进行处理-----即旋转。先来个详细的图:(Root是失去平衡的树的根结点,pivot是旋转后重新平衡的树的根结点。

总共有四种情况插入导致不平衡:(不平衡结点为上图中的root)

(1)不平衡结点的左子树的左子树高度增加,导致不平衡结点的左子树结点高度增加,如果不平衡结点的左子树结点高度原来就比不平衡结点的右子树结点高度大一,则现在变为大2.导致不平衡结点的平衡因子由-1变为-2。需要对不平衡结点进行右旋,即把不平衡结点移动到它的右孩子的位置,将左孩子移动到它的位置上,并将左孩子的右子树接到不平衡结点的左孩子上。

(2)不平衡结点的右子树的右子树高度增加,导致不平衡结点的右子树结点高度增加,如果不平衡结点的右子树结点高度原来就比不平衡结点的左子树结点高度大一,则现在变为大2.导致不平衡结点的平衡因子由1变为2。需要对不平衡结点进行左旋,即把不平衡结点移动到它的左孩子的位置,将右孩子移动到它的位置上,并将右孩子的左子树接到不平衡结点的右孩子上。

下面两种情况进行一次旋转并不能使树恢复平衡,需要进行两次旋转。

(3)不平衡结点的左子树的右子树高度增加,导致不平衡结点的左子树结点高度增加,如果不平衡结点的左子树结点高度原来就比不平衡结点的右子树结点高度大一,则现在变为大2.导致不平衡结点的平衡因子由-1变为-2。先进行左旋使树变为(1)的情况,再进行右旋。

(4)不平衡结点的右子树的左子树高度增加,导致不平衡结点的右子树结点高度增加,如果不平衡结点的右子树结点高度原来就比不平衡结点的左子树结点高度大一,则现在变为大2.导致不平衡结点的平衡因子由1变为2。先进行右旋使树变为(2)的情况,再进行左旋。

知道了四种需要进行旋转的情况,我们知道有不平衡结点后该如何进行位置调整。但是如何知道查找平衡结点呢?当我们进行插入时,需要将插入元素不断地与树中的结点进行比较,然后决定插入它的左子树还是它的右子树,这条路径记录了插入元素和哪些结点相关(即哪些结点的左子树或右子树插入了元素)。这条路径上的结点的平衡因子可能会发生变化,记住是可能。

调整平衡因子

插入结点后,插入路径上的结点的平衡因子需要进行调整以表达现在的平衡情况。是不是在插入路径范围进行变化呢?不是。之后的回溯过程会从插入路径回溯,直到找到不平衡点,找到不平衡点后,不平衡点的祖先结点们的平衡因子是不用改变的。从插入结点到不平衡结点中的每个结点之间的平衡因子需要怎么变化呢?因为它们的平衡因子之前都是0.现在插入了新结点,这些结点的高度都会加1.如果插入元素小于结点值,则结点平衡因子-1,大于则结点平衡因子+1(分别对应插入了结点的哪个子树中)。至于为什么么这些结点的平衡因子都是之前都是零0,看获得不平衡点。

获得不平衡点

分析旋转的四种情况,不然发现,旋转前和旋转后,子树t的高度是没有变化的。也就是说只需要找到路径中和插入结点最近的不平衡点,然后以该不平衡结点进行旋转处理,则路径中该不平衡结点的祖先结点们的平衡因子是不变的。该结点即为不平衡点,即旋转中的root结点。由此可见插入新元素后不平衡点可能大于一个,但是经过对离插入结点最近的不平衡点进行旋转调整后,不平衡点全部消失。如何判断谁是可能是最近的不平衡点呢?插入路径中离插入结点最近的插入时平衡因子不等于0的结点即为可能的不平衡点。为什么呢?因为如果结点平衡因子是0,插入一个结点不会导致该结点的平衡因子变为+2,或者-2。但是会改变它的父结点的平衡因子,会使父结点的平衡因子变化1。如果父结点的平衡因子之前是0.则继续向上回溯。

(1)如果父结点的平衡因子因为变化1而变为0,则是在父结点的较短的子树中插入了新结点导致子树高度加1,使父结点平衡因子变为了0。父结点为根的子树高度没有变化,则祖先们的平衡因子不需要变化,所以得到没有平衡因子的结论。

2)如果父结点的平衡因子因为变化1而变为-2或者+2,那么父结点成为了不平衡结点,需要以父结点为根进行旋转变化。至于使用哪种变化,首先根据父结点与插入值的大小关系,插入值小于该结点,则为L,大于则为R。再根据插入值与该结点的左孩子(L)或者右孩子(R)进行大小比较得出。LL、LR、RR、RL四种情况之一进行位置调整。

旋转后平衡因子调整

上面获取不平衡结点后,进行了位置调整,但是位置调整后平衡因子也需要再次调整。

一、LL型平衡因子调整

二、LR型平衡因子调整

三、RR型平衡因子调整

四、RL型平衡因子调整