AVL树的性质
1. 左子树和右子树的高度之差的绝对值不超过1
2. 树中的每个左子树和右子树都是AVL树
3. 每个节点都有一个平衡因子(balance factor--bf),任一节点的平衡因子是-1,0,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
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
|
#pragma once
template
<
class
K,
class
V>
struct
AVLTreeNode
{
K _key;
V _value;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int
_bf;
//平衡因子
AVLTreeNode(
const
K& key,
const
V& value)
: _key(key)
, _value(value)
, _left(NULL)
, _right(NULL)
, _parent(NULL)
, _bf(0)
{}
};
template
<
class
K,
class
V>
class
AVLTree
{
typedef
AVLTreeNode<K, V> Node;
public
:
AVLTree()
: _root(NULL)
{}
~AVLTree()
{}
public
:
//空树
//查找位置
//插入节点
//更新平衡因子
//如果进行了旋转调整，则将parent进行重新连接
bool
Insert(
const
K& key,
const
V& value)
{
//空树
if
(_root == NULL)
{
_root =
new
Node(key, value);
return
true
;
}
//查找位置
Node* cur = _root;
Node* parent = NULL;
while
(cur)
{
if
(key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else
if
(key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else
{
return
false
;
}
}
//插入节点
cur =
new
Node(key, value);
if
(key > parent->_key)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
//更新平衡因子(右树-左树)
bool
isRotate =
false
;
//定义标志位，记录是否旋转
while
(parent)
{
if
(parent->_left == cur)
//插在parent的左边，平衡因子减1
{
parent->_bf--;
}
else
//插在parent的右边，平衡因子加1
{
parent->_bf++;
}
if
(parent->_bf == 0)
break
;
else
if
(parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = cur->_parent;
}
else
//旋转，调整平衡因子 2 -2
{
isRotate =
true
;
if
(parent->_bf == 2)
{
if
(cur->_bf == 1)
{
_RotateL(parent);
}
else
//cur->_bf == -1
{
_RotateRL(parent);
}
}
else
//parent->_bf == -2
{
if
(cur->_bf == -1)
{
_RotateR(parent);
}
else
{
_RotateLR(parent);
}
}
break
;
}
}
if
(isRotate)
//true则表示进行了调整
{
Node* GrandParent = parent->_parent;
if
(GrandParent == NULL)
{
_root = parent;
}
else
{
if
(parent->_key < GrandParent->_key)
{
GrandParent->_left = parent;
}
else
{
GrandParent->_right = parent;
}
}
}
return
true
;
}
void
InOrder()
{
_InOrder(_root);
cout << endl;
}
bool
IsBalanceTree()
{
return
_IsBalanceTree(_root);
}
protected
:
bool
_IsBalanceTree(Node* root)
{
if
(root == NULL)
{
return
true
;
}
int
left = _Height(root->_left);
int
right = _Height(root->_right);
int
bf =
abs
(right - left);
if
(bf > 1)
{
return
false
;
}
else
if
(bf !=
abs
(root->_bf))
{
cout << root->_bf <<
"平衡因子有误！"
<< endl;
return
false
;
}
return
_IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}
//左单旋
void
_RotateL(Node*& parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if
(subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
subR->_parent = parent->_parent;
parent->_parent = subR;
parent->_bf = subR->_bf = 0;
parent = subR;
}
void
_RotateR(Node*& parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if
(subLR)
{
subLR->_parent = parent;
}
subL->_right = parent;
subL->_parent = parent->_parent;
parent->_parent = subL;
parent->_bf = subL->_bf = 0;
parent = subL;
}
void
_RotateLR(Node*& parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
// 左单旋
subL->_right = subLR->_left;
if
(subLR->_left)
{
subLR->_left->_parent = subL;
}
subLR->_left = subL;
subLR->_parent = subL->_parent;
subL->_parent = subLR;
if
(subLR->_bf == 0 || subLR->_bf == -1)
{
subL->_bf = 0;
}
else
// subLR->_bf == 1
{
subL->_bf = -1;
}
// 右单旋
parent->_left = subLR->_right;
if
(subLR->_right)
{
subLR->_right->_parent = parent;
}
subLR->_right = parent;
subLR->_parent = parent->_parent;
parent->_parent = subLR;
if
(subLR->_bf == 0 || subLR->_bf == 1)
{
parent->_bf = 0;
}
else
// subLR->_bf == -1
{
parent->_bf = 1;
}
subLR->_bf = 0;
parent = subLR;
}
void
_RotateRL(Node*& parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
subR->_left = subRL->_right;
if
(subRL->_right)
{
subRL->_right->_parent = subR;
}
subRL->_right = subR;
subR->_parent = subRL;
if
(subRL->_bf == 0 || subRL->_bf == 1)
{
subR->_bf = 0;
}
else
{
subR->_bf = 1;
}
parent->_right = subRL->_left;
if
(subRL->_left)
{
subRL->_left->_parent = parent;
}
subRL->_left = parent;
subRL->_parent = parent->_parent;
parent->_parent = subRL;
if
(subRL->_bf == 0 || subRL->_bf == -1)
{
parent->_bf = 0;
}
else
{
parent->_bf = -1;
}
subRL->_bf = 0;
parent = subRL;
}
void
_InOrder(Node* root)
{
if
(root == NULL)
{
return
;
}
_InOrder(root->_left);
cout << root->_key <<
" "
;
_InOrder(root->_right);
}
int
_Height(Node* root)
{
if
(root == NULL)
{
return
0;
}
int
left = _Height(root->_left) + 1;
int
right = _Height(root->_right) + 1;
return
left > right ? left : right;
}
protected
:
Node* _root;
};
void
TestAVL1()
{
AVLTree<
int
,
int
> t;
int
a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
for
(
int
i = 0; i <
sizeof
(a) /
sizeof
(
int
); ++i)
{
t.Insert(a[i], i);
}
t.InOrder();
cout <<
"IsBlance?"
<< t.IsBalanceTree() << endl;
}
void
TestAVL2()
{
AVLTree<
int
,
int
> t;
int
a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for
(
int
i = 0; i <
sizeof
(a) /
sizeof
(
int
); ++i)
{
t.Insert(a[i], i);
t.InOrder();
}
cout <<
"IsBlance?"
<< t.IsBalanceTree() << endl;
}
|
本文转自 七十七快 51CTO博客，原文链接:http://blog.51cto.com/10324228/1771003
