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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
| #include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
struct AvlNode;
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;
typedef char ElementType;
AvlTree MakeEmpty(AvlTree &T);
Position Find(ElementType X, AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
AvlTree Insert(ElementType X, AvlTree &T);
AvlTree Delete(ElementType X, AvlTree &T);
ElementType Retrieve(Position P);
struct AvlNode {
ElementType Element;
AvlTree Left;
AvlTree Right;
int Height;
};
AvlTree MakeEmpty(AvlTree &T) {
if (T != NULL) {
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free(T);
}
return NULL;
}
/* Function to compute height of an AVL node */
static int Height(Position P) {
if (P == NULL)
return -1;
else
return P->Height;
}
void DispTree(AvlTree T) {
if (T) {
printf("%d\t", T->Element);
DispTree(T->Left);
DispTree(T->Right);
}
}
int Max(int x, int y) {
return x - y ? x : y;
}
/* This function can be called only if K2 has left child */
/* Perform a rotate between a node (K2) and its left child */
/* Update heights, then return new root */
static Position SingleRotateWithLeft(Position &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) + 1;
return K1; /* New root */
}
static Position SingleRotateWithRight(Position &K2) {
Position K1;
K1 = K2->Right;
K2->Right = K1->Left;
K1->Left = K2;
K1->Height = Max(K2->Height, Height(K1->Right)) + 1;
K2->Height = Max(Height(K2->Left), Height(K1->Right)) + 1;
return K1;
}
/*
* Routine to perform double rotation
* This function can be called only if K3 has a left
* Child and K3's left child has a right child
* Do the left-right double rotation
* Update heights, then return new root
*/
static Position DoubleRotateWithLeft(Position &K3) {
/* Rotate between K1 and K2 */
K3->Left = SingleRotateWithRight(K3->Left);
/* Rotate between K3 and K2 */
return SingleRotateWithLeft(K3);
}
static Position DoubleRotateWithRight(Position &K3) {
/* Rotate between K1 and K2 */
K3->Right = SingleRotateWithLeft(K3->Right);
/* Rotate between K3 and K2 */
return SingleRotateWithRight(K3);
}
/* Insertion into an AVL tree */
AvlTree Insert(ElementType X, AvlTree &T) {
if (T == NULL) {
/* Create and return a one-node tree */
T = (AvlNode *) malloc(sizeof(AvlNode));
if (T == NULL)
printf("Out of space");
else {
T->Element = X;
T->Height = 0;
T->Left = T->Right = NULL;
}
} else if (X < T->Element) {
T->Left = Insert(X, T->Left);
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->Right) == 2)
if (X > T->Right->Element)
T = SingleRotateWithRight(T);
else
T = DoubleRotateWithRight(T);
}
/* Else X is in the tree already; we'll do nothing */
T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
return T;
}
Position FindMin(AvlTree T) {
while (T->Left)
T = T->Left;
return T;
}
Position FindMax(AvlTree T) {
while (T->Right)
T = T->Right;
return T;
}
AvlTree SearchPreviousNode(AvlTree T1, AvlTree T2) {
if (T2) {
if (T2->Left == T1 || T2->Right == T1)
return T2;
SearchPreviousNode(T1, T2->Left);
SearchPreviousNode(T1, T2->Right);
}
return NULL;
}
AvlTree Delete(ElementType X, AvlTree &T) {
AvlNode *TmpCell = NULL;
if (T == NULL) {
printf("删除节点不存在");
return NULL;
} else if (X > T->Element) {
T->Right = Delete(X, T->Right); /* 在右边进行了删除 */
if (Height(T->Left) - Height(T->Right) > 1) { /* 原来是平衡二叉树，现在右边的高度可能减少了，判断是否平衡 */
TmpCell = T->Left; /* 左子树高一点，接着查看左子树的左子树 */
if (Height(TmpCell->Left) >= Height(TmpCell->Right)) /* 查看造成不平衡的是否在左边 即左子树的左子树高一点*/
T = SingleRotateWithRight(T);
else /* 左子树的右子树高一点 LR */
T = DoubleRotateWithRight(T);
}
T->Height = Height(T);
} else if (X < T->Element) {
T->Left = Delete(X, T->Left);
if (Height(T->Right) - Height(T->Left) > 1) { /* 删除后如果失衡 */
TmpCell = T->Right; /* 右子树比左子树高 */
if (Height(TmpCell->Right) >= Height(TmpCell->Left)) /* 做RR */
T = SingleRotateWithRight(T);
else
T = DoubleRotateWithLeft(T); /* 做RL */
}
T->Height = Height(T); /* 更新高度 */
} else if (X == T->Element) {
if (T->Right && T->Left) {
TmpCell = FindMin(T->Right); /* 左右孩子都有时，找到右边最小的，补到T的位置，然后将在T右边最小的删除 */
T->Element = TmpCell->Element;
T->Right = Delete(T->Element, T->Right);
} else {/* 只有一个孩子 */
TmpCell = T;
if (T->Left == NULL)
T = T->Left;
else if (T->Right == NULL)
T = T->Right;
free(TmpCell);
}
}
return T;
}
|