AVL树和伸展树

AVL树

带有平衡条件的二叉树,通常要求每颗树的左右子树深度差<=1

可以将破坏平衡的插入操作分为四种,最后通过旋转恢复平衡



破坏平衡的插入方式 描述 恢复平衡旋转方式
LL 在左儿子的左子树进行插入 右旋转
RR 在右儿子的右子树进行插入 左旋转
LR 在左儿子的右子树进行插入 先左旋转 后右旋转
RL 在右儿子的左子树进行插入 先右旋转 后左旋转

# AVL树的实现 ###
AVL树的节点声明
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct AvlNode ;
typedef struct AvlNode *Poisition ;
typedef struct AvlNode *AvlTree ;

AvlTree MakeEmpty(AvlTree T) ;
Position Find(ElementType X, AvlTree T) ;
Position FindMin(AvlTree T) ;
Position FinMax(AvlTree T) ;
AvlTree Insert(ElementType X, AvlTree T) ;
AvlTree Delete(ElementType X, AvlTree T) ;
ElementType Retrieve(Poisition P) ;

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

计算AVL节点高度函数

1
2
3
4
5
6
7
int Height(Position P)
{
if(P == NULL)
return -1 ;
else
P->Height ;
}

向AVL树插入节点的函数

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
AvlTree Insert(ElementType X, AvlTree T)
{
if(T == NULL)
{
T = malloc(sizeof(struct AvlTree)) ;
if(T == NULL)
Error("内存不足") ;
T->Element = X ;
T->Height = 0 ;
T-Left = T->Right = NULL ;
}
else if(X < T->Element)
{
T->Left = Insert(X,L->Left,)
if(Height(T->Left) - Height(T->Right)) == 2//如果平衡被破坏了,则执行旋转
if(X < T->Left->Element) //LL
T = SingleRotateWithLeft(T) ;
else //LR
T = DoubleRotateWightLeft(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) // RR
T = SingleRotateWithRight(T) ;
else //RL
T = DoubleRotateWithRight(T) ;
}
}

在左儿子上的单旋转

右旋

1
2
3
4
5
6
7
8
9
10
11
Position SingleRotateLeft(Position K2) //K2为平衡被破坏的点
{
Position K1 ;
K1 = K2->Left ;
K2->Left = K1->Right ;
K1->Right = K2 ;
K2->Height = Max(Height(K2->Left),Height(K2->Right)) + 1;
K1->Height = Max(Height(K1->Left),K2->Height) + ;

return K1 ;
}

在左儿子上的双旋转

先左旋后后旋

1
2
3
4
5
6
Position DoubleRotateRight(Position K2)
{
K3->Left = SinglRotateRight(K3->Left) ;

retrun SinglRotateLeft(K3) ;
}

伸展树

目的:加快访问效率

基本想法:当一个节点被访问后,经过一系列的AVL树的旋转到达根节点

伸展树的实现

类型声明

1
2
3
4
5
6
7
8
9
10
struct SplayTree ;
typedef struct SplayTree *Position ;
typedef struct SplayTree *SplayTree ;

Position FindMin(SplayTree T) ;
Position FinMax(SplayTree T) ;
Position Find(SpalyTree T, ElementType X) ;
Position Insert(SpalyTree T, ElementType X) ;
Position Delete(SpalyTree T, ElementType X) ;
Position Splay(SpalyTree T, ElementType X) ;

Find函数

1
2
3
4
5
6
7
8
9
10
11
Position Find(SplayTree T, ElementType X)
{
if(T == NULL)
return NULL ;
else if(X < T->Left->Element)
return Find(T->Left,X) ;
else if(X > T->Right->Element)
return Find(T-Right,X) ;

return T ;
}

Splay函数

把对应节点旋转至根节点,分在左子树和右子树两种情况 ;

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
SplayTree Splay(SplayTree T,ElementType X)
{
SplayTree N ,K1,R,L;
N->Left = N->Right = NULL ;

if(T == NULL)
return NULL ;
while(true)
{
if(X < T->Element)
{
if(T->Left == NULL)
break ;
if(X < T->Left->Element)
{
K1 = T->Left ;
T->Left = K1->Right ;
K1->Right = T ;
if(T->Right == NULL)
break ;
}
R->Left = T ;
R = T ;
T = T->Left ;
}

else if(X > Element)
{
if(T->Right == NULL)
return NULL ;
if(X > T-Right->Element)
{
K1 = T->Right;
T->Right = K1->Left;
K1->left = T;
T = K1;
if (T->Right == NULL)
break;
}
L->Right = T ;
L = T ;
T = T->Right ;
}
else
{
break ;
}
}
L->Right = T->Left;
R->Left = T->Right;
T->Left = N->Right;
Tree->Right = N->Left;

return T ;
}

Delete函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
SplayTree Delete(SplayTree T, ElementType X)
{
SplayTree S ;
if(T == NULL)
return NULL ;
if(Find(T,X) == NULL)
return T ;
T = Splay(T, X);

if (T->Left != NULL)
{
S = Splay(T->Left, X);
S->Right = T->Right;
}
else
S = T->Right ;

free(T);

return X;
}

总结

二叉树、AVL树、伸展树都是一种特殊的树,都是为了更好更快的执行某种操作。