數(shù)據(jù)結(jié)構(gòu) 紅黑樹(shù)的詳解
紅黑樹(shù)是具有下列著色性質(zhì)的二叉查找樹(shù)：
1.每一個(gè)節(jié)點(diǎn)或者著紅色，或者著黑色。
2.根是黑色的。
3.如果一個(gè)節(jié)點(diǎn)是紅色的，那么它的子節(jié)點(diǎn)必須是黑色。
4.從一個(gè)節(jié)點(diǎn)到一個(gè)NULL指針的每一條路徑必須包含相同數(shù)目的黑色節(jié)點(diǎn)。
下面是一棵紅黑樹(shù)。
1.自底向上插入
通常把新項(xiàng)作為樹(shù)葉放到樹(shù)中。如果我們把該項(xiàng)涂成黑色，那么違反條件4，因?yàn)閷?huì)建立一條更長(zhǎng)的黑節(jié)點(diǎn)路徑。因此這一項(xiàng)必須涂成紅色。如果它的父節(jié)點(diǎn)是黑色的，插入完成。如果父節(jié)點(diǎn)是紅色的，那么違反條件3。在這種情況下我們必須調(diào)整該樹(shù)以滿足條件3。用于完成這項(xiàng)目任務(wù)的基本操作是顏色的改變和樹(shù)的旋轉(zhuǎn)。
如果新插入的節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色，那么插入完成。
如果父節(jié)點(diǎn)是紅色，那么有幾種情形需要考慮。首先，假設(shè)這個(gè)父節(jié)點(diǎn)的兄弟是黑色（NULL節(jié)點(diǎn)約定為黑色）。這對(duì)于插入3或8是適用的，但對(duì)插入99不適用。令X是新加的樹(shù)葉，P是它的父節(jié)點(diǎn)，S是該父節(jié)點(diǎn)的兄弟，G是祖父節(jié)點(diǎn)情況一：父節(jié)點(diǎn)的兄弟是黑色的。通過(guò)操作使得到達(dá)A,B,C的黑色路徑保持不變（滿足條件4），而且沒(méi)有連續(xù)的紅色節(jié)點(diǎn)（滿足條件3）.。
情況二：父節(jié)點(diǎn)的兄弟是紅色的。
2.自頂向下刪除
紅黑樹(shù)中的刪除可以是自頂向下進(jìn)行。每一件工作都?xì)w結(jié)于能夠刪除一片樹(shù)葉。這是因?yàn)椋獎(jiǎng)h除一個(gè)帶有兩個(gè)兒子的節(jié)點(diǎn)，我們用右子樹(shù)上的最小節(jié)點(diǎn)代替它；該節(jié)點(diǎn)最多有一個(gè)兒子，然后將該節(jié)點(diǎn)刪除。只有一個(gè)右兒子的節(jié)點(diǎn)可以用相同的方式刪除，而只有一個(gè)左兒子的節(jié)點(diǎn)通過(guò)用其左子樹(shù)上最大的節(jié)點(diǎn)替換，然后可將該節(jié)點(diǎn)刪除。但是假如刪除的節(jié)點(diǎn)不是紅色的，那么就會(huì)破壞紅黑樹(shù)的平衡。解決的方法就是保證從上到下刪除期間樹(shù)葉是紅色的。
在整個(gè)討論中，令X為當(dāng)前節(jié)點(diǎn)，T是它的兄弟，而P是它們的父親。開(kāi)始時(shí)我們把根涂成紅色。當(dāng)沿著樹(shù)向下遍歷時(shí)，我們?cè)O(shè)法保證X是紅色的。當(dāng)我們到達(dá)一個(gè)新的節(jié)點(diǎn)時(shí)，我們要確信P是紅色的并且X和T是黑色的（因?yàn)椴荒苡袃蓚€(gè)相連的紅色節(jié)點(diǎn)）。存在兩種主要情形。
情況一：X有兩個(gè)黑色兒子。此時(shí)有三個(gè)子情況。
（1）T有兩個(gè)黑兒子，那么我們可以翻轉(zhuǎn)X、T、P的顏色來(lái)保持這種不變性。
（2）T的左兒子是紅色的
（3）T的右兒子是紅色的
情況二：X的兒子之一是紅的。在這種情況下，我們落到下一層，得到新的X、T、P。如果幸運(yùn)，X落在紅兒子上。則我們繼續(xù)前行。如果不是這樣，那么我們知道T將是紅的，而X和P將是黑的。我們可以旋轉(zhuǎn)T和P，使得X的新父親是紅的；當(dāng)然X和它的祖父是黑的。此時(shí)我們可以回到第一種主情況。
3.紅黑樹(shù)的實(shí)現(xiàn)
3.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
|
// // RedBlackTree.h // RedBlackTree3 // // Created by Wuyixin on 2017/7/3. // Copyright © 2017年 Coding365. All rights reserved. // #ifndef RedBlackTree_h #define RedBlackTree_h #include <stdio.h> #include <stdlib.h> #include <limits.h> typedef int ElementType; typedef enum { RED, BLACK } COLOR; typedef struct RedBlackNode *RedBlackTree,*Position; struct RedBlackNode{ ElementType Element; COLOR Color; RedBlackTree Left; RedBlackTree Right; }; static Position NullNode = NULL; static Position Header; static Position X,P,GP,GGP; /* 初始化 */ RedBlackTree Initialize(); /* 插入 */ RedBlackTree Insert(RedBlackTree T,ElementType Item); /* 刪除 */ RedBlackTree Remove(RedBlackTree T,ElementType Item); /* 查找 */ Position Find(RedBlackTree T,ElementType Item); /* 遍歷 */ void Travel(RedBlackTree T); #endif /* RedBlackTree_h */ |
3.2 實(shí)現(xiàn)文件
|
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
|
// // RedBlackTree.c // RedBlackTree3 // // Created by Wuyixin on 2017/7/3. // Copyright © 2017年 Coding365. All rights reserved. // #include "RedBlackTree.h" /* 左旋轉(zhuǎn) */static Position SingleRotateLeft(Position X); /* 右旋轉(zhuǎn) */static Position SingleRotateRight(Position X); /* 旋轉(zhuǎn) */static Position Rotate(Position Parent,Position* Origin ,ElementType Item); /* 左旋轉(zhuǎn) */static Position SingleRotateLeft(Position T){ Position TL = T->Left; T->Left = TL->Right; TL->Right = T; return TL; } /* 右旋轉(zhuǎn) */static Position SingleRotateRight(Position T){ Position TR = T->Right; T->Right = TR->Left; TR->Left = T; return TR; } /* 旋轉(zhuǎn) */static Position Rotate(Position Parent,Position* Origin ,ElementType Item){ if (Item < Parent->Element){ if (Origin != NULL) *Origin = Parent->Left; return Parent->Left = Item < Parent->Left->Element ? SingleRotateLeft(Parent->Left) : SingleRotateRight(Parent->Left); } else{ if (Origin != NULL) *Origin = Parent->Right; return Parent->Right = Item < Parent->Right->Element ? SingleRotateLeft(Parent->Right) : SingleRotateRight(Parent->Right); } } /* 初始化 */RedBlackTree Initialize(){ if (NullNode == NULL){ NullNode = malloc(sizeof(struct RedBlackNode)); if (NullNode == NULL) exit(EXIT_FAILURE); NullNode->Element = INT_MAX; NullNode->Color = BLACK; NullNode->Left = NullNode->Right = NullNode; } Header = malloc(sizeof(struct RedBlackNode)); if (Header == NULL) exit(EXIT_FAILURE); /* header的值為無(wú)窮小，所以根插入到右邊*/ Header->Element = INT_MIN; Header->Left = Header->Right = NullNode; Header->Color = BLACK; return Header; } static Position GetSibling(Position Parent,Position X){ if (Parent->Element == INT_MIN) return NULL; if (X == Parent->Left) return Parent->Right; else if (X == Parent->Right) return Parent->Left; else return NULL; } void HandleReorientForInsert(ElementType Item){ Position Sibling,Origin; /* 當(dāng)P與X同時(shí)為紅節(jié)點(diǎn)才進(jìn)行調(diào)整 */ if (X == NullNode || !(P->Color == RED && X->Color == RED)) return ; Sibling = GetSibling(GP, P); if (Sibling == NULL) return ; /* GP,P,X是成字型，調(diào)整為一字型 */ if ((GP->Element < Item) != (P->Element < Item)){ P = Rotate(GP, &Origin,Item); X = Origin; } GP = Rotate(GGP, &Origin,Item); P = Origin; /* P的兄弟是黑色的 */ if (Sibling->Color == BLACK){ GP->Color = BLACK; GP->Left->Color = RED; GP->Right->Color = RED; } /* P的兄弟是紅的 */ else{ GP->Color = RED; GP->Left->Color = BLACK; GP->Right->Color = BLACK; } } RedBlackTree _Insert(RedBlackTree T,ElementType Item){ if (T == NullNode){ T = malloc(sizeof(struct RedBlackNode)); T->Element = Item; T->Left = T->Right = NullNode; T->Color = RED; } else if (Item < T->Element) T->Left = _Insert(T->Left, Item); else if (Item > T->Element) T->Right = _Insert(T->Right, Item); /* 重復(fù)值不插入 */ X = P,P = GP,GP = GGP, GGP = T; HandleReorientForInsert(Item); return T; } /* 插入 */RedBlackTree Insert(RedBlackTree T,ElementType Item){ GGP = GP = P = X = NullNode; T = _Insert(T, Item); T->Right->Color = BLACK; return T; } static void _HandleReorientForRemove(ElementType Item){ RedBlackTree Sibling,R; Sibling = GetSibling(P, X); if (Sibling == NULL) return ; if (Sibling->Left->Color == BLACK && Sibling->Right->Color == BLACK){ P->Color = BLACK; X->Color = RED; Sibling->Color = RED; }else if(Sibling->Left->Color == RED){ R = Sibling->Left; P->Color = BLACK; X->Color = RED; R = Rotate(P, NULL, R->Element); GP = Rotate(GP, NULL, R->Element); }else if (Sibling->Right->Color == RED){ X->Color = RED; P->Color = BLACK; Sibling->Color = RED; Sibling->Right->Color = BLACK; GP = Rotate(GP, NULL, Sibling->Element); } } static void HandleReorientForRemove(RedBlackTree T, ElementType Item){ RedBlackTree Sibling,Origin,OriginGP; if (X == NullNode) return ; /* X有兩個(gè)黑兒子 */ if (X->Left->Color == BLACK && X->Right->Color == BLACK){ _HandleReorientForRemove(Item); }else{ OriginGP = GP; /* 落到下一層 */ GP = P; P = X; if (Item < X->Element) X = X->Left; else X = X->Right; Sibling = GetSibling(P, X); /* 如果X是黑的，則Sibling是紅的，旋轉(zhuǎn) */ if (X->Color == BLACK){ GP = Rotate(GP, &Origin, Sibling->Element); P = Origin; GP->Color = BLACK; P->Color = RED; _HandleReorientForRemove(Item); } /* 恢復(fù)X,PX,GP。由于X是當(dāng)前節(jié)點(diǎn) 如果當(dāng)前節(jié)點(diǎn)正是Item，不恢復(fù)會(huì)影響查找 */ if (X->Element == Item){ X = P ; P = GP ;GP = OriginGP; } } } /* 刪除 */RedBlackTree Remove(RedBlackTree T,ElementType Item){ ElementType Origin; Position DeletePtr; Origin = NullNode->Element; NullNode->Element = Item; GP = P = X = T; /* 根染紅 */ T->Right->Color = RED; while (X->Element != Item) { GP = P ; P = X; if (Item < X->Element) X = X->Left; else X = X->Right; HandleReorientForRemove(T, Item); } NullNode->Element = Origin; /* 找到 */ if (X != NullNode){ DeletePtr = X; if (X->Left != NullNode){ GP = P ; P = X; X = X->Left; HandleReorientForRemove(T, Item); /* 尋找左子樹(shù)最大值替換 */ while (X->Right != NullNode) { GP = P ; P = X; X = X->Right; HandleReorientForRemove(T, Item); } if (X == P->Left) P->Left = X->Left; else P->Right = X->Left; }else if (X->Right != NullNode){ GP = P ; P = X; X = X->Right; HandleReorientForRemove(T, Item); /* 尋找右子樹(shù)最大值替換 */ while (X->Left != NullNode) { GP = P ; P = X; X = X->Left; HandleReorientForRemove(T, Item); } if (X == P->Left) P->Left = X->Right; else P->Right = X->Right; }else{ /* X是樹(shù)葉 */ if (X == P->Left) P->Left = NullNode; else P->Right = NullNode; } DeletePtr->Element = X->Element; free(X); } /* 根染黑 */ T->Right->Color = BLACK; return T; } typedef enum { ROOT, LEFT, RIGHT } NodeType; static char *TypeC; static char *ColorC; void _Travel(RedBlackTree T , NodeType Type){ if (T != NullNode){ if (Type == ROOT) TypeC = "root"; else if (Type == LEFT) TypeC = "left"; else if (Type == RIGHT) TypeC = "right"; if (T->Color == BLACK) ColorC = "black"; else ColorC = "red"; printf("(%d,%s,%s) ",T->Element,ColorC,TypeC); _Travel(T->Left, LEFT); _Travel(T->Right, RIGHT); } } /* 遍歷 */void Travel(RedBlackTree T){ _Travel(T->Right,ROOT); } |
3.3 調(diào)用
|
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
|
// // main.c // RedBlackTree3 // // Created by Wuyixin on 2017/7/3. // Copyright © 2017年 Coding365. All rights reserved. // #include "RedBlackTree.h" int main(int argc, const char * argv[]) { RedBlackTree T = Initialize(); T = Insert(T, 10); T = Insert(T, 85); T = Insert(T, 15); T = Insert(T, 70); T = Insert(T, 20); T = Insert(T, 60); T = Insert(T, 30); T = Insert(T, 50); T = Insert(T, 65); T = Insert(T, 80); T = Insert(T, 90); T = Insert(T, 40); T = Insert(T, 5); T = Insert(T, 55); T = Insert(T, 100); T = Remove(T, 100); Travel(T); return 0; } |
以上就是關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法中紅黑二叉樹(shù)的詳解，如有疑問(wèn)請(qǐng)留言或者到本站的社區(qū)討論，感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
原文鏈接：http://blog.csdn.net/xiaohusaier/article/details/75731526
