------------------
本文參考：Google、算法導(dǎo)論、STL源碼剖析、計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)。
本人聲明：個(gè)人原創(chuàng)，轉(zhuǎn)載請(qǐng)注明出處。

更多請(qǐng)參考：
http://blog.csdn.net/v_JULY_v/archive/2010/12/29/6105630.aspx
詳情，參見(jiàn)My BLog：
http://blog.csdn.net/v_JULY_v

一、紅黑樹(shù)的介紹
先來(lái)看下算法導(dǎo)論對(duì)R-B Tree的介紹：
紅黑樹(shù)，一種二叉查找樹(shù)，但在每個(gè)結(jié)點(diǎn)上增加一個(gè)存儲(chǔ)位表示結(jié)點(diǎn)的顏色，可以是Red或Black。
通過(guò)對(duì)任何一條從根到葉子的路徑上各個(gè)結(jié)點(diǎn)著色方式的限制，紅黑樹(shù)確保沒(méi)有一條路徑會(huì)比其他路徑長(zhǎng)出倆倍，因而是接近平衡的。  

前面說(shuō)了，紅黑樹(shù)，是一種二叉查找樹(shù)，既然是二叉查找樹(shù)，那么它必滿(mǎn)足二叉查找樹(shù)的一般性質(zhì)。
下面，再具體介紹紅黑樹(shù)之前，咱們先來(lái)了解下 二叉查找樹(shù)的一般性質(zhì)：
1.在一棵二叉查找樹(shù)上，執(zhí)行查找、插入、刪除等操作，的時(shí)間復(fù)雜度為O（lgn）。
因?yàn)?，一棵由n個(gè)結(jié)點(diǎn)，隨機(jī)構(gòu)造的二叉查找樹(shù)的高度為O（lgn），所以順理成章，一般操作的執(zhí)行時(shí)間為O（lgn）。
（至于n個(gè)結(jié)點(diǎn)的二叉樹(shù)高度為O（lgn）的證明，可參考算法導(dǎo)論 第12章 二叉查找樹(shù)。）
2.但若是一棵具有n個(gè)結(jié)點(diǎn)的線性鏈，則此些操作最壞情況運(yùn)行時(shí)間為O（n）。

而紅黑樹(shù)，能保證在最壞情況下，基本的動(dòng)態(tài)幾何操作的時(shí)間均為O（lgn）。
ok，我們知道，紅黑樹(shù)上每個(gè)結(jié)點(diǎn)內(nèi)含五個(gè)域，color，key，left，right。如果相應(yīng)的指針域沒(méi)有，則設(shè)為NIL。

一般的，紅黑樹(shù)，滿(mǎn)足一下性質(zhì)，即只有滿(mǎn)足一下性質(zhì)的樹(shù)，我們才稱(chēng)之為紅黑樹(shù)：
1）每個(gè)結(jié)點(diǎn)要么是紅的，要么是黑的。
2）根結(jié)點(diǎn)是黑的。
3）每個(gè)葉結(jié)點(diǎn)，即空結(jié)點(diǎn)（NIL）是黑的。
4）如果一個(gè)結(jié)點(diǎn)是紅的，那么它的倆個(gè)兒子都是黑的。
5）對(duì)每個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)到其子孫結(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑結(jié)點(diǎn)。

下圖所示，即是一顆紅黑樹(shù)：

此圖忽略了葉子和根部的父結(jié)點(diǎn)。總之，可以這樣表示，就對(duì)了。:D。

二、樹(shù)的旋轉(zhuǎn)知識(shí)
當(dāng)我們?cè)趯?duì)紅黑樹(shù)進(jìn)行插入和刪除等操作時(shí)，對(duì)樹(shù)做了修改，那么可能會(huì)違背紅黑樹(shù)的性質(zhì)。
為了保持紅黑樹(shù)的性質(zhì)，我們可以通過(guò)對(duì)樹(shù)進(jìn)行旋轉(zhuǎn)，即修改樹(shù)種某些結(jié)點(diǎn)的顏色及指針結(jié)構(gòu)，以達(dá)到對(duì)紅黑樹(shù)進(jìn)行
插入、刪除結(jié)點(diǎn)等操作時(shí)，紅黑樹(shù)依然能保持它特有的性質(zhì)（如上文所述的，五點(diǎn)性質(zhì)）。

樹(shù)的旋轉(zhuǎn)，分為左旋和右旋，以下借助圖來(lái)做形象的解釋和介紹：
1.左旋


如上圖所示：
當(dāng)在某個(gè)結(jié)點(diǎn)pivot上，做左旋操作時(shí)，我們假設(shè)它的右孩子y不是NIL[T]，pivot可以為樹(shù)內(nèi)任意右孩子而不是NIL[T]的結(jié)點(diǎn)。
左旋以pivot到y(tǒng)之間的鏈為“支軸”進(jìn)行，它使y成為該孩子樹(shù)新的根，而y的左孩子b則成為pivot的右孩子。
 
來(lái)看算法導(dǎo)論對(duì)此操作的算法實(shí)現(xiàn)（以x代替上述的pivot）：

C/C++ code

 LEFT-ROTATE(T, x)
1  y ← right[x] ? Set y.
2  right[x] ← left[y]      ? Turn y's left subtree into x's right subtree.
3  p[left[y]] ← x
4  p[y] ← p[x]             ? Link x's parent to y.
5  if p[x] = nil[T]
6     then root[T] ← y
7     else if x = left[p[x]]
8             then left[p[x]] ← y
9             else right[p[x]] ← y
10  left[y] ← x             ? Put x on y's left.
11  p[x] ← y

 

2.右旋
右旋與左旋差不多，再此不做詳細(xì)介紹。


對(duì)于樹(shù)的旋轉(zhuǎn)，能保持不變的只有原樹(shù)的搜索性質(zhì)，而原樹(shù)的紅黑性質(zhì)則不能保持，
在紅黑樹(shù)的數(shù)據(jù)插入和刪除后可利用旋轉(zhuǎn)和顏色重涂來(lái)恢復(fù)樹(shù)的紅黑性質(zhì)。

至于有些書(shū)如 STL源碼剖析有對(duì)雙旋的描述，其實(shí)雙旋只是單旋的兩次應(yīng)用，并無(wú)新的內(nèi)容，
因此這里就不再介紹了，而且左右旋也是相互對(duì)稱(chēng)的，只要理解其中一種旋轉(zhuǎn)就可以了。


三、紅黑樹(shù)插入、刪除操作的具體實(shí)現(xiàn)
ok，接下來(lái)，咱們來(lái)具體了解紅黑樹(shù)的插入操作。
向一棵含有n個(gè)結(jié)點(diǎn)的紅黑樹(shù)插入一個(gè)新結(jié)點(diǎn)的操作可以在O（lgn）時(shí)間內(nèi)完成。

算法導(dǎo)論：

C/C++ code

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)

咱們來(lái)具體分析下，此段代碼：
RB-INSERT(T, z)，將z插入紅黑樹(shù)T 之內(nèi)。

為保證紅黑性質(zhì)在插入操作后依然保持，上述代碼調(diào)用了一個(gè)輔助程序RB-INSERT-FIXUP
來(lái)對(duì)結(jié)點(diǎn)進(jìn)行重新著色，并旋轉(zhuǎn)。

14 left[z] ← nil[T]
15 right[z] ← nil[T] //保持正確的樹(shù)結(jié)構(gòu)
第16行，將z著為紅色，由于將z著為紅色可能會(huì)違背某一條紅黑樹(shù)的性質(zhì)，
所以，在第17行，調(diào)用RB-INSERT-FIXUP（T,z）來(lái)保持紅黑樹(shù)的性質(zhì)。

RB-INSERT-FIXUP(T, z)，如下所示：

C/C++ code

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，參考一網(wǎng)友的言論，用自己的語(yǔ)言，再來(lái)具體解剖下上述倆段代碼。
為了保證闡述清晰，我再寫(xiě)下紅黑樹(shù)的5個(gè)性質(zhì)：

1）每個(gè)結(jié)點(diǎn)要么是紅的，要么是黑的。
2）根結(jié)點(diǎn)是黑的。
3）每個(gè)葉結(jié)點(diǎn)，即空結(jié)點(diǎn)（NIL）是黑的。
4）如果一個(gè)結(jié)點(diǎn)是紅的，那么它的倆個(gè)兒子都是黑的。
5）對(duì)每個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)到其子孫結(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑結(jié)點(diǎn)。

在對(duì)紅黑樹(shù)進(jìn)行插入操作時(shí)，我們一般總是插入紅色的結(jié)點(diǎn)，因?yàn)檫@樣可以在插入過(guò)程中盡量避免對(duì)樹(shù)的調(diào)整。
那么，我們插入一個(gè)結(jié)點(diǎn)后，可能會(huì)使原樹(shù)的哪些性質(zhì)改變列?
由于，我們是按照二叉樹(shù)的方式進(jìn)行插入，因此元素的搜索性質(zhì)不會(huì)改變。

如果插入的結(jié)點(diǎn)是根結(jié)點(diǎn)，性質(zhì)2會(huì)被破壞，如果插入結(jié)點(diǎn)的父結(jié)點(diǎn)是紅色，則會(huì)破壞性質(zhì)4。
因此，總而言之，插入一個(gè)紅色結(jié)點(diǎn)只會(huì)破壞性質(zhì)2或性質(zhì)4。
我們的回復(fù)策略很簡(jiǎn)單，
其一、把出現(xiàn)違背紅黑樹(shù)性質(zhì)的結(jié)點(diǎn)向上移，如果能移到根結(jié)點(diǎn)，那么很容易就能通過(guò)直接修改根結(jié)點(diǎn)來(lái)恢復(fù)紅黑樹(shù)的性質(zhì)。直接通過(guò)修改根結(jié)點(diǎn)來(lái)恢復(fù)紅黑樹(shù)應(yīng)滿(mǎn)足的性質(zhì)。
其二、窮舉所有的可能性，之后把能歸于同一類(lèi)方法處理的歸為同一類(lèi)，不能直接處理的化歸到下面的幾種情況，

情況1：插入的是根結(jié)點(diǎn)。
原樹(shù)是空樹(shù)，此情況只會(huì)違反性質(zhì)2。
  對(duì)策：直接把此結(jié)點(diǎn)涂為黑色。
情況2：插入的結(jié)點(diǎn)的父結(jié)點(diǎn)是黑色。
此不會(huì)違反性質(zhì)2和性質(zhì)4，紅黑樹(shù)沒(méi)有被破壞。
  對(duì)策：什么也不做。
情況3：當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)是紅色且祖父結(jié)點(diǎn)的另一個(gè)子結(jié)點(diǎn)（叔叔結(jié)點(diǎn)）是紅色。
此時(shí)父結(jié)點(diǎn)的父結(jié)點(diǎn)一定存在，否則插入前就已不是紅黑樹(shù)。
與此同時(shí)，又分為父結(jié)點(diǎn)是祖父結(jié)點(diǎn)的左子還是右子，對(duì)于對(duì)稱(chēng)性，我們只要解開(kāi)一個(gè)方向就可以了。

在此，我們只考慮父結(jié)點(diǎn)為祖父左子的情況。
同時(shí)，還可以分為當(dāng)前結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子還是右子，但是處理方式是一樣的。我們將此歸為同一類(lèi)。
  對(duì)策：將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)涂黑，祖父結(jié)點(diǎn)涂紅，把當(dāng)前結(jié)點(diǎn)指向祖父節(jié)點(diǎn)，從新的當(dāng)前節(jié)點(diǎn)重新開(kāi)始算法。

針對(duì)情況3，變化前（圖片來(lái)源：saturnman）：
  變化前：


變化后：


情況4：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色,叔叔節(jié)點(diǎn)是黑色，當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的右子
對(duì)策：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)做為新的當(dāng)前節(jié)點(diǎn)，以新當(dāng)前節(jié)點(diǎn)為支點(diǎn)左旋。
如下圖所示，變化前：


 變化后：


情況5：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色,叔叔節(jié)點(diǎn)是黑色，當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的左子
解法：父節(jié)點(diǎn)變?yōu)楹谏?，祖父?jié)點(diǎn)變?yōu)榧t色，在祖父節(jié)點(diǎn)為支點(diǎn)右旋

如下圖所示


變化后：



--------------------------------
 ok，接下來(lái)，咱們最后來(lái)簡(jiǎn)單了解，紅黑樹(shù)的刪除操作：
算法導(dǎo)論一書(shū)，給的算法實(shí)現(xiàn)： 
RB-DELETE(T, z)
 

C/C++ code

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

C/C++ code

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

saturnman：
我們紅黑樹(shù)刪除的幾種情況：
(注：以下各種情況，不與上述算法導(dǎo)論之上的代碼相對(duì)應(yīng)。)
情況1：當(dāng)前節(jié)點(diǎn)是紅+黑色
  解法，直接把當(dāng)前節(jié)點(diǎn)染成黑色，結(jié)束。
此時(shí)紅黑樹(shù)性質(zhì)全部恢復(fù)。

情況2：當(dāng)前節(jié)點(diǎn)是黑+黑且是根節(jié)點(diǎn)
  解法：什么都不做，結(jié)束

情況3：當(dāng)前節(jié)點(diǎn)是黑+黑且兄弟節(jié)點(diǎn)為紅色(此時(shí)父節(jié)點(diǎn)和兄弟節(jié)點(diǎn)的子節(jié)點(diǎn)分為黑)。
  解法：把父節(jié)點(diǎn)染成紅色，把兄弟結(jié)點(diǎn)染成黑色，之后重新進(jìn)入算法（我們只討論當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)左孩子時(shí)的情況）。此變換后原紅黑樹(shù)性質(zhì)5不變，而把問(wèn)題轉(zhuǎn)化為兄弟節(jié)點(diǎn)為黑色的情況。
  3.變化前：
..........

===========
更多請(qǐng)參考：
http://blog.csdn.net/v_JULY_v/archive/2010/12/29/6105630.aspx
詳情，參見(jiàn)My BLog：
http://blog.csdn.net/v_JULY_v