平衡二叉树(AVL tree)调整算法请参见我的博文:
若要在 C++ 中使用则只要将 KYAVLTreeC.c 改为 KYAVLTreeC.cpp 即可。
用C语言实现平衡二叉树(AVL tree)头文件如下:
1 // =======================================
2 // Unit : AVL tree (KYAVLTreeC.h)
3 // Version: 2.1.0.0 (build 2011.03.04)
4 // Author : Kyee Ye
5 // Email : kyee_ye(at)126.com
6 // Copyright (C) Kyee workroom
7 // =======================================
8
9 #ifndef _KYAVLTreeC_H_
10 #define _KYAVLTreeC_H_
11
12 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
13
14 /* 类型定义 */
15
16 // 布尔类型 {0: False, 1: True}
17 #ifndef _KYBOOL_DEFINED_
18 typedef char Bool;
19 #define _KYBOOL_DEFINED_
20 #endif
21
22 // AVL 树结点类型
23 typedef struct
24 {
25 void* Item; // 项数据
26 void* Data; // 自定义数据
27 } TKYAVLNode, *PKYAVLNode;
28
29 // OnCompare 结点比较事件
30 // 若返回值 result == 0 则表示 ANode1 等于 ANode2
31 // 若返回值 result > 0 则表示 ANode1 大于 ANode2
32 // 若返回值 result < 0 则表示 ANode1 小于 ANode2
33 typedef long (*TKYAVL_OnCompare)(const TKYAVLNode* ANode1,
34 const TKYAVLNode* ANode2);
35
36 // OnDeletion 结点删除事件
37 typedef void (*TKYAVL_OnDeletion)(void* ATree, TKYAVLNode* ANode);
38
39 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
40
41 /* 公用函数, 注: 为了效率不检查 void* ATree 是否合法, 此参数需要外部来维护 */
42
43 // 创建/释放 AVL 树
44 void* KYAVLTree_Create(TKYAVL_OnCompare OnCompare,
45 TKYAVL_OnDeletion OnDeletion);
46 void KYAVLTree_Free(void* ATree);
47
48 // 读取 AVL 树属性
49 void* KYAVLTree_Data(void* ATree); // default: NULL
50 long KYAVLTree_Count(void* ATree); // default: 0
51 long KYAVLTree_MaxCount(void* ATree); // default: 0
52 Bool KYAVLTree_CanDuplicate(void* ATree); // default: False
53
54 // 设置 AVL 树属性
55 void KYAVLTree_SetData(void* ATree, void* AData);
56 void KYAVLTree_SetMaxCount(void* ATree, long AMaxCount);
57 void KYAVLTree_SetCanDuplicate(void* ATree, Bool ACanDuplicate);
58
59 // 清除 AVL 树的所有结点, 激发 OnDeletion 事件
60 void KYAVLTree_Clear(void* ATree);
61
62 // 添加 AVL 结点, 同时: {Node->Item == AItem, Node->Data == Data}
63 TKYAVLNode* KYAVLTree_Add(void* ATree, void* AItem, void* AData);
64
65 // 删除值为 AItem 和 Data 的 Compare(
) == 0 第一个 AVL 结点, 激发 OnDeletion 事件
66 Bool KYAVLTree_Delete(void* ATree, const void* AItem, const void* AData);
67
68 // 移除指定 AVL 结点, 激发 OnDeletion 事件
69 Bool KYAVLTree_Remove(void* ATree, TKYAVLNode* ANode);
70
71 // 搜索值为 AItem 和 Data 的 Compare() == 0 第一个 AVL 结点
72 TKYAVLNode* KYAVLTree_Find(void* ATree, const void* AItem, const void* AData);
73 Bool KYAVLTree_Search(void* ATree, void** ARetItem, void** ARetData,
74 const void* AItem, const void* AData);
75
76 // 查找最近一个 AVL 结点
77 // 若 ANearest == NULL 则表示项值大于树中的最后一个结点值;
78 // 若返回值为 true, 则表示找到项值的结点, 否则项值在 ANearest 结点之前
79 Bool KYAVLTree_FindNearest(void* ATree, const void* AItem,
80 const void* AData, PKYAVLNode* ANearest);
81
82 // 判断 AVL 结点是否存在
83 Bool KYAVLTree_Existed(void* ATree, TKYAVLNode* ANode);
84 //Bool KYAVLTree_Existed(void* ATree, const void* AItem, const void* AData)
85 // { return KYAVLTree_Find(ATree, AItem, AData) != NULL; }
86
87 // 取 AVL 树的结点
88 TKYAVLNode* KYAVLTree_Root(void* ATree); // 树的根结点, default: NULL
89 TKYAVLNode* KYAVLTree_Last(void* ATree); // 树的尾结点, default: NULL
90 TKYAVLNode* KYAVLTree_First(void* ATree); // 树的首结点, default: NULL
91
92 // 取 AVL 结点的属性
93 long KYAVLTree_Level(TKYAVLNode* ANode); // 结点所在的层号, Level(NULL) = -1
94 long KYAVLTree_Height(TKYAVLNode* ANode); // 结点的子树高度, Height(NULL) = 0
95 char KYAVLTree_Balance(TKYAVLNode* ANode); // 结点的子树平衡标志
96
97 // 取 AVL 结点的左右子结点及父结点
98 TKYAVLNode* KYAVLTree_Left(TKYAVLNode* ANode); // 左子结点, Left(NULL) = NULL
99 TKYAVLNode* KYAVLTree_Right(TKYAVLNode* ANode); // 右子结点, Right(NULL) = NULL
100 TKYAVLNode* KYAVLTree_Parent(TKYAVLNode* ANode); // 父结点, Parent(NULL) = NULL
101
102 // 取 AVL 结点的前后结点
103 TKYAVLNode* KYAVLTree_Prior(TKYAVLNode* ANode); // 前一结点, Prior(NULL) = NULL
104 TKYAVLNode* KYAVLTree_Next(TKYAVLNode* ANode); // 下一结点, Next(NULL) = NULL
105
106 #endif
107
用C语言实现平衡二叉树(AVL tree)源
1 // =======================================
2 // Unit : AVL tree (KYAVLTreeC.c)
3 // Version: 2.1.0.0 (build 2011.03.04)
4 // Author : Kyee Ye
5 // Email : kyee_ye(at)126.com
6 // Copyright (C) Kyee workroom
7 // =======================================
8
9 #include <malloc.h>
10 #include "KYAVLTreeC.h"
11
12 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
13
14 /* 类型定义 */
15
16 // 空值
17 #ifndef NULL
18 #define NULL 0
19 #endif
20
21 // 布尔假
22 #ifndef False
23 #define False 0
24 #endif
25
26 // 布尔真
27 #ifndef True
28 #define True 1
29 #endif
30
31 // AVL 树结点项类型
32 typedef struct _KYAVLItem
33 {
34 TKYAVLNode Node; // 结点
35 struct _KYAVLItem* Parent; // 父结点项
36 struct _KYAVLItem* Left; // 左子结点项
37 struct _KYAVLItem* Right; // 右子结点项
38 struct _KYAVLItem* Prior; // 前一结点项
39 struct _KYAVLItem* Next; // 下一结点项
40 char Balance; // 平衡标志: Height(Left) - Height(Right)
41 Bool Deleting; // 正在删除
42 } *PKYAVLItem;
43 typedef struct _KYAVLItem TKYAVLItem;
44
45 // AVL 树类型
46 typedef struct
47 {
48 void* Data; // 自定义数据
49 TKYAVLItem* Root; // 根结点
50 TKYAVLItem* Head; // 首结点
51 TKYAVLItem* Tail; // 尾结点
52 long Count; // 结点个数
53 long MaxCount; // 结点最大个数, 默认值为 0 表示无限制
54 Bool CanDuplicate; // 是否允许重复, 默认值为 False
55
56 // 事件
57 TKYAVL_OnCompare OnCompare;
58 TKYAVL_OnDeletion OnDeletion;
59 } TKYAVLTree, *PKYAVLTree;
60
61 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
62
63 /* 平衡调整函数 */
64
65 // 左右结点调整的平衡增量
66 static const char _Delta_Balance[2] = {1, -1};
67
68 // 调整结点并返回调整后的子树根结点(Left->Left)
69 static TKYAVLItem* L_AdjustLL(TKYAVLTree* ATree, TKYAVLItem* AParent,
70 TKYAVLItem* ATo, TKYAVLItem* ANode)
71 {
72 // 初始化
73 TKYAVLItem* pGrandparent= AParent->Parent;
74 TKYAVLItem* pRight = ATo->Right;
75
76 // 修改链接
77 ATo->Parent = pGrandparent;
78 ATo->Right = AParent;
79
80 AParent->Parent = ATo;
81 AParent->Left = pRight;
82
83 // 修改平衡值
84 AParent->Balance = _Delta_Balance[False] - ATo->Balance;
85 ATo->Balance -= _Delta_Balance[False];
86 //ANode->Balance = ANode->Balance;
87
88 // 修改子结点
89 if (pRight != NULL)
90 pRight->Parent = AParent;
91
92 // 修改根结点
93 if (pGrandparent == NULL)
94 ATree->Root = ATo;
95 else if (pGrandparent->Left == AParent)
96 pGrandparent->Left = ATo;
97 else
98 pGrandparent->Right = ATo;
99
100 // 返回结果
101 return ATo;
102 }
103
104 // 调整结点并返回调整后的子树根结点(Left->Right)
105 static TKYAVLItem* L_AdjustLR(TKYAVLTree* ATree, TKYAVLItem* AParent,
106 TKYAVLItem* ATo, TKYAVLItem* ANode)
107 {
108 // 初始化
109 TKYAVLItem* pGrandparent= AParent->Parent;
110 TKYAVLItem* pRight = ANode->Right;
111 TKYAVLItem* pLeft = ANode->Left;
112
113 // 修改链接
114 ANode->Parent = pGrandparent;
115 ANode->Left = ATo;
116 ANode->Right = AParent;
117
118 ATo->Parent = ANode;
119 ATo->Right = pLeft;
120
121 AParent->Parent = ANode;
122 AParent->Left = pRight;
123
124 // 修改平衡值
125 if (ANode->Balance == _Delta_Balance[False])
126 AParent->Balance = _Delta_Balance[True];
127 else
128 AParent->Balance = 0;
129
130 ATo->Balance += _Delta_Balance[False];
131 if (ANode->Balance == _Delta_Balance[True])
132 ATo->Balance += _Delta_Balance[False];
133
134 ANode->Balance += AParent->Balance + ATo->Balance;
135
136 // 修改左子结点
137 if (pLeft != NULL)
138 pLeft->Parent = ATo;
139
140 // 修改右子结点
141 if (pRight != NULL)
142 pRight->Parent = AParent;
143
144 // 修改根结点
145 if (pGrandparent == NULL)
146 ATree->Root = ANode;
147 else if (pGrandparent->Left == AParent)
148 pGrandparent->Left = ANode;
149 else
150 pGrandparent->Right = ANode;
151
152 // 返回结果
153 return ANode;
154 }
155
156 // 调整结点并返回调整后的子树根结点(Right->Left)
157 static TKYAVLItem* L_AdjustRL(TKYAVLTree* ATree, TKYAVLItem* AParent,
158 TKYAVLItem* ATo, TKYAVLItem* ANode)
159 {
160 // 初始化
161 TKYAVLItem* pGrandparent= AParent->Parent;
162 TKYAVLItem* pRight = ANode->Right;
163 TKYAVLItem* pLeft = ANode->Left;
164
165 // 修改链接
166 ANode->Parent = pGrandparent;
167 ANode->Left = AParent;
168 ANode->Right = ATo;
169
170 AParent->Parent = ANode;
171 AParent->Right = pLeft;
172
173 ATo->Parent = ANode;
174 ATo->Left = pRight;
175
176 // 修改平衡值
177 if (ANode->Balance == _Delta_Balance[True])
178 AParent->Balance = _Delta_Balance[False];
179 else
180 AParent->Balance = 0;
181
182 ATo->Balance += _Delta_Balance[True];
183 if (ANode->Balance == _Delta_Balance[False])
184 ATo->Balance += _Delta_Balance[True];
185
186 ANode->Balance += AParent->Balance + ATo->Balance;
187
188 // 修改左子结点
189 if (pLeft != NULL)
190 pLeft->Parent = AParent;
191
192 // 修改右子结点
193 if (pRight != NULL)
194 pRight->Parent = ATo;
195
196 // 修改根结点
197 if (pGrandparent == NULL)
198 ATree->Root = ANode;
199 else if (pGrandparent->Left == AParent)
200 pGrandparent->Left = ANode;
201 else
202 pGrandparent->Right = ANode;
203
204 // 返回结果
205 return ANode;
206 }
207
208 // 调整结点并返回调整后的子树根结点(Right->Right)
209 static TKYAVLItem* L_AdjustRR(TKYAVLTree* ATree, TKYAVLItem* AParent,
210 TKYAVLItem* ATo, TKYAVLItem* ANode)
211 {
212 // 初始化
213 TKYAVLItem* pGrandparent= AParent->Parent;
214 TKYAVLItem* pLeft = ATo->Left;
215
216 // 修改链接
217 ATo->Parent = pGrandparent;
218 ATo->Left = AParent;
219
220 AParent->Parent = ATo;
221 AParent->Right = pLeft;
222
223 // 修改平衡值
224 AParent->Balance = _Delta_Balance[True] - ATo->Balance;
225 ATo->Balance -= _Delta_Balance[True];
226 //ANode->Balance = ANode->Balance;
227
228 // 修改子结点
229 if (pLeft != NULL)
230 pLeft->Parent = AParent;
231
232 // 修改根结点
233 if (pGrandparent == NULL)
234 ATree->Root = ATo;
235 else if (pGrandparent->Left == AParent)
236 pGrandparent->Left = ATo;
237 else
238 pGrandparent->Right = ATo;
239
240 // 返回结果
241 return ATo;
242 }
243
244 // 调整结点的方法
245 typedef TKYAVLItem* (*TDoAdjust)(TKYAVLTree* ATree, TKYAVLItem* AParent,
246 TKYAVLItem* ATo, TKYAVLItem* ANode);
247
248 // 调整结点方法列表
249 static const TDoAdjust _DoAdjust[2][2] = {{L_AdjustLL, L_AdjustLR},
250 {L_AdjustRL, L_AdjustRR}};
251
252 // 调整结点并返回调整后的子树根结点
253 /*
254 (_DoAdjust[AIsRight1][AIsRight2])(ATree, AParent, ATo, ANode);
255 */
256
257 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
258
259 /* 静态函数 */
260
261 // OnCompare != NULL 时查找结点
262 // (若 ANearest 返回为 NULL, 则表示此结点大于所有结点值, 添加时要加入末尾)
263 static Bool L_DoFindNode(TKYAVLTree* ATree, const TKYAVLNode* ANode,
264 PKYAVLItem* ANearest)
265 {
266 // 初始化
267 long intCompare;
268 Bool result = False;
269 TKYAVLItem* pFound = NULL;
270 TKYAVLItem* pNode = ATree->Root;
271
272 // 循环查找
273 while (pNode != NULL)
274 {
275 // 比较大小
276 intCompare = ATree->OnCompare(ANode, (TKYAVLNode*)pNode);
277 pFound = pNode;
278
279 // 判断是否成功
280 if (intCompare == 0)
281 {
282 result = True;
283 break;
284 }
285 else if (intCompare < 0)
286 pNode = pNode->Left;
287 else
288 {
289 pFound = pNode->Next;
290 pNode = pNode->Right;
291 }
292 }
293
294 // 若允许重复则需要找到相等的第一项
295 if (result && ATree->CanDuplicate)
296 {
297 pNode = pFound->Left;
298 while (pNode != NULL)
299 if (ATree->OnCompare(ANode, (TKYAVLNode*)pNode) == 0)
300 {
301 pFound = pNode;
302 pNode = pNode->Left;
303 }
304 else if (pNode->Right != NULL)
305 pNode = pNode->Right;
306 else
307 break;
308 }
309
310 // 返回结果
311 *ANearest = pFound;
312 return result;
313 }
314
315 // 查找结点
316 // (若 ANearest 返回为 NULL, 则表示此结点大于所有结点值, 添加时要加入末尾)
317 static Bool L_FindNode(TKYAVLTree* ATree, const TKYAVLNode* ANode,
318 PKYAVLItem* ANearest)
319 {
320 // 初始化
321 Bool result = False;
322 TKYAVLItem* pFound = NULL;
323 TKYAVLItem* pNode = ATree->Root;
324
325 // 判断比较事件是否非空
326 if (ATree->OnCompare != NULL)
327 return L_DoFindNode(ATree, ANode, ANearest);
328
329 // 循环查找
330 while (pNode != NULL)
331 {
332 pFound = pNode;
333 if (ANode->Item == pNode->Node.Item)
334 {
335 result = True;
336 break;
337 }
338 else if ((long)ANode->Item < (long)pNode->Node.Item)
339 pNode = pNode->Left;
340 else
341 {
342 pFound = pNode->Next;
343 pNode = pNode->Right;
344 }
345 }
346
347 // 若允许重复则需要找到相等的第一项
348 if (result && ATree->CanDuplicate)
349 {
350 pNode = pFound->Left;
351 while (pNode != NULL)
352 if (ANode->Item == pNode->Node.Item)
353 {
354 pFound = pNode;
355 pNode = pNode->Left;
356 }
357 else if (pNode->Right != NULL)
358 pNode = pNode->Right;
359 else
360 break;
361 }
362
363 // 返回结果
364 *ANearest = pFound;
365 return result;
366 }
367
368 // 新增结点并修改上下链接
369 static TKYAVLItem* L_DoNewNode(TKYAVLTree* ATree, const TKYAVLNode* ANode,
370 PKYAVLItem* ATo, Bool* AIsAdd, Bool* AIsBreak)
371 {
372 // 分配项
373 TKYAVLItem* result= (TKYAVLItem*)malloc(sizeof(TKYAVLItem));
374
375 // 初始化项
376 result->Node = *ANode;
377 result->Parent = NULL;
378 result->Left = NULL;
379 result->Right = NULL;
380 result->Prior = NULL;
381 result->Next = NULL;
382 result->Balance = 0;
383 result->Deleting = False;
384 ATree->Count++;
385
386 // 初始化
387 *AIsAdd = False;
388 *AIsBreak = False;
389
390 // 修改链接
391 if (*ATo == NULL)
392 {
393 if (ATree->Tail == NULL)
394 {
395 ATree->Root = result;
396 ATree->Head = result;
397 ATree->Tail = result;
398 *AIsBreak = True;
399 }
400 else
401 {
402 *ATo = ATree->Tail;
403 *AIsAdd = True;
404 result->Prior = ATree->Tail;
405 ATree->Tail->Next = result;
406 ATree->Tail = result;
407 }
408 }
409 else if (((*ATo)->Left != NULL) && ((*ATo)->Right != NULL))
410 {
411 *AIsAdd = True;
412 *ATo = (*ATo)->Prior;
413 result->Prior = *ATo;
414 result->Next = (*ATo)->Next;
415 (*ATo)->Next->Prior = result;
416 (*ATo)->Next = result;
417 }
418 else
419 {
420 result->Prior = (*ATo)->Prior;
421 result->Next = (*ATo);
422
423 if ((*ATo)->Prior != NULL)
424 (*ATo)->Prior->Next = result;
425 else
426 ATree->Head = result;
427 (*ATo)->Prior = result;
428 }
429
430 // 返回结果
431 return result;
432 }
433
434 // 减平衡值(注: AParent != NULL)
435 static void L_DecBalance(TKYAVLTree* ATree, Bool AIsRight, TKYAVLItem* AParent)
436 {
437 // 初始化
438 Bool boolBreak, boolRight;
439 PKYAVLItem pTo, pNode;
440
441 // 循环调整平衡值
442 for (; ;)
443 {
444 // 修改父结点的平衡值
445 AParent->Balance -= _Delta_Balance[AIsRight];
446
447 // 判断是否中止调整
448 if (AParent->Balance == -_Delta_Balance[AIsRight])
449 break;
450 else if (AParent->Balance != 0) // 调整结点
451 {
452 // 取 To 结点
453 if (AIsRight)
454 {
455 pTo = AParent->Left;
456 boolRight = (pTo->Balance == _Delta_Balance[True]);
457 }
458 else
459 {
460 pTo = AParent->Right;
461 boolRight = (pTo->Balance != _Delta_Balance[False]);
462 }
463
464 // 取 Node 结点并调整结点
465 boolBreak = (pTo->Balance == 0);
466 pNode = (boolRight) ? pTo->Right : pTo->Left;
467 AParent = (_DoAdjust[!AIsRight][boolRight])(ATree, AParent, pTo, pNode);
468
469 // 判断是否中止调整
470 if (boolBreak)
471 break;
472 }
473
474 // 取祖父结点
475 pNode = AParent->Parent;
476 if (pNode == NULL)
477 break;
478
479 // 向上传递平衡值
480 AIsRight = (pNode->Right == AParent);
481 AParent = pNode;
482 }
483 }
484
485 // 增平衡值(注: AParent != NULL)
486 static void L_IncBalance(TKYAVLTree* ATree, Bool AIsRight, TKYAVLItem* AParent,
487 TKYAVLItem* ATo, TKYAVLItem* ANode)
488 {
489 // 初始化
490 Bool boolRight = False;
491
492 // 循环调整平衡值
493 do
494 {
495 // 修改父结点的平衡值
496 boolRight = (AParent->Right == ATo);
497 AParent->Balance += _Delta_Balance[boolRight];
498
499 // 判断是否向上调整
500 if (AParent->Balance == _Delta_Balance[boolRight])
501 {
502 ANode = ATo;
503 ATo = AParent;
504 AParent = AParent->Parent;
505 AIsRight = boolRight;
506 }
507 else if (AParent->Balance != 0) // 调整结点并中止向上调整
508 {
509 (_DoAdjust[boolRight][AIsRight])(ATree, AParent, ATo, ANode);
510 break;
511 }
512 else
513 break;
514 } while (AParent != NULL);
515 }
516
517 // 加入结点到 ATo 后面(注: ATo->Right 必定为 NULL)
518 static void L_DoAdd(TKYAVLTree* ATree, TKYAVLItem* ANode, TKYAVLItem* ATo)
519 {
520 // 初始化
521 TKYAVLItem* pParent = ATo->Parent;
522
523 // 加入右结点
524 ANode->Parent = ATo;
525 ATo->Right = ANode;
526 ATo->Balance += _Delta_Balance[True];
527
528 // 判断是否平衡
529 if ((ATo->Balance != 0) && (pParent != NULL))
530 L_IncBalance(ATree, True, pParent, ATo, ANode);
531 }
532
533 // 插入结点到 ATo 前面
534 static void L_DoInsert(TKYAVLTree* ATree, TKYAVLItem* ANode, TKYAVLItem* ATo)
535 {
536 // 初始化
537 TKYAVLItem* pLeft = ATo->Left;
538 TKYAVLItem* pParent = ATo->Parent;
539
540 // 加入左结点
541 ANode->Parent = ATo;
542 ATo->Left = ANode;
543 ATo->Balance += _Delta_Balance[False];
544
545 // 判断左子结点是否非空(若非空则ATo->Right必定为NULL)
546 if (pLeft != NULL)
547 {
548 pLeft->Parent = ANode;
549 ANode->Left = pLeft;
550 ANode->Balance += _Delta_Balance[False];
551
552 // 调整
553 L_AdjustLL(ATree, ATo, ANode, pLeft);
554 }
555 else if ((ATo->Balance != 0) && (pParent != NULL))
556 L_IncBalance(ATree, False, pParent, ATo, ANode);
557 }
558
559 //若 ATo == NULL 则追加到末尾, 否则插入 ATo 之前
560 // 注: FRoot, FHead, FTail, FCurr, FCount 会产生变化
561 static TKYAVLItem* L_InsertNode(TKYAVLTree* ATree, const TKYAVLNode* ANode, TKYAVLItem* ATo)
562 {
563 // 初始化
564 Bool boolAdd, boolBreak;
565 TKYAVLItem* result = L_DoNewNode(ATree, ANode, &ATo, &boolAdd, &boolBreak);
566
567 // 操作
568 if (boolBreak)
569 ;
570 else if (boolAdd)
571 L_DoAdd(ATree, result, ATo);
572 else
573 L_DoInsert(ATree, result, ATo);
574
575 // 返回结果
576 return result;
577 }
578
579 // 从树中删除结点, 并重新平衡树, 但不释放结点项
580 // 注: FRoot, FHead, FTail, FCurr, FCount 会产生变化
581 static void L_DeleteNode(TKYAVLTree* ATree, TKYAVLItem* ANode)
582 {
583 // 初始化
584 Bool boolRight;
585 TKYAVLItem* pParent = ANode->Parent;
586 TKYAVLItem* pPrior = ANode->Prior;
587 TKYAVLItem* pRight = ANode->Right;
588 TKYAVLItem* pLeft = ANode->Left;
589
590 // 置删除标志
591 ATree->Count--;
592 ANode->Deleting = True;
593
594 // 修改前一个链接
595 if (pPrior == NULL)
596 ATree->Head = ANode->Next;
597 else
598 pPrior->Next = ANode->Next;
599
600 // 修改下一个链接
601 if (ANode->Next == NULL)
602 ATree->Tail = pPrior;
603 else
604 ANode->Next->Prior = pPrior;
605
606 // 判断左子结点是否为空
607 if (pLeft == NULL)
608 {
609 // 修改右子结点的连接
610 if (pRight != NULL)
611 pRight->Parent = pParent;
612
613 // 判断父结点是否为空
614 if (pParent == NULL)
615 ATree->Root = pRight;
616 else
617 {
618 // 修改父结点的连接
619 boolRight = (pParent->Right == ANode);
620 if (boolRight)
621 pParent->Right = pRight;
622 else
623 pParent->Left = pRight;
624
625 // 减平衡值
626 L_DecBalance(ATree, boolRight, pParent);
627 }
628 }
629 else if (pRight == NULL) // 判断右子结点是否为空
630 {
631 // 修改左子结点的连接
632 pLeft->Parent = pParent;
633
634 // 判断父结点是否为空
635 if (pParent == NULL)
636 ATree->Root = pLeft;
637 else
638 {
639 // 修改父结点的连接
640 boolRight = (pParent->Right == ANode);
641 if (boolRight)
642 pParent->Right = pLeft;
643 else
644 pParent->Left = pLeft;
645
646 // 减平衡值
647 L_DecBalance(ATree, boolRight, pParent);
648 }
649 }
650 else if (pPrior == pLeft) // 判断左子结点是否为前一结点
651 {
652 // 判断父结点是否为空
653 if (pParent == NULL)
654 ATree->Root = pLeft;
655 else if (pParent->Right == ANode)
656 pParent->Right = pLeft;
657 else
658 pParent->Left = pLeft;
659
660 // 修改左右子结点的连接
661 pRight->Parent = pLeft;
662 pLeft->Parent = pParent;
663 pLeft->Right = pRight;
664 pLeft->Balance = ANode->Balance;
665
666 // 减平衡值
667 L_DecBalance(ATree, False, pLeft);
668 }
669 else
670 {
671 // 判断父结点是否为空
672 if (pParent == NULL)
673 ATree->Root = pPrior;
674 else if (pParent->Right == ANode)
675 pParent->Right = pPrior;
676 else
677 pParent->Left = pPrior;
678
679 // 修改左右子结点的连接
680 pLeft->Parent = pPrior;
681 pRight->Parent = pPrior;
682
683 // 取前一结点的父结点和左子结点(pPrior->Right 必定为 NULL)
684 pParent = pPrior->Parent;
685 pLeft = pPrior->Left;
686
687 // 使用前一结点替换当前结点
688 pPrior->Parent = ANode->Parent;
689 pPrior->Left = ANode->Left;
690 pPrior->Right = ANode->Right;
691 pPrior->Balance = ANode->Balance;
692
693 // 修改前一结点的左子结点的连接
694 if (pLeft != NULL)
695 pLeft->Parent = pParent;
696
697 // 修改前一结点的父结点的连接(pParent->Right 必定为 pPrior)
698 pParent->Right = pLeft;
699
700 // 减平衡值
701 L_DecBalance(ATree, True, pParent);
702 }
703 }
704
705 // 清除所有结点
706 static void L_ClearNodes(TKYAVLTree* ATree, TKYAVLItem* AHead)
707 {
708 // 初始化
709 TKYAVLItem* pNode;
710
711 // 判断 OnDeletion 事件是否非空
712 if (ATree->OnDeletion != NULL)
713 while (AHead != NULL)
714 {
715 pNode = AHead;
716 AHead = AHead->Next;
717
718 // 激发 OnDeletion 事件
719 ATree->OnDeletion(ATree, (TKYAVLNode*)pNode);
720
721 // 删除结点项
722 free(pNode);
723 }
724 else
725 while (AHead != NULL)
726 {
727 pNode = AHead;
728 AHead = AHead->Next;
729
730 // 删除结点项
731 free(pNode);
732 }
733 }
734
735 // 设置所有结点删除标志
736 static void L_SetAllDeleting(TKYAVLItem* AHead)
737 {
738 while (AHead != NULL)
739 {
740 AHead->Deleting = True;
741 AHead = AHead->Next;
742 }
743 }
744
745 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
746
747 /* 公用函数, 注: 为了效率不检查 void* ATree 是否合法, 此参数需要外部来维护 */
748
749 // 创建 AVL 树
750 void* KYAVLTree_Create(TKYAVL_OnCompare OnCompare, TKYAVL_OnDeletion OnDeletion)
751 {
752 // 初始化
753 TKYAVLTree* result = (TKYAVLTree*)malloc(sizeof(TKYAVLTree));
754
755 // 赋值
756 result->Data = NULL;
757 result->Root = NULL;
758 result->Head = NULL;
759 result->Tail = NULL;
760 result->Count = 0;
761 result->MaxCount = 0;
762 result->CanDuplicate = False;
763
764 // 设置事件
765 result->OnCompare = OnCompare;
766 result->OnDeletion = OnDeletion;
767
768 // 返回结果
769 return result;
770 }
771
772 // 释放 AVL 树
773 void KYAVLTree_Free(void* ATree)
774 {
775 // 清除
776 KYAVLTree_Clear(ATree);
777
778 // 释放
779 free(ATree);
780 }
781
782 // default: NULL
783 void* KYAVLTree_Data(void* ATree)
784 {
785 return ((TKYAVLTree*)ATree)->Data;
786 }
787
788 // 取 AVL 树的结点个数, default: 0
789 long KYAVLTree_Count(void* ATree)
790 {
791 return ((TKYAVLTree*)ATree)->Count;
792 }
793
794 // 取 AVL 树的结点最大个数, default: 0
795 long KYAVLTree_MaxCount(void* ATree)
796 {
797 return ((TKYAVLTree*)ATree)->MaxCount;
798 }
799
800 // 取 AVL 树的是否允许相同结点值项, default: False
801 Bool KYAVLTree_CanDuplicate(void* ATree)
802 {
803 return ((TKYAVLTree*)ATree)->CanDuplicate;
804 }
805
806 // AVL 树设置属性
807 void KYAVLTree_SetData(void* ATree, void* AData)
808 {
809 ((TKYAVLTree*)ATree)->Data = AData;
810 }
811
812 // 设置 AVL 树的结点最大个数, 0 表示无限制个数
813 void KYAVLTree_SetMaxCount(void* ATree, long AMaxCount)
814 {
815 if (AMaxCount <= 0)
816 ((TKYAVLTree*)ATree)->MaxCount = 0;
817 else if (AMaxCount <= ((TKYAVLTree*)ATree)->Count)
818 ((TKYAVLTree*)ATree)->MaxCount = ((TKYAVLTree*)ATree)->Count;
819 else
820 ((TKYAVLTree*)ATree)->MaxCount = AMaxCount;
821 }
822
823 // 设置 AVL 树的允许相同结点值项
824 void KYAVLTree_SetCanDuplicate(void* ATree, Bool ACanDuplicate)
825 {
826 ((TKYAVLTree*)ATree)->CanDuplicate = (ACanDuplicate != 0);
827 }
828
829 // 清除 AVL 树的所有结点, 激发 OnDeletion 事件
830 void KYAVLTree_Clear(void* ATree)
831 {
832 // 初始化
833 TKYAVLTree* pTree = (TKYAVLTree*)ATree;
834 TKYAVLItem* pHead = pTree->Head; //(TKYAVLItem*)InterlockedExchange((long*)&pTree->Head, 0);
835
836 // 清空
837 pTree->Head = NULL;
838 pTree->Root = NULL;
839 pTree->Tail = NULL;
840 pTree->Count = 0;
841
842 // 设置删除标志
843 if (pHead != NULL)
844 L_SetAllDeleting(pHead);
845
846 // 清除树
847 if (pHead != NULL)
848 L_ClearNodes(pTree, pHead);
849 }
850
851 // 添加 AVL 结点, 同时: {Node->Item == AItem, Node->Data == Data}
852 TKYAVLNode* KYAVLTree_Add(void* ATree, void* AItem, void* AData)
853 {
854 // 初始化
855 TKYAVLNode* result = NULL;
856 TKYAVLTree* pTree = (TKYAVLTree*)ATree;
857
858 // 检查个数
859 if ((pTree->MaxCount == 0) || (pTree->Count < pTree->MaxCount))
860 {
861 // 初始化
862 TKYAVLNode recNode;
863 TKYAVLItem* pNearest;
864
865 // 查找结点
866 recNode.Item = AItem;
867 recNode.Data = AData;
868 if (!L_FindNode(pTree, &recNode, &pNearest) || pTree->CanDuplicate)
869 result = (TKYAVLNode*)L_InsertNode(pTree, &recNode, pNearest);
870 }
871
872 // 返回结果
873 return result;
874 }
875
876 // 删除值为 AItem 和 Data 的 Compare() == 0 第一个 AVL 结点, 激发 OnDeletion 事件
877 Bool KYAVLTree_Delete(void* ATree, const void* AItem, const void* AData)
878 {
879 // 初始化
880 Bool result = False;
881 TKYAVLTree* pTree = (TKYAVLTree*)ATree;
882 TKYAVLItem* pFound;
883 TKYAVLNode recNode;
884
885 // 查找结点
886 recNode.Item = (void*)AItem;
887 recNode.Data = (void*)AData;
888 if (L_FindNode(pTree, &recNode, &pFound))
889 {
890 // 删除结点
891 L_DeleteNode(pTree, pFound);
892 result = True;
893
894 // 激发 OnDeletion 事件
895 if (pTree->OnDeletion != NULL)
896 pTree->OnDeletion(ATree, (TKYAVLNode*)pFound);
897
898 // 释放
899 free(pFound);
900 }
901
902 // 返回结果
903 return result;
904 }
905
906 // 移除指定 AVL 结点, 激发 OnDeletion 事件
907 Bool KYAVLTree_Remove(void* ATree, TKYAVLNode* ANode)
908 {
909 // 初始化
910 Bool result = False;
911
912 // 判断结点是否存在
913 if (KYAVLTree_Existed(ATree, ANode))
914 {
915 // 初始化
916 TKYAVLTree* pTree = (TKYAVLTree*)ATree;
917
918 // 删除结点
919 L_DeleteNode(pTree, (TKYAVLItem*)ANode);
920 result = True;
921
922 // 激发 OnDeletion 事件
923 if (pTree->OnDeletion != NULL)
924 pTree->OnDeletion(ATree, ANode);
925
926 // 释放
927 free(ANode);
928 }
929
930 // 返回结果
931 return result;
932 }
933
934 // 搜索值为 AItem 和 Data 的 Compare() == 0 第一个 AVL 结点
935 TKYAVLNode* KYAVLTree_Find(void* ATree, const void* AItem, const void* AData)
936 {
937 // 初始化
938 TKYAVLNode* result = NULL;
939 TKYAVLItem* pFound;
940 TKYAVLNode recNode;
941
942 // 查找
943 recNode.Item = (void*)AItem;
944 recNode.Data = (void*)AData;
945 if (L_FindNode((TKYAVLTree*)ATree, &recNode, &pFound))
946 result = (TKYAVLNode*)pFound;
947
948 // 返回结果
949 return result;
950 }
951
952 Bool KYAVLTree_Search(void* ATree, void** ARetItem, void** ARetData,
953 const void* AItem, const void* AData)
954 {
955 // 初始化
956 Bool result = False;
957 TKYAVLItem* pFound;
958 TKYAVLNode recNode;
959
960 // 查找
961 recNode.Item = (void*)AItem;
962 recNode.Data = (void*)AData;
963 if (L_FindNode((TKYAVLTree*)ATree, &recNode, &pFound))
964 {
965 result = True;
966 *ARetItem = pFound->Node.Item;
967 *ARetData = pFound->Node.Data;
968 }
969
970 // 返回结果
971 return result;
972 }
973
974 // 查找最近一个 AVL 结点
975 // 若 ANearest == NULL 则表示项值大于树中的最后一个结点值
976 // 若返回值为 True, 则表示找到项值的结点, 否则项值在 ANearest 结点之前
977 Bool KYAVLTree_FindNearest(void* ATree, const void* AItem,
978 const void* AData, PKYAVLNode* ANearest)
979 {
980 // 初始化
981 TKYAVLNode recNode;
982
983 // 赋值
984 recNode.Item = (void*)AItem;
985 recNode.Data = (void*)AData;
986
987 // 查找
988 return L_FindNode((TKYAVLTree*)ATree, &recNode, (PKYAVLItem*)ANearest);
989 }
990
991 // 判断 AVL 结点是否存在
992 Bool KYAVLTree_Existed(void* ATree, TKYAVLNode* ANode)
993 {
994 // 初始化
995 Bool result = False;
996 TKYAVLTree* pTree = (TKYAVLTree*)ATree;
997 TKYAVLItem* pNode = (TKYAVLItem*)ANode;
998
999 // 判断是否未删除
1000 if ((pTree->Root != NULL) && (pNode != NULL) && !pNode->Deleting)
1001 {
1002 // 取根结点
1003 while (pNode->Parent != NULL)
1004 pNode = pNode->Parent;
1005
1006 // 判断根是否相同
1007 result = (pNode == pTree->Root);
1008 }
1009
1010 // 返回结果
1011 return result;
1012 }
1013
1014 // 取 AVL 树的根结点, default: NULL
1015 TKYAVLNode* KYAVLTree_Root(void* ATree)
1016 {
1017 return (TKYAVLNode*)((TKYAVLTree*)ATree)->Root;
1018 }
1019
1020 // 取 AVL 树的尾结点, default: NULL
1021 TKYAVLNode* KYAVLTree_Last(void* ATree)
1022 {
1023 return (TKYAVLNode*)((TKYAVLTree*)ATree)->Tail;
1024 }
1025
1026 // 取 AVL 树的首结点, default: NULL
1027 TKYAVLNode* KYAVLTree_First(void* ATree)
1028 {
1029 return (TKYAVLNode*)((TKYAVLTree*)ATree)->Head;
1030 }
1031
1032 // 取 AVL 结点所在的层号, Level(NULL) = -1
1033 long KYAVLTree_Level(TKYAVLNode* ANode)
1034 {
1035 // 初始化
1036 long result = -1;
1037 TKYAVLItem* pNode = (TKYAVLItem*)ANode;
1038
1039 // 循环计算
1040 while (pNode != NULL)
1041 {
1042 result++;
1043 pNode = pNode->Parent;
1044 }
1045
1046 // 返回结果
1047 return result;
1048 }
1049
1050 // 取 AVL 结点的子树高度, Height(NULL) = 0
1051 long KYAVLTree_Height(TKYAVLNode* ANode)
1052 {
1053 // 初始化
1054 long result = 0;
1055 TKYAVLItem* pNode = (TKYAVLItem*)ANode;
1056
1057 // 循环计算
1058 while (pNode != NULL)
1059 {
1060 result++;
1061
1062 // 判断子树高度
1063 if (pNode->Balance == _Delta_Balance[True])
1064 pNode = pNode->Right;
1065 else
1066 pNode = pNode->Left;
1067 }
1068
1069 // 返回结果
1070 return result;
1071 }
1072
1073 // 取 AVL 结点的子树平衡标志
1074 char KYAVLTree_Balance(TKYAVLNode* ANode)
1075 {
1076 if (ANode != NULL)
1077 return ((TKYAVLItem*)ANode)->Balance;
1078 else
1079 return 0;
1080 }
1081
1082 // 取 AVL 结点的左子结点
1083 TKYAVLNode* KYAVLTree_Left(TKYAVLNode* ANode)
1084 {
1085 if (ANode != NULL)
1086 return (TKYAVLNode*)((TKYAVLItem*)ANode)->Left;
1087 else
1088 return NULL;
1089 }
1090
1091 // 取 AVL 结点的右子结点
1092 TKYAVLNode* KYAVLTree_Right(TKYAVLNode* ANode)
1093 {
1094 if (ANode != NULL)
1095 return (TKYAVLNode*)((TKYAVLItem*)ANode)->Right;
1096 else
1097 return NULL;
1098 }
1099
1100 // 取 AVL 结点的父结点
1101 TKYAVLNode* KYAVLTree_Parent(TKYAVLNode* ANode)
1102 {
1103 if (ANode != NULL)
1104 return (TKYAVLNode*)((TKYAVLItem*)ANode)->Parent;
1105 else
1106 return NULL;
1107 }
1108
1109 // 取 AVL 结点的前一结点
1110 TKYAVLNode* KYAVLTree_Prior(TKYAVLNode* ANode)
1111 {
1112 if (ANode != NULL)
1113 return (TKYAVLNode*)((TKYAVLItem*)ANode)->Prior;
1114 else
1115 return NULL;
1116 }
1117
1118 // 取 AVL 结点的下一结点
1119 TKYAVLNode* KYAVLTree_Next(TKYAVLNode* ANode)
1120 {
1121 if (ANode != NULL)
1122 return (TKYAVLNode*)((TKYAVLItem*)ANode)->Next;
1123 else
1124 return NULL;
1125 }
1126
码如下:
posted on 2011-05-22 12:34
Kyee Ye 阅读(2306)
评论(0) 编辑 收藏 引用 所属分类:
源码