数据结构 | 平衡二叉树
发表于 更新于 
作者
次浏览 15 分钟阅读
背景:
AVL(Adelson-Velskii和Landis发明者的首字母)树 是带有平衡条件的二叉查找树。
二叉查找树的性能分析：
- 在一颗左右子树高度平衡情况下，最优的时间复杂度为$O(log_{2}{n})$，这与这半查找相同；
- 在一个只有右子树的二叉树中，最差的时间复杂度会脱变为线性查找$O(n)$。
由于二叉查找树存在以上问题，所以AVL树通过旋转使自身始终保持平衡状态，因此，一颗基于二叉查找树的AVL树具有如下性质：
- 二叉查找树中任何一个结点的左子树和右子树高度相差的绝对值最多为1。
- 它的左、右子树也分别都是平衡二叉树。
如果树在插入过程中出现了不平衡的现象， 则需要通过旋转方式进行平衡处理：
失衡与处理详解：
1. 旋转的方向主要划分为左旋与右旋处理:
左旋代码:
1
2
3
4
5
6
7
8
void L_rotate(BiTree *t)
{
BiTree s;
s = (*t)->rchild; // s指向t的右子树根结点
(*t)->rchild = s->lchild; // s的左子树挂接为t的右子树
s->lchild = (*t);
*t = s; // t指向新的根结点
}
右旋代码：
1
2
3
4
5
6
7
8
void R_rotate(BiTree *t)
{
BiTree s;
s = (*t)->lchild; // s指向t的左子树根结点
(*t)->lchild = s->rchild; // s的右子树挂接为t的左子树
s->rchild = (*t);
*t = s; // t指向新的根结点
}
2. 调平策略:
我们将右子树增高一设置为 +1, 左子树增高一设置为-1. 则树的失衡主要分为四种:
1.单项左旋平衡处理
- 失衡的树平衡度+2, 左子树平衡度+1
- 失衡的树平衡度+2, 左子树平衡度0
2.双向旋转(先左后右)平衡处理:
主要应对失衡树的平衡度为-2, 左子树的平衡度为+1 的情况。
先对左子树进行左平衡处理，再对根进行右平衡处理
3.单项右旋平衡处理:
主要应对两种情况:
- 失衡的树平衡度-2, 右子树平衡度-1
- 失衡的树平衡度-2, 右子树平衡度0
4.双向旋转(先右后左)平衡处理:
主要应对失衡树的平衡度为+2, 右子树的平衡度为-1 的情况。
先对右子树进行右平衡处理，再对根进行左平衡处理
代码:
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
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
/* 二叉树的二叉链表结点结构定义 */
typedef struct BitNode /* 结点结构 */
{
int data; /* 结点数据 */
int bf; /* 结点的平衡因子 */
struct BitNode *lchild, *rchild; /* 左右孩子指针 */
} BitNode, *BiTree;
/* 对以p为根的二叉排序树作右旋处理 */
/* 处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点 */
//右旋-顺时针旋转(如LL型就得对根结点做该旋转)
void R_Rotate(BiTree *P)
{
BiTree L;
L=(*P)->lchild; /* L指向P的左子树根结点 */
(*P)->lchild=L->rchild; /* L的右子树挂接为P的左子树 */
L->rchild=(*P);
*P=L; /* P指向新的根结点 */
}
/* 对以P为根的二叉排序树作左旋处理， */
/* 处理之后P指向新的树根结点，即旋转处理之前的右子树的根结点0 */
//左旋-逆时针旋转(如RR型就得对根结点做该旋转)
void L_Rotate(BiTree *P)
{
BiTree R;
R = (*P)->rchild; /* R指向P的右子树根结点 */
(*P)->rchild = R->lchild; /* R的左子树挂接为P的右子树 */
R->lchild = (*P);
*P = R; /* P指向新的根结点 */
}
#define LH +1 /* 左高 */
#define EH 0 /* 等高 */
#define RH -1 /* 右高 */
/* 对以指针T所指结点为根的二叉树作左平衡旋转处理 */
/* 本算法结束时，指针T指向新的根结点 */
void LeftBalance(BiTree *T)
{
BiTree L,Lr;
L = (*T)->lchild; /* L指向T的左子树根结点 */
switch(L->bf)
{
/* 检查T的左子树的平衡度，并作相应平衡处理 */
case LH: /* 新结点插入在T的左孩子的左子树上，要作单右旋处理 */
(*T)->bf=L->bf=EH;
R_Rotate(T);
break;
case RH: /* 新结点插入在T的左孩子的右子树上，要作双旋处理 */ //
Lr=L->rchild; /* Lr指向T的左孩子的右子树根 */
switch(Lr->bf)
{
/* 修改T及其左孩子的平衡因子 */
case LH:
(*T)->bf=RH;
L->bf=EH;
break;
case EH:
(*T)->bf=L->bf=EH;
break;
case RH:
(*T)->bf=EH;
L->bf=LH;
break;
}
Lr->bf=EH;
L_Rotate(&(*T)->lchild); /* 对T的左子树作左旋平衡处理 */
R_Rotate(T); /* 对T作右旋平衡处理 */
}
}
/* 对以指针T所指结点为根的二叉树作右平衡旋转处理， */
/* 本算法结束时，指针T指向新的根结点 */
void RightBalance(BiTree *T)
{
BiTree R,Rl;
R=(*T)->rchild; /* R指向T的右子树根结点 */
switch(R->bf)
{
/* 检查T的右子树的平衡度，并作相应平衡处理 */
case RH: /* 新结点插入在T的右孩子的右子树上，要作单左旋处理 */
(*T)->bf=R->bf=EH;
L_Rotate(T);
break;
case LH: /* 新结点插入在T的右孩子的左子树上，要作双旋处理 */ //最小不平衡树的根结点为负，其右孩子为正
Rl=R->lchild; /* Rl指向T的右孩子的左子树根 */
switch(Rl->bf)
{
/* 修改T及其右孩子的平衡因子 */
case RH:
(*T)->bf=LH;
R->bf=EH;
break;
case EH:
(*T)->bf=R->bf=EH;
break;
case LH:
(*T)->bf=EH;
R->bf=RH;
break;
}
Rl->bf=EH;
R_Rotate(&(*T)->rchild); /* 对T的右子树作右旋平衡处理 */
L_Rotate(T); /* 对T作左旋平衡处理 */
}
}
/* 若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个 */
/* 数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树 */
/* 失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否。 */
Status InsertAVL(BiTree *T,int e,Status *taller)
{
if(!*T)
{
/* 插入新结点，树“长高”，置taller为TRUE */
*T=(BiTree)malloc(sizeof(BitNode));
(*T)->data=e;
(*T)->lchild=(*T)->rchild=NULL;
(*T)->bf=EH;
*taller=TRUE;
}
else
{
if (e==(*T)->data)
{
/* 树中已存在和e有相同关键字的结点则不再插入 */
*taller=FALSE;
return FALSE;
}
if (e<(*T)->data)
{
/* 应继续在T的左子树中进行搜索 */
if(!InsertAVL(&(*T)->lchild, e, taller)) /* 未插入 */
return FALSE;
if(*taller) /* 已插入到T的左子树中且左子树“长高” */
switch((*T)->bf) /* 检查T的平衡度 */
{
case LH: /* 原本左子树比右子树高，需要作左平衡处理 */
LeftBalance(T);
*taller=FALSE;
break;
case EH: /* 原本左、右子树等高，现因左子树增高而使树增高 */
(*T)->bf=LH;
*taller=TRUE;
break;
case RH: /* 原本右子树比左子树高，现左、右子树等高 */
(*T)->bf=EH;
*taller=FALSE;
break;
}
}
else
{
/* 应继续在T的右子树中进行搜索 */
if(!InsertAVL(&(*T)->rchild,e, taller)) /* 未插入 */
{
return FALSE;
}
if(*taller) /* 已插入到T的右子树且右子树“长高” */
{
switch((*T)->bf) /* 检查T的平衡度 */
{
case LH: /* 原本左子树比右子树高，现左、右子树等高 */
(*T)->bf=EH;
*taller=FALSE;
break;
case EH: /* 原本左、右子树等高，现因右子树增高而使树增高 */
(*T)->bf=RH;
*taller=TRUE;
break;
case RH: /* 原本右子树比左子树高，需要作右平衡处理 */
RightBalance(T);
*taller=FALSE;
break;
}
}
}
}
return TRUE;
}
/*
若在平衡的二叉排序树t中存在和e有相同关键字的结点，则删除之
并返回TRUE，否则返回FALSE。若因删除而使二叉排序树
失去平衡，则作平衡旋转处理，布尔变量shorter反映t变矮与否
*/
int deleteAVL(BiTree *t, int key, int *shorter)
{
if(*t == NULL) //不存在该元素
{
return FALSE; //删除失败
}
else if(key == (*t)->data) //找到元素结点
{
BitNode *q = NULL;
if((*t)->lchild == NULL) //左子树为空
{
q = (*t);
(*t) = (*t)->rchild;
free(q);
*shorter = TRUE;
}
else if((*t)->rchild == NULL) //右子树为空
{
q = (*t);
(*t) = (*t)->lchild;
free(q);
*shorter = TRUE;
}
else //左右子树都存在,
{
q = (*t)->lchild;
while(q->rchild)
{
q = q->rchild;
}
(*t)->data = q->data;
deleteAVL(&(*t)->lchild, q->data, shorter); //在左子树中递归删除前驱结点
}
}
else if(key < (*t)->data) //左子树中继续查找
{
if(!deleteAVL(&(*t)->lchild, key, shorter))
{
return FALSE;
}
if(*shorter)
{
switch((*t)->bf)
{
case LH:
(*t)->bf = EH;
*shorter = TRUE;
break;
case EH:
(*t)->bf = RH;
*shorter = FALSE;
break;
case RH:
RightBalance(&(*t)); //右平衡处理
if((*t)->rchild->bf == EH) //注意这里，画图思考一下
*shorter = FALSE;
else
*shorter = TRUE;
break;
}
}
}
else //右子树中继续查找
{
if(!deleteAVL(&(*t)->rchild, key, shorter))
{
return FALSE;
}
if(shorter)
{
switch((*t)->bf)
{
case LH:
LeftBalance(&(*t)); //左平衡处理
if((*t)->lchild->bf == EH) //注意这里，画图思考一下
*shorter = FALSE;
else
*shorter = TRUE;
break;
case EH:
(*t)->bf = LH;
*shorter = FALSE;
break;
case RH:
(*t)->bf = EH;
*shorter = TRUE;
break;
}
}
}
return TRUE;
}
void InOrderTraverse(BiTree t)
{
if(t)
{
InOrderTraverse(t->lchild);
printf("%d ", t->data);
InOrderTraverse(t->rchild);
}
}
int main(void)
{
int i;
int a[10]={3,2,1,4,5,6,7,10,9,8};
BiTree T=NULL;
Status taller;
for(i=0;i<10;i++)
{
InsertAVL(&T,a[i],&taller);
}
printf("中序遍历二叉平衡树:\n");
InOrderTraverse(T);
printf("\n");
printf("删除结点元素5后中序遍历:\n");
int shorter;
deleteAVL(&T, 5, &shorter);
InOrderTraverse(T);
printf("\n");
return 0;
}
本文由作者按照 CC BY 4.0 进行授权