AVL树

前面介绍了二叉查找树,二叉查找树的平均时间复杂度为O(logN),是相当低的,因此是一种非常优异的模型。但是这只是对一个随机输入的二叉查找树有效(平衡的二叉树)。当我们进行一定次数的插入(或删除)后,可能会导致二叉树不平衡,甚至退化成链表,这样会重新使时间复杂度变为O(logN).因此,引入AVL树。

AVL树是Adelson-Velskii和Landis于1962年发明的自平衡二叉树。在一个二叉树中引入平衡条件,最简单的当然是每个节点的左子树和右子树的高度一样。但是这个条件太强了,因此AVL树引入例如下面的一个限制:

每个节点的左子树的高度和右子树的高度的差的绝对值不超过1(空树的高度定义为-1)

旋转

对于AVL树,除了插入结点外,所有的操作都可以在O(logN)的时间内完成。对于插入节点的情况,插入可能会破坏AVL树的约束条件,而我们可以通过对树的适当旋转来修正。
avlTree1

对一个AVL树插入一个节点,分4中情况

  • 对左子树插入左子节点

  • 对右子树插入左子节点

  • 对左子树插入右子节点

  • 对右子树插入右子节点

其中(1)和(4)是镜面对称情况,(2)和(3)是镜面对称情况,因此他们相应的旋转情况是一致的,因此这里只分析(1)和(2)的情况。

  • 单旋转:

对于(1)的情况适用于单旋转,如上面的图所示,插入节点5,就是在左子树插入左子节点,这个结果直接导致了不符合AVL的约束条件,对于节点7来说,它已经失去了平衡了,节点4,8的失衡也是由于节点7的失衡,因此为了恢复平衡,我们要把节点7的左子树提高一个level,把节点7的右子树降低一个level,因此可以得到上图的旋转后的结果

要旋转之前首先要清晰到底应该是哪个节点导致的不平衡。

对于编程实现来说,旋转本质上是指针的一些改变

从上图可以看到旋转后的树与旋转前的树的高度是一样的。这其实很好理解,正因为增加了一个节点导致树变深了,进而导致了unbalance,所以通过旋转必然要减掉这个深度,否则一样的unbalance.

  • 双旋转:

对应于(2)的情况,单旋转已经不能解决问题了。因此要引入两次但旋转,即双旋转来解决

avlTree2

在这个例子中根节点8是平衡的,不平衡的是节点9,因此要对节点9做双旋转。

另一个例子:

avlTree3

这个例子中根节点6不平衡,因此要对根节点做旋转。

代码实现

AVL树的定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct Avltree;
typedef struct AvlNode *AvlTree;
typedef AvlTree Position;

struct AvlNode
{
ElementType Element;
AvlTree Left;
AvlTree Right;
int Height;
};

// calculate height
static int Height(Position P)
{
if(P==NULL)
return -1;
else
return P->Height;
}

插入节点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
AvlTree Insert(Element X,AvlTree T)
{
if(T==NULL)
{
T = malloc(sizeof(struct AvlNode));
if(T==NULL)
Error("Out of Space!");
T->Left = T->Right = NULL;
T->Element = X;
T->Height = 0;
}
else if(X<T->Element)
{
T->Left = Insert(X,T->Left);
//if X==T->Left,the next if condition is false,it will do nothing
if(Height(T->Left) - Height(T->Right)==2)
if(X<T->Left->Element)
T = SingleRotateWithLeft(T);
else
T = DoubleRotateWithLeft(T);
}
else if(X>T->Element)
{
T->Right = Insert(X,T->Right);
if(Height(T->Right) - Height(T->Left)==2)
if(X>T->Right->Element)
T = SingleRotateWithRight(T);
else
T = DoubleRotateWithRight(T);
}

T->Height = Max(Height(T->Left),Height(T->Right))+1;
return T;
}

左节点单旋转:

avlTree4

1
2
3
4
5
6
7
8
9
10
Position SingleRotateWithLeft(Position P1)
{
Position P2;
P2 = P1->Left;
P1->Left = P2->Right;
P2->Right = P1;
P1->Height = Max(Height(P1->Left),Height(P1->Right));
P2->Height = Max(Height(P2->Left),P1->Height);
return P2; //new root
}

右节点单循环:(与上面的是镜面对称)

1
2
3
4
5
6
7
8
9
10
Position SingleRotateWithRight(Position P1)
{
Position P2;
P2 = P1->Right;
P1->Right = P2->Left;
P2->Left = P1;
P1->Height = Max(Height(P1->Left),Height(P1->Right));
P2->Height = Max(Height(P2->Right),P1->Height);
return P2; //new root
}

下面是双旋转:其实双旋转的编程实现比较简单,就是把单旋转做两遍,一次左,一次右。

左节点双旋转:
avlTree5

1
2
3
4
5
Position DoubleRotateWithLeft(Position P3)
{
P3->Left = SingleRotateWithRight(P3->Left);
return SingleRotateWithLeft(P3);
}

右节点双旋转:

1
2
3
4
5
Position DoubleRotateWithRight(Position P3)
{
P3->Right = SingleRotateWithLeft(P3->Right);
return SingleRotateWithRight(P3);
}

这两个双旋转是镜面对称的。

总结:

AVL树是平衡的二叉树,它有限制:“每个节点的左子树的高度和右子树的高度的差的绝对值不超过1”(空树的高度定义为-1)。对AVL树插入值很有可能导致二叉树不再平衡,因此可以通过旋转来消除这种不平衡。旋转分单旋转和双旋转,分别对应于不同的插入情况。最多只需要双旋转。