之前看了很多寫紅黑樹的博客，但是感覺都講的不太清楚！沒說這樣操作如何使他保持平衡的，于是疑惑重重，就看不下去了，一次不經意看到一個人說 維基百科的紅黑樹 講的好，我就隨便點了一下一看——這下瘋了~，怎么講的這么好！可以說是把一個復雜的問題，講得簡單化！這太幸福了！?于是我就慢慢學會了！強烈推薦維基的這個講解，再也找不到比這還好的講解了！不知道它上邊其它的怎么樣，反正這個很好！！既然學會了，走過來了，我也要留下腳印！
下面將是我對紅黑樹的總結，里面的性感的圖片都是維基百科紅黑樹上的^_^！我討論的紅黑樹需建立在會平衡二叉樹的基礎上去學，即若不懂“旋轉”操作，請看 平衡二叉樹 的旋轉操作。
紅黑樹（RBT）的定義：它或者是一顆空樹，或者是具有一下性質的二叉查找樹：
1.節點非紅即黑。
2.根節點是黑色。
3.所有NULL結點稱為葉子節點，且認為顏色為黑 。
4.所有紅節點的子節點都為黑色。
5.從任一節點到其葉子節點的所有路徑上都包含相同數目的黑節點。
看完紅黑樹的定義是不是可暈？怎么這么多要求！！這怎么約束啊？我剛看到這5條約束，直接無語了，1-3、4還好說，第5點是怎么回事啊？怎么約束？整這么復雜的條件好干啥啊？我來簡單說說呵：第3條，顯然這里的葉子節點不是平常我們所說的葉子節點，如圖標有NIL的為葉子節點，為什么不按常規出牌，因為按一般的葉子節點也行，但會使算法更復雜；第4條，即該樹上決不允許存在兩個連續的紅節點；第5條，比如圖中紅8到1左邊的葉子節點的路徑包含2個黑節點，到6下的葉子節點的路徑也包含2個黑節點。所有性質1-5合起來約束了該樹的平衡性能--即該樹上的最長路徑不可能會大于2倍最短路徑。為什么？因為第1條該樹上的節點非紅即黑，由于第4條該樹上不允許存在兩個連續的紅節點，那么對于從一個節點到其葉子節點的一條最長的路徑一定是紅黑交錯的，那么最短路徑一定是純黑色的節點；而又第5條從任一節點到其葉子節點的所有路徑上都包含相同數目的黑節點，這么來說最長路徑上的黑節點的數目和最短路徑上的黑節點的數目相等！而又第2條根結點為黑、第3條葉子節點是黑，那么可知：最長路徑<=2*最短路徑。一顆二叉樹的平衡性能越好，那么它的效率越高！ 顯然紅黑樹的平衡性能比AVL的略差些，但是經過大量試驗證明，實際上紅黑樹的效率還是很不錯了，仍能達到O(logN) ，這個我不知道，我現在不可能做過大量試驗，只是聽人家這樣說，O(∩_∩)O哈哈~但你至少知道他的時間復雜度一定小于2O(logN)!
上邊的性質看個10遍，看懂看透徹再看操作！
插入操作
由于性質的約束：插入點不能為黑節點，應插入紅節點。因為你插入黑節點將破壞性質5，所以每次插入的點都是紅結點，但是若他的父節點也為紅，那豈不是破壞了性質4？對啊，所以要做一些“旋轉”和一些節點的變色！另為敘述方便我們給要插入的節點標為N（紅色），父節點為P，祖父節點為G，叔節點為U。下邊將一一列出所有插入時遇到的情況：
情形1 ： 該樹為空樹，直接插入根結點的位置，違反性質1，把節點顏色有紅改為黑即可 。
情形2 ： 插入節點N的父節點P為黑色，不違反任何性質，無需做任何修改 。
?情形1很簡單，情形2中P為黑色，一切安然無事，但P為紅就不一樣了，下邊是P為紅的各種情況，也是真正要學的地方！
情形3 ： N為紅，P為紅，（祖節點一定存在，且為黑，下邊同理）U也為紅，這里不論P是G的左孩子，還是右孩子；不論N是P的左孩子，還是右孩子 。
操作：如圖把P、U改為黑色，G改為紅色，未結束。
解析：N、P都為紅，違反性質4；若把P改為黑，符合性質4，顯然左邊少了一個黑節點，違反性質5；所
以
我們把G，U都改為相反色，這樣一來通過G的路徑的黑節點數目沒變，即符合4、5，但是G變紅了，若G的父節點又是紅的不就有違反了4，是這樣，所以經過上邊操作后未結束，需把G作為起始點，即把G看做一個插入的紅節點繼續向上檢索----屬于哪種情況，按那種情況操作~要么中間就結束，要么知道根結點（此時根結點變紅，一根結點向上檢索，那木有了，那就把他變為黑色吧）。
情形4 ：N為紅，P為紅，U為黑，P為G的左孩子，N為P的左孩子（或者P為G的右孩子，N為P的左孩子；反正就是同向的）。
操作：如圖P、G變色，P、G變換即左左單旋（或者右右單旋），結束。
解析：要知道經過P、G變換（旋轉），變換后P的位置就是當年G的位置，所以紅P變為黑，而黑G變為紅都是為了不違反性質5，而維持到達葉節點所包含的黑節點的數目不變！還可以理解為：也就是相當于（只是相當于，并不是實事，只是為了更好理解；）把紅N頭上的紅節點移到對面黑U的頭上；這樣即符合了性質4也不違反性質5，這樣就結束了。
?
情形5 ：N為紅，P為紅，U為黑，P為G的左孩子，N為P的右孩子（或者P為G的右孩子，N為P的左孩子；反正兩方向相反）。
?
操作：需要進行兩次變換（旋轉），圖中只顯示了一次變換-----首先P、N變換，顏色不變；然后就變成了情形4的情況，按照情況4操作，即結束。
解析：由于P、N都為紅，經變換，不違反性質5；然后就變成4的情形，此時G與G現在的左孩子變色，并變換，結束。
?
?
刪除操作
我們知道刪除需先找到“替代點”來替代刪除點而被刪除，也就是刪除的是替代點，而替代點N的至少有一個子節點為NULL，那么，若N為紅色，則兩個子節點一定都為NULL（必須地），那么直接把N刪了，不違反任何性質，ok，結束了；若N為黑色，另一個節點M不為NULL，則另一個節點M一定是紅色的，且M的子節點都為NULL（按性質來的，不明白，自己分析一下）那么把N刪掉，M占到N的位置，并改為黑色，不違反任何性質，ok，結束了；若N為黑色，另一個節點也為NULL，則把N刪掉，該位置置為NULL，顯然這個黑節點被刪除了，破壞了性質5，那么要以N節點為起始點檢索看看屬于那種情況，并作相應的操作，另還需說明N為黑點（也許是NULL，也許不是，都一樣），P為父節點，S為兄弟節點（這個我真想給兄弟節點叫B（brother）多好啊，不過人家圖就是S我也不能改，在重畫圖，太浪費時間了！S也行呵呵，就當是sister也行，哈哈）分為以下5中情況：
情形1 ： S為紅色（那么父節點P一定是黑，子節點一定是黑），N是P的左孩子（或者N是P的右孩子）。
操作：P、S變色，并交換----相當于AVL中的右右中旋轉即以P為中心S向左旋（或者是AVL中的左左中的旋轉），未結束。
解析：我們知道P的左邊少了一個黑節點，這樣操作相當于在N頭上又加了一個紅節點----不違反任何性質，但是到通過N的路徑仍少了一個黑節點，需要再把對N進行一次檢索，并作相應的操作才可以平衡（暫且不管往下看）。
?
?
情形2 ：P、S及S的孩子們都為黑。
操作：S改為紅色，未結束。
解析：S變為紅色后經過S節點的路徑的黑節點數目也減少了1，那個從P出發到其葉子節點到所有路徑所包含的黑節點數目（記為num）相等了。但是這個num比之前少了1，因為左右子樹中的黑節點數目都減少了！一般地，P是他父節點G的一個孩子，那么由G到其葉子節點的黑節點數目就不相等了，所以說沒有結束，需把P當做新的起始點開始向上檢索。
?
情形3 ：P為紅（S一定為黑），S的孩子們都為黑。
?
操作：P該為黑，S改為紅，結束。
解析：這種情況最簡單了，既然N這邊少了一個黑節點，那么S這邊就拿出了一個黑節點來共享一下，這樣一來，S這邊沒少一個黑節點，而N這邊便多了一個黑節點，這樣就恢復了平衡，多么美好的事情哈！
?
?
情形4 ：P任意色，S為黑，N是P的左孩子，S的右孩子SR為紅，S的左孩子任意（或者是N是P的右孩子，S的左孩子為紅，S的右孩子任意）。
操作：SR（SL）改為黑，P改為黑，S改為P的顏色，P、S變換--這里相對應于AVL中的右右中的旋轉（或者是AVL中的左左旋轉），結束。
解析：P、S旋轉有變色，等于給N這邊加了一個黑節點，P位置（是位置而不是P）的顏色不變，S這邊少了一個黑節點；SR有紅變黑，S這邊又增加了一個黑節點；這樣一來又恢復了平衡，結束。
?
?
情形5 ：P任意色，S為黑，N是P的左孩子，S的左孩子SL為紅，S的右孩子SR為黑（或者N是P的有孩子，S的右孩子為紅，S的左孩子為黑）。
?
操作：SL（或SR）改為黑，S改為紅，SL（SR）、S變換；此時就回到了情形4，SL（SR）變成了黑S，S變成了紅SR（SL），做情形4的操作即可，這兩次變換，其實就是對應AVL的右左的兩次旋轉（或者是AVL的左右的兩次旋轉）。
解析：這種情況如果你按情形4的操作的話，由于SR本來就是黑色，你無法彌補由于P、S的變換（旋轉）給S這邊造成的損失！所以我沒先對S、SL進行變換之后就變為情形4的情況了，何樂而不為呢？
?
好了，這五種情況都討論完了，我想強調的是：注意哪些分方向的情況，每個分方向的情形就兩種情況，不要搞迷了！下邊我寫的代碼，不用關心是什么方向，我主要是用一個指針數組即child[2]，0代表左，1代表右，進行兩個節點的變換（旋轉）的時候只需向conversion(&T,direction);傳入父節點指針的地址及子節點在父節點的方位（0或1）；有興趣可以看代碼.
歡迎大家留言指正哦^_^
下邊貼上我的C代碼：
簡介：主要是用遞歸實現插入、刪除，回溯時檢索并恢復平衡。
?
?
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 #define RED 0
5 #define BACK 1
6
7 typedef int Elemtype;
8
9 //定義一個紅黑樹的結點
10 typedef struct Red_Back_Tree
11 {
12 Elemtype e;
13 int color;
14 struct Red_Back_Tree * child[2];
15 }* RBT;
16
17 // 兩個節點變換函數
18 void conversion(RBT *T,int direction);
19
20 // 刪除一個節點的所用函數
21 int DeleteRBT(RBT *T,Elemtype e); // 刪除主(接口)函數
22 int find_replace_point(RBT gogal,RBT *l); // 尋找替代點
23 int keep_balance_for_delete(RBT *T,int direction); // 刪除的平衡操作
24 int do_with_start_point(RBT gogal,RBT *T,int direction); // 處理第一個起始點
25
26 // 插入一個節點的所用函數
27 int InsertRBT(RBT *T,Elemtype e); // 插入接口函數
28 int _InsertRBT(RBT *T,Elemtype e); // 插入主函數
29 int keep_balance_for_insert(RBT *T,int firdirection,Elemtype e);// 插入的平衡操作
30 RBT create_one_node(Elemtype e); // 新建一個節點
31
32
33
34 void conversion(RBT *T,int direction)
35 {
36 RBT f=(*T),s=f->child[direction],ss=s->child[!direction];
37
38 f->child[direction]=ss;
39 s->child[!direction]=f;
40 *T=s;
41 }
42
43 //★★★★★★★★★★★★★★★★★刪除操作★★★★★★★★★★★★★★★★★★★★★★★★★★★
44
45 int do_with_start_point(RBT gogal,RBT *T,int direction)
46 {
47 gogal->e=(*T)->e;
48 if(BACK==((*T)->color))
49 {
50 if(NULL!=(*T)->child[direction])
51 {
52 (*T)->e=(*T)->child[direction]->e;
53 free((*T)->child[direction]);
54 (*T)->child[direction]=NULL;
55 return 1;
56 }
57 else
58 {
59 free((*T));
60 *T=NULL;
61 return 0;
62 }
63 }
64 else
65 {
66 free((*T));
67 (*T)=NULL;
68 return 1;
69 }
70 }
71
72 int keep_balance_for_delete(RBT *T,int direction)
73 {
74 RBT p=(*T),b=p->child[!direction];
75
76 if(RED==b->color)
77 {
78 p->color=RED;
79 b->color=BACK;
80 // conversion(&p,!direction);//很恐怖的一個寫法，偶然中發現：這里傳的地址是假的!不是T!!
81 // 考我怎么這么傻逼!!如果不是及時發現，到調試時將是無限恐怖
82 // 將是一個巨大的隱藏的BUG!!!將會帶來巨大的麻煩!!!
83 conversion(T,!direction);
84 return keep_balance_for_delete(&((*T)->child[direction]),direction);
85 }
86 else if(BACK==p->color && BACK==b->color &&
87 (NULL==b->child[0] || BACK==b->child[0]->color) &&
88 (NULL==b->child[1] || BACK==b->child[1]->color)) //這里感覺不美，就一次為NULL卻每次要
89 { //判斷是否為NULL，不美……
90 b->color=RED;
91 return 0;
92 }
93 else if(RED==p->color &&
94 (NULL==b->child[0] || BACK==b->child[0]->color) &&
95 (NULL==b->child[1] || BACK==b->child[1]->color))
96 {
97 p->color=BACK;
98 b->color=RED;
99 return 1;
100 }
101 // 第一次調試
102 // 調試原因：由于刪除0點未按預料的操作應該是情況④，卻按⑤操作
103 // 錯誤的地方：RED==b->child[!direction] ! 丟了->color 這個錯誤我上邊錯了幾次，不過編譯器報錯改了過來
104 // 這次的編譯器不報錯，看代碼也看不錯來，最后追究到這里，一一對照才發現!!!
105 // else if(BACK==b->color && (NULL!=b->child[!direction] && RED==b->child[!direction]))
106 else if(BACK==b->color && (NULL!=b->child[!direction] && RED==b->child[!direction]->color))
107 {
108 b->color=p->color;
109 p->color=BACK;
110 b->child[!direction]->color=BACK;
111 conversion(T,!direction);
112 return 1;
113 }
114 else
115 {
116 b->child[direction]->color=p->color;
117 p->color=BACK;
118 conversion(&(p->child[!direction]),direction);//這里的p寫的才算不錯!即p也(*T)都行，一樣!
119 conversion(T,!direction);
120 return 1;
121 }
122
123 }
124
125 int find_replace_point(RBT gogal,RBT *l)
126 {
127 if(NULL!=(*l)->child[0])
128 {
129 if(find_replace_point(gogal,&(*l)->child[0])) return 1;
130 return keep_balance_for_delete(l,0);
131 //...
132 }
133 // 第二次調試---其實沒F5,F10,F11，根據結果猜測，到這里看看還真是的!
134 // 調試原因：刪除0好了，刪除1又錯了---2不見了，1還在
135 // 錯誤的地方：就在這里，找到替代點，卻沒有“替代”，這等于把替代點刪了...
136 // 這里很明顯，gogal這個刪除點指針根本就沒用...我當時忘了吧!!修改如下!
137 // else //替代點為起始點
138 // {
139 // return do_with_start_point(l,1);
140 // }
141 else
142 {
143 return do_with_start_point(gogal,l,1);
144 }
145 }
146
147 int DeleteRBT(RBT *T,Elemtype e)
148 {
149 if(!(*T)) return -1;
150 else if(e>(*T)->e)
151 {
152 if(DeleteRBT(&((*T)->child[1]),e)) return 1;
153 return keep_balance_for_delete(T,1);
154 //...
155 }
156 else if(e<(*T)->e)
157 {
158 if(DeleteRBT(&((*T)->child[0]),e)) return 1;
159 return keep_balance_for_delete(T,0);
160 //...
161 }
162 else
163 {
164 if(NULL!=(*T)->child[1]) //真正的刪除點不是起始點，需找替代點
165 {
166 if(find_replace_point((*T),&((*T)->child[1]))) return 1;
167 return keep_balance_for_delete(T,1);
168 //...
169 }
170 else //真正的刪除點就是起始點
171 {
172 return do_with_start_point((*T),T,0);
173 }
174 }
175 }
176 //★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
177
178
179 //★★★★★★★★★★★★★★★★★★★插入操作★★★★★★★★★★★★★★★★★★★★★★★★★
180
181 RBT create_one_node(Elemtype e)
182 {
183 RBT p=(RBT)malloc(sizeof(struct Red_Back_Tree));
184 p->e=e; p->color=RED;
185 p->child[0]=p->child[1]=NULL;
186 return p;
187 }
188
189 int keep_balance_for_insert(RBT *T,int firdirection,Elemtype e)
190 {
191 RBT p=(*T)->child[firdirection],u=(*T)->child[!firdirection];
192 int secdirection=( (e>p->e) ? 1 : 0 ); // 查處第二個方向
193
194 if(NULL!=u && RED==u->color) /*****③叔節點為紅色*****/
195 {
196 p->color=BACK;
197 u->color=BACK;
198 (*T)->color=RED;
199 return 1; //繼續...
200 }
201 else /*****④叔節點為黑色*****/
202 {
203 if(firdirection!=secdirection) conversion(&((*T)->child[firdirection]),secdirection);
204 (*T)->color=RED; (*T)->child[firdirection]->color=BACK;
205 conversion(T,firdirection);
206 return 0;
207 }
208 }
209
210 int _InsertRBT(RBT *T,Elemtype e)
211 {
212 int info=0;
213 if(NULL==(*T)) /*****①插入到根節點*****/ //這里只是包含這種情況
214 {
215 *T=create_one_node(e);
216 (*T)->color=RED;
217 info=1;
218 }
219 else if(e>((*T)->e))
220 {
221 info=_InsertRBT(&(*T)->child[1],e);
222 if(info<1) return info;
223 else if(info==1) /*****②父節點為黑******/
224 {
225 if(BACK==((*T)->color)) info--;
226 else info++;
227 }
228 else
229 {
230 info=keep_balance_for_insert(T,1,e);
231 }
232
233 }
234 else if(e<((*T)->e))
235 {
236 info=_InsertRBT(&((*T)->child[0]),e);
237 if(info<1) return info;
238 else if(info==1)
239 {
240 if(BACK==((*T)->color)) info--;
241 else info++;
242 }
243 else
244 {
245 info=keep_balance_for_insert(T,0,e);
246 }
247
248 }
249 else return info=-1;
250
251 return info;
252 }
253
254 int InsertRBT(RBT *T,Elemtype e) //插入節點函數返回值： -1->改點已存在 0->成功插入
255 {
256 int info=0; // info: -1->已存在 0->結束 1->回溯到父節點 2->回溯到祖節點
257
258 //2011年11月30日9:13:47 昨天晚上最后又想來這里這個if可以不要即可，也就是把它也放到_InsertRBT
259 //內處理，在InsertRBT中有個判斷即可!即改成下邊的寫法!
260 // if(NULL==(*T)) /*****①插入到根節點*****/
261 // {
262 // *T=create_one_node(e);
263 // (*T)->color=BACK;
264 // }
265 // else
266 // {
267 // info=_InsertRBT(T,e); // 經過再三思考，這里info的返回值只可能為：-1 0 1
268 // if(info>0) (*T)->color=BACK,info=0; // 查看根節點是否為紅
269 // }
270
271 info=_InsertRBT(T,e);
272 if(info==1) (*T)->color=BACK,info=0;
273 // 為了防止根結點變為紅，它其實是處理了兩種情況的后遺癥
274 // 分別是：③情況回溯上來，根節點變紅 ①情況插入點即為根節點，為紅
275 // 這里沒有直接把根結點變黑，主要是為了與_InsertRBT保持一致的寫法，其實都行!
276 return info;
277 }
278 //★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
279
280
281 //******************JUST FOR TEST********************//
282 RBT queue[1000];
283 void print(RBT cur)
284 {
285 int front=0,rear=0;
286 int count=1,temp=0;
287
288 if(NULL==cur)
289 {
290 printf("NULL\n");
291 return ;
292 }
293
294 queue[rear]=cur;
295 while(front<=rear)
296 {
297 cur=queue[front++]; count--;
298 if(NULL!=cur->child[0]) queue[++rear]=cur->child[0],temp++;
299 if(NULL!=cur->child[1]) queue[++rear]=cur->child[1],temp++;
300
301 printf("%d color->",cur->e);
302 if(BACK==cur->color) printf("BACK |");
303 else printf("RED |");
304
305 if(0==count)
306 {
307 count=temp;
308 temp=0;
309 printf("\n");
310 }
311 }
312 }
313 //*****************************************************//
314
315 //*****************DEAR MAIN***************************//
316 int main()
317 {
318 RBT T=NULL;
319 int i,nodenum=100;
320
321 print(T);
322 printf("\n");
323
324 printf("\n插入操作\n");
325 for(i=0;i<nodenum;i++)
326 {
327 InsertRBT(&T,i);
328 printf("插入%d\n",i);
329 print(T);
330 printf("\n");
331 }
332
333 // print(T);
334 printf("\n刪除操作:\n");
335
336 for(i=0;i<nodenum;i++)
337 {
338 DeleteRBT(&T,i);
339 printf("刪除%d\n",i);
340 print(T);
341 printf("\n");
342 }
343
344 return 0;
345 }
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
