红黑树
介紹還有一種平衡二叉樹：紅黑樹（Red Black Tree），紅黑樹由Rudolf Bayer于1972年發明，當時被稱為平衡二叉B樹（symmetric binary B-trees），1978年被Leonidas J. Guibas和Robert Sedgewick改成一個比較摩登的名字：紅黑樹。
紅黑樹和之前所講的AVL樹相似，都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能。自從紅黑樹出來后，AVL樹就被放到了博物館里，據說是紅黑樹有更好的效率，更高的統計性能。只是在我了解了紅黑樹的實現原理后，并不相信這是真的，關于這一點我們會在后面進行討論。
紅黑樹和AVL樹的差別在于它使用顏色來標識結點的高度，它所追求的是局部平衡而不是AVL樹中的很嚴格的平衡。之前我們在解說AVL樹時，已經領教過AVL樹的復雜，但AVL樹的復雜比起紅黑樹來說簡直是小巫見大巫。紅黑樹是真正的變態級數據結構。
首先來一個Silverlight做的紅黑樹的動畫，它有助于幫你理解什么是紅黑樹。這里須要注意，必須安裝Silverlight 2.0 RTW才干正常執行游戲，下載地址：
http://www.microsoft.com/silverlight/resources/install.aspx?v=2.0
使用注意事項：
l結點僅僅接收整數，假設在加入和刪除操作中輸入非法字串，則會隨機加入或刪除一個0~99之間的整數。
l能夠不在編輯框中輸入數字，直接單擊加入和刪除button進行加入和刪除操作。
l能夠拖動拖動條控制動畫速度。
紅黑樹的平衡
紅黑樹首先是一棵二叉查找樹，它每一個結點都被標上了顏色（紅色或黑色），紅黑樹滿足下面5個性質：
1、每一個結點的顏色僅僅能是紅色或黑色。
2、根結點是黑色的。
3、每一個葉子結點都帶有兩個空的黑色結點（被稱為黑哨兵），假設一個結點n的僅僅有一個左孩子，那么n的右孩子是一個黑哨兵；假設結點n僅僅有一個右孩子，那么n的左孩子是一個黑哨兵。
4、假設一個結點是紅的，則它的兩個兒子都是黑的。也就是說在一條路徑上不能出現相鄰的兩個紅色結點。
5、對于每一個結點來說，從該結點到其子孫葉結點的全部路徑上包括同樣數目的黑結點。
紅黑樹的這5個性質中，第3點是比較難理解的，但它卻很有必要。我們看圖1中的左邊這張圖，假設不使用黑哨兵，它全然滿足紅黑樹性質，結點50到兩個葉結點8和葉結點82路徑上的黑色結點數都為2個。但假設增加黑哨兵后（如圖1右圖中的小黑圓點），葉結點的個數變為8個黑哨兵，根結點50到這8個葉結點路徑上的黑高度就不一樣了，所以它并非一棵紅黑樹。
要看真正的紅黑樹請在以上動畫中加入幾個結點，看看是否滿足以上性質。
紅黑樹的旋轉操作
紅黑樹的旋轉操作和AVL樹一樣，分為LL、RR、LR、RL四種旋轉類型，區別在于旋轉完畢后改變的是結點的顏色，而不是平衡因子。旋轉動畫演示請參考AVL這篇文章中的Flash動畫：
http://www.cnblogs.com/abatei/archive/2008/11/17/1335031.html
紅黑樹上結點的插入
在討論紅黑樹的插入操作之前必需要明確，不論什么一個即將插入的新結點的初始顏色都為紅色。這一點非常easy理解，由于插入黑點會添加某條路徑上黑結點的數目，從而導致整棵樹黑高度的不平衡。但假設新結點父結點為紅色時（如圖2所看到的），將會違返紅黑樹性質：一條路徑上不能出現相鄰的兩個紅色結點。這時就需要通過一系列操作來使紅黑樹保持平衡。
為了清楚地表示插入操作下面在結點中使用“新”字表示一個新插入的結點；使用“父”字表示新插入點的父結點；使用“叔”字表示“父”結點的兄弟結點；使用“祖”字表示“父”結點的父結點。插入操作分為下面幾種情況：
1、黑父
如圖3所看到的，假設新點的父結點為黑色結點，那么插入一個紅點將不會影響紅黑樹的平衡，此時插入操作完畢。紅黑樹比AVL樹優秀的地方之中的一個在于黑父的情況比較常見，從而使紅黑樹須要旋轉的幾率相對AVL樹來說會少一些。
2．紅父
假設新點的父結點為紅色，這時就須要進行一系列操作以保證整棵樹紅黑性質。如圖3所看到的，因為父結點為紅色，此時能夠判定，祖父結點必然為黑色。這時須要依據叔父結點的顏色來決定做什么樣的操作。青色結點表示顏色未知。因為有可能須要根結點到新點的路徑上進行多次旋轉操作，而每次進行不平衡推斷的起始點（我們可將其視為新點）都不一樣。所以我們在此使用一個藍色箭頭指向這個起始點，并稱之為判定點。
2.1紅叔
當叔父結點為紅色時，如圖4所看到的，無需進行旋轉操作，僅僅要將父和叔結點變為黑色，將祖父結點變為紅色就可以。但因為祖父結點的父結點有可能為紅色，從而違反紅黑樹性質。此時必須將祖父結點作為新的判定點繼續向上進行平衡操作。
須要注意，不管“父”在“叔”的左邊還是右邊，不管“新”是“父”的左孩子還是右孩子，它們的操作都全然一樣。
2.2黑叔
當叔父結點為黑色時，須要進行旋轉，下面圖示了全部的旋轉可能
情形1：
情形2：
情形3：
情形4：
能夠觀察到，當旋轉完畢后，新的旋轉根所有為黑色，此時不須要再向上回溯進行平衡操作，插入操作完畢。須要注意，上面四張圖的“叔”、“1”、“2”、“3”結點有可能為黑哨兵結點。
事實上紅黑樹的插入操作不是非常難，甚至比AVL樹的插入操作還更簡單些。但刪除操作就遠遠比AVL樹復雜得多，以下就介紹紅黑樹的刪除操作。
紅黑樹上結點的刪除
紅黑樹本身是一棵二叉查找樹，它的刪除和二叉查找樹的刪除相似。首先要找到真正的刪除點，當被刪除結點n存在左右孩子時，真正的刪除點應該是n的中序遍在前驅，關于這一點請復習二叉查找樹的刪除。如圖9所看到的，當刪除結點20時，實際被刪除的結點應該為18，結點20的數據變為18。
所以能夠判斷出，在進行刪除操作時，真正的刪除點必然是僅僅有一個孩子或沒有孩子的結點。而依據紅黑樹的性質能夠得出下面兩個結論：
1、刪除操作中真正被刪除的必然是僅僅有一個紅色孩子或沒有孩子的結點。
2、假設真正的刪除點是一個紅色結點，那么它必然是一個葉子結點。
理解這兩點很重要，如圖10所看到的，除了情況(a)外，其它任一種況結點N都無法滿足紅黑樹性質。
在下面討論中，我們使用藍色箭頭表示真正的刪除點，它也是旋轉操作過程中的第一個判定點；真正的刪除點使用“舊”標注，舊點所在位置將被它的的孩子結點所代替（最多僅僅有一個孩子），我們使用“新”表示舊點的孩子結點。刪除操作可分為下面幾種情形：
1、舊點為紅色結點
若舊點為紅色結點，則它必然是葉子結點，直接刪除就可以。如圖11所看到的
2、一紅一黑
當舊點為黑色結點，新點為紅色結點時，將新點代替舊點位置后，將新點染成黑色就可以（如圖12所看到的）。這里須要注意：舊點為紅色，新點為黑色的情況不可能存在。
3、雙黑
當舊點和新點都為黑色時（新點為空結點時，亦屬于這樣的情況），情況比較復雜，須要依據舊點兄弟結點的顏色來決定進行什么樣的操作。我們使用“兄”來表示舊點的兄弟結點。這里可分為紅兄和黑兄兩種情況：
3.1紅兄
因為兄弟結點為紅色，所以父結點必然為黑色，而舊點被刪除后，新點代替了它的位置。下圖演示了兩種可能的情況：
紅兄的情況須要進行RR或LL型旋轉，然后將父結點染成紅色，兄結點染成黑色。然后又一次以新點為判定點進行平衡操作。我們能夠觀察到，旋轉操作完畢后，判定點沒有向上回溯，而是減少了一層，此時變成了黑兄的情況。
3.2黑兄
黑兄的情況最為復雜，須要依據黑兄孩子結點（這里用“侄”表示）和父親結點的顏色來決定做什么樣的操作。
3.2.1黑兄二黑侄紅父
如圖14所看到的，這樣的情況比較簡單，僅僅需將父結點變為黑色，兄結點變為黑色，新結點變為黑色就可以，刪除操作到此結束。
3.2.2黑兄二黑侄黑父
如圖15所看到的，此時將父結點染成新結點的顏色，新結點染成黑色，兄結點染成紅色就可以。當新結點為紅色時，父結點被染成紅色，此時須要以父結點為判定點繼續向上進行平衡操作。
3.2.3黑兄紅侄
黑兄紅侄有以下四種情形，以下分別進行圖示：
情形1：
情形2：
情形3：
情形4：
由以上圖例所看到的，看完以上四張圖的兄弟有可能會有一個疑問，假設情形1和情形2中的兩個侄子結點都為紅色時，是該進行LL旋轉還是進行LR旋轉呢？答案是進行LL旋轉。情形3和情形4則是優先進行RR旋轉的判定。
教你透徹了解紅黑樹
作者July、saturnman2010年12月29日
本文參考：Google、算法導論、STL源代碼剖析、計算機程序設計藝術。
本人聲明：個人原創，轉載請注明出處。
推薦閱讀：Left-Leaning Red-Black Trees,Dagstuhl Workshop on Data Structures, Wadern, Germany, February, 2008.
------------------------------
紅黑樹系列，四篇文章于今日已經完畢。[二零一一年一月九日]
教你透徹了解紅黑樹：
http://blog.csdn.net/v_JULY_v/archive/2010/12/29/6105630.aspx
紅黑樹算法的層層剖析與逐步實現 [此文被推薦]
http://blog.csdn.net/v_JULY_v/archive/2010/12/31/6109153.aspx
教你徹底實現紅黑樹：紅黑樹的c源代碼實現與剖析
http://blog.csdn.net/v_JULY_v/archive/2011/01/03/6114226.aspx
一步一圖一代碼，一定要讓你真正徹底明確紅黑樹 [最后更新]
http://blog.csdn.net/v_JULY_v/archive/2011/01/09/6124989.aspx
------------------------------
一、紅黑樹的介紹
先來看下算法導論對R-B Tree的介紹：
紅黑樹，一種二叉查找樹，但在每一個結點上添加一個存儲位表示結點的顏色，能夠是Red或Black。
通過對不論什么一條從根到葉子的路徑上各個結點著色方式的限制，紅黑樹確保沒有一條路徑會比其
他路徑長出倆倍，因而是接近平衡的。
前面說了，紅黑樹，是一種二叉查找樹，既然是二叉查找樹，那么它必滿足二叉查找樹的一般性質。
以下，在詳細介紹紅黑樹之前，咱們先來了解下 二叉查找樹的一般性質：
1.在一棵二叉查找樹上，運行查找、插入、刪除等操作，的時間復雜度為O（lgn）。
由于，一棵由n個結點，隨機構造的二叉查找樹的高度為lgn，所以順理成章，一般操作的運行時間為O（lgn）。
//至于n個結點的二叉樹高度為lgn的證明，可參考算法導論 第12章 二叉查找樹 第12.4節。
2.但若是一棵具有n個結點的線性鏈，則此些操作最壞情況運行時間為O（n）。
而紅黑樹，能保證在最壞情況下，主要的動態幾何操作的時間均為O（lgn）。
ok，我們知道，紅黑樹上每一個結點內含五個域，color，key，left，right。假設對應的指針域沒有，則設為NIL。
一般的，紅黑樹，滿足下面性質，即僅僅有滿足下面所有性質的樹，我們才稱之為紅黑樹：
1）每一個結點要么是紅的，要么是黑的。
2）根結點是黑的。
3）每一個葉結點，即空結點（NIL）是黑的。
4）假設一個結點是紅的，那么它的倆個兒子都是黑的。
5）對每一個結點，從該結點到其子孫結點的全部路徑上包括同樣數目的黑結點。
下圖所看到的，即是一顆紅黑樹：
此圖忽略了葉子和根部的父結點。
二、樹的旋轉知識
當我們在對紅黑樹進行插入和刪除等操作時，對樹做了改動，那么可能會違背紅黑樹的性質。
為了保持紅黑樹的性質，我們能夠通過對樹進行旋轉，即改動樹種某些結點的顏色及指針結構，以達到對紅黑樹進行
插入、刪除結點等操作時，紅黑樹依舊能保持它特有的性質（如上文所述的，五點性質）。
樹的旋轉，分為左旋和右旋，下面借助圖來做形象的解釋和介紹：
1.左旋
如上圖所看到的：
當在某個結點pivot上，做左旋操作時，我們如果它的右孩子y不是NIL[T]，pivot能夠為樹內隨意右孩子而不是NIL[T]的結點。
左旋以pivot到y之間的鏈為“支軸”進行，它使y成為該孩子樹新的根，而y的左孩子b則成為pivot的右孩子。
來看算法導論對此操作的算法實現（以x取代上述的pivot）：
LEFT-ROTATE(T,x)
1y←right[x]?Sety.
2right[x]←left[y]?Turny's left subtree intox's right subtree.
3p[left[y]]←x
4p[y]←p[x]?Linkx's parent toy.
5ifp[x] =nil[T]
6thenroot[T]←y
7else ifx=left[p[x]]
8thenleft[p[x]]←y
9elseright[p[x]]←y
10left[y]←x?Putxony's left.
11p[x]←y
2.右旋
右旋與左旋差點兒相同，再此不做具體介紹。
對于樹的旋轉，能保持不變的僅僅有原樹的搜索性質，而原樹的紅黑性質則不能保持，
在紅黑樹的數據插入和刪除后可利用旋轉和顏色重涂來恢復樹的紅黑性質。
至于有些書如 STL源代碼剖析有對雙旋的描寫敘述，事實上雙旋僅僅是單旋的兩次應用，并無新的內容，
因此這里就不再介紹了，并且左右旋也是相互對稱的，僅僅要理解當中一種旋轉就能夠了。
三、紅黑樹插入、刪除操作的詳細實現
三、I、ok，接下來，咱們來詳細了解紅黑樹的插入操作。
向一棵含有n個結點的紅黑樹插入一個新結點的操作能夠在O（lgn）時間內完畢。
算法導論：
RB-INSERT(T, z)
1 y ← nil[T]
2 x ← root[T]
3 while x ≠ nil[T]
4 do y ← x
5 if key[z] < key[x]
6 then x ← left[x]
7 else x ← right[x]
8 p[z] ← y
9 if y = nil[T]
10 then root[T] ← z
11 else if key[z] < key[y]
12 then left[y] ← z
13 else right[y] ← z
14 left[z] ← nil[T]
15 right[z] ← nil[T]
16 color[z] ← RED
17 RB-INSERT-FIXUP(T, z)
咱們來詳細分析下，此段代碼：
RB-INSERT(T, z)，將z插入紅黑樹T 之內。
為保證紅黑性質在插入操作后依舊保持，上述代碼調用了一個輔助程序RB-INSERT-FIXUP
來對結點進行又一次著色，并旋轉。
14 left[z] ← nil[T]
15 right[z] ← nil[T] //保持正確的樹結構
第16行，將z著為紅色，因為將z著為紅色可能會違背某一條紅黑樹的性質，
所以，在第17行，調用RB-INSERT-FIXUP（T,z）來保持紅黑樹的性質。
RB-INSERT-FIXUP(T, z)，例如以下所看到的：
1 while color[p[z]] = RED
2 do if p[z] = left[p[p[z]]]
3 then y ← right[p[p[z]]]
4 if color[y] = RED
5 then color[p[z]] ← BLACK ? Case 1
6 color[y] ← BLACK ? Case 1
7 color[p[p[z]]] ← RED ? Case 1
8 z ← p[p[z]] ? Case 1
9 else if z = right[p[z]]
10 then z ← p[z] ? Case 2
11 LEFT-ROTATE(T, z) ? Case 2
12 color[p[z]] ← BLACK ? Case 3
13 color[p[p[z]]] ← RED ? Case 3
14 RIGHT-ROTATE(T, p[p[z]]) ? Case 3
15 else (same as then clause
with "right" and "left" exchanged)
16 color[root[T]] ← BLACK
ok，參考一網友的言論，用自己的語言，再來詳細解剖下上述倆段代碼。
為了保證闡述清晰，我再寫下紅黑樹的5個性質：
1）每一個結點要么是紅的，要么是黑的。
2）根結點是黑的。
3）每一個葉結點，即空結點（NIL）是黑的。
4）假設一個結點是紅的，那么它的倆個兒子都是黑的。
5）對每一個結點，從該結點到其子孫結點的全部路徑上包括同樣數目的黑結點。
在對紅黑樹進行插入操作時，我們一般總是插入紅色的結點，由于這樣能夠在插入過程中盡量避免對樹的調整。
那么，我們插入一個結點后，可能會使原樹的哪些性質改變列?
由于，我們是依照二叉樹的方式進行插入，因此元素的搜索性質不會改變。
假設插入的結點是根結點，性質2會被破壞，假設插入結點的父結點是紅色，則會破壞性質4。
因此，總而言之，插入一個紅色結點僅僅會破壞性質2或性質4。
我們的回復策略非常簡單，
其一、把出現違背紅黑樹性質的結點向上移，假設能移到根結點，那么非常easy就能通過直接改動根結點來恢復紅黑樹的性質。直接通過改動根結點來恢復紅黑樹應滿足的性質。
其二、窮舉全部的可能性，之后把能歸于同一類方法處理的歸為同一類，不能直接處理的化歸到以下的幾種情況，
//注：下面情況3、4、5與上述算法導論上的代碼RB-INSERT-FIXUP(T, z)，相相應：
情況1：插入的是根結點。
原樹是空樹，此情況僅僅會違反性質2。
對策：直接把此結點涂為黑色。
情況2：插入的結點的父結點是黑色。
此不會違反性質2和性質4，紅黑樹沒有被破壞。
對策：什么也不做。
情況3：當前結點的父結點是紅色且祖父結點的還有一個子結點（叔叔結點）是紅色。
此時父結點的父結點一定存在，否則插入前就已不是紅黑樹。
與此同一時候，又分為父結點是祖父結點的左子還是右子，對于對稱性，我們僅僅要解開一個方向就能夠了。
在此，我們僅僅考慮父結點為祖父左子的情況。
同一時候，還能夠分為當前結點是其父結點的左子還是右子，可是處理方式是一樣的。我們將此歸為同一類。
對策：將當前節點的父節點和叔叔節點涂黑，祖父結點涂紅，把當前結點指向祖父節點，從新的當前節點又一次開始算法。
針對情況3，變化前（圖片來源：saturnman）[插入4節點]：
變化后：
情況4：當前節點的父節點是紅色,叔叔節點是黑色，當前節點是其父節點的右子
對策：當前節點的父節點做為新的當前節點，以新當前節點為支點左旋。
例如以下圖所看到的，變化前[插入7節點]：
變化后：
情況5：當前節點的父節點是紅色,叔叔節點是黑色，當前節點是其父節點的左子
解法：父節點變為黑色，祖父節點變為紅色，在祖父節點為支點右旋
例如以下圖所看到的[插入2節點]
變化后：
==================
三、II、ok，接下來，咱們最后來了解，紅黑樹的刪除操作：
算法導論一書，給的算法實現：
RB-DELETE(T, z) 單純刪除結點的總操作
1 if left[z] = nil[T] or right[z] = nil[T]
2 then y ← z
3 else y ← TREE-SUCCESSOR(z)
4 if left[y] ≠ nil[T]
5 then x ← left[y]
6 else x ← right[y]
7 p[x] ← p[y]
8 if p[y] = nil[T]
9 then root[T] ← x
10 else if y = left[p[y]]
11 then left[p[y]] ← x
12 else right[p[y]] ← x
13 if y 3≠ z
14 then key[z] ← key[y]
15 copy y's satellite data into z
16 if color[y] = BLACK
17 then RB-DELETE-FIXUP(T, x)
18 return y
RB-DELETE-FIXUP(T, x) 恢復與保持紅黑性質的工作
1 while x ≠ root[T] and color[x] = BLACK
2 do if x = left[p[x]]
3 then w ← right[p[x]]
4 if color[w] = RED
5 then color[w] ← BLACK ? Case 1
6 color[p[x]] ← RED ? Case 1
7 LEFT-ROTATE(T, p[x]) ? Case 1
8 w ← right[p[x]] ? Case 1
9 if color[left[w]] = BLACK and color[right[w]] = BLACK
10 then color[w] ← RED ? Case 2
11 x p[x] ? Case 2
12 else if color[right[w]] = BLACK
13 then color[left[w]] ← BLACK ? Case 3
14 color[w] ← RED ? Case 3
15 RIGHT-ROTATE(T, w) ? Case 3
16 w ← right[p[x]] ? Case 3
17 color[w] ← color[p[x]] ? Case 4
18 color[p[x]] ← BLACK ? Case 4
19 color[right[w]] ← BLACK ? Case 4
20 LEFT-ROTATE(T, p[x]) ? Case 4
21 x ← root[T] ? Case 4
22 else (same as then clause with "right" and "left" exchanged)
23 color[x] ← BLACK
為了保證下面的介紹與闡述清晰，我第三次重寫下紅黑樹的5個性質
1）每一個結點要么是紅的，要么是黑的。
2）根結點是黑的。
3）每一個葉結點，即空結點（NIL）是黑的。
4）假設一個結點是紅的，那么它的倆個兒子都是黑的。
5）對每一個結點，從該結點到其子孫結點的全部路徑上包括同樣數目的黑結點。
（相信，重述了3次，你應該有深刻記憶了。:D）
saturnman：
紅黑樹刪除的幾種情況：
-------------------------------------------------
博主提醒：
下面全部的操作，是針對紅黑樹已經刪除結點之后，
為了恢復和保持紅黑樹原有的5點性質，所做的恢復工作。
前面，我已經說了，由于插入、或刪除結點后，
可能會違背、或破壞紅黑樹的原有的性質，
所以為了使插入、或刪除結點后的樹依舊維持為一棵新的紅黑樹，
那就要做倆方面的工作：
1、部分結點顏色，又一次著色
2、調整部分指針的指向，即左旋、右旋。
而以下全部的文字，則是針對紅黑樹刪除結點后，所做的修復紅黑樹性質的工作。
二零一一年一月七日更新。
------------------------------------------------------------
(注：下面的情況3、4、5、6，與上述算法導論之代碼RB-DELETE-FIXUP(T, x) 恢復與保持
中case1，case2，case3，case4相相應。)
情況1：當前節點是紅色
解法，直接把當前節點染成黑色，結束。
此時紅黑樹性質所有恢復。
情況2：當前節點是黑色且是根節點
解法：什么都不做，結束
情況3：當前節點是黑色，且兄弟節點為紅色(此時父節點和兄弟節點的子節點分為黑)。
解法：把父節點染成紅色，把兄弟結點染成黑色，之后又一次進入算法（我們僅僅討論當前節點是其父節點左孩子時的情況）。
然后，針對父節點做一次左旋。此變換后原紅黑樹性質5不變，而把問題轉化為兄弟節點為黑色的情況。
3.變化前：
3.變化后：
情況4：當前節點是黑色，且兄弟是黑色，且兄弟節點的兩個子節點全為黑色。
解法：把當前節點和兄弟節點中抽取一重黑色追加到父節點上，把父節點當成新的當前節點，又一次進入算法。（此變換后性質5不變）
4.變化前
4.變化后
情況5：當前節點顏色是黑色，兄弟節點是黑色，兄弟的左子是紅色，右子是黑色。
解法：把兄弟結點染紅，兄弟左子節點染黑，之后再在兄弟節點為支點解右旋，
之后又一次進入算法。此是把當前的情況轉化為情況6，而性質5得以保持。
5.變化前：
5.變化后：
情況6：當前節點顏色是黑色，它的兄弟節點是黑色，可是兄弟節點的右子是紅色，兄弟節點左子的顏色隨意。
解法：把兄弟節點染成當前節點父節點的顏色，把當前節點父節點染成黑色，兄弟節點右子染成黑色，
之后以當前節點的父節點為支點進行左旋，此時算法結束，紅黑樹全部性質調整正確。
6.變化前：
6.變化后：
限于篇幅，不再過多贅述。很多其它，可參考算法導論或下文我寫的第二篇文章。
完。
July、二零一零年十二月二十九日初稿。三十日凌晨修訂。行文3個小時以上。
----------------
今下午畫紅黑樹畫了好幾個鐘頭，貼倆張圖：
紅黑樹插入的3種情況：
紅黑樹刪除的4種情況：
ok，僅僅貼倆張，很多其它，參考我寫的關于紅黑樹的第二篇文章：
紅黑樹算法的層層剖析與逐步實現[推薦]
http://blog.csdn.net/v_JULY_v/archive/2010/12/31/6109153.aspx
這篇文章針對算法實現源代碼分十層，層層、逐層剖析，相信，更清晰易懂。
//尤其文末針對紅黑樹的刪除情況，層次清晰。
July、二零一零年十二月三十一日、最后更新。
總結
- 上一篇： HTML 图片标签
- 下一篇： 为什么敏捷开发在亚洲实行不了