研究紅黑樹有10天多了，從最初了解什么是紅黑樹，到看偽代碼，到網(wǎng)上查找資料，再到自己用C代碼實現(xiàn)，感觸很多。當(dāng)然，最多的感觸就是，紅黑樹光從理解和實現(xiàn)角度來說并不復(fù)雜，這是帶給我很大安慰的地方。然后，強烈推薦一個博客吧http://blog.csdn.net/v_july_v/article/details/6284050，博主是一個很nice的人，熱心幫我解答了一個問題，而且，在他的博文里只要任何一處發(fā)現(xiàn)了錯誤，就免費送一些很好的資料的pdf版本。然后，再推薦一本書，相信很多人都知道《算法導(dǎo)論》（Intro to Algorithm）。

好了，切入正題，首先，說一下什么是紅黑樹。這里假設(shè)大家都知道樹這樣一種數(shù)據(jù)結(jié)構(gòu)，不明白的朋友快去找本數(shù)據(jù)結(jié)構(gòu)樹看一下吧。紅黑樹是一種二叉查找樹，二叉嘛，就是只分兩個叉嘍，那就是至多只有兩個子樹嘍。就好比，現(xiàn)在計劃生育，只生一個好，那么有兩個呢，最好是雙胞胎，多棒啊扯遠了

紅黑樹的每一個結(jié)點，都有五個域：我把它分為兩派，我思想突然轉(zhuǎn)到變形金剛里的博派和狂派了，額。。。這兩個派別呢，叫指針域和數(shù)據(jù)域，指針域包括parent( p )、leftchild( left )和rightchild( right )，數(shù)據(jù)域包括key和color，key值的類型可以是內(nèi)置類型或者自己typedef的新類型，color就是咱們紅黑樹的特色了，紅黑紅黑，意思就是咱們這個紅黑樹的結(jié)點呢，只有兩種顏色，要么是紅，要么是黑。哈哈，突然想到，我做人有時候也這樣，太過較真，非紅即黑，非黑即白，不好不好

《算法導(dǎo)論》第二版原文中說，if a child or the parent of a node does not exist, the corresponding field of the node contains the value NIL。通俗地說，如果某個結(jié)點它的一個孩子或者父結(jié)點不存在，那么該結(jié)點相應(yīng)的指針域就指向結(jié)點NIL(nil[T])。比如，如果結(jié)點z的父結(jié)點不存在，那么p[z] = nil[T]。算法導(dǎo)論里把nil[T]視為外結(jié)點，把紅黑樹本身帶有關(guān)鍵字的結(jié)點稱為內(nèi)結(jié)點。nil[T]的屬性p, left, right, key這四個都可以任意規(guī)定，但是color應(yīng)當(dāng)是黑色(Black)，這是為什么呢，請看下文分解

光知道紅黑樹的以上這些還是不夠，因為這樣我就可以隨便構(gòu)造紅黑樹了，我可以構(gòu)造一個結(jié)點全是黑的或者全是紅的，那么還叫什么紅黑樹啊，所以，最重要的，紅黑樹必須滿足5個條件：

1）每個結(jié)點要么是紅的，要么是黑色；

2）根結(jié)點必須是黑色的；

3）外結(jié)點（NIL）是黑色的；

4）如果一個結(jié)點是紅色的，那么他的兩個孩子都是黑的；（，怎么生出來兩個都是黑孩兒，難道...）

5）對每個結(jié)點，從該結(jié)點到子孫結(jié)點的所有路徑上包含相同的黑結(jié)點。這個如果大家不明白，請看下文，我會解釋。

這樣一個特別的樹和普通的二叉樹相比他有什么優(yōu)點呢。普通二叉樹的性能與該二叉樹的形狀有關(guān)，如果這個二叉樹長得很高，那么用它實現(xiàn)集合操作比如SEARCH，性能不會比順序表好多少，最壞情況下是O(logn)。但是，咱們的紅黑樹，根據(jù)《算法導(dǎo)論》里的引理13.1： 一棵有n個內(nèi)結(jié)點的紅黑樹的高度至多為2log(n+1)。所以，動態(tài)集合操作SEARCH、MINIMUM、MAXIMUM、SUCCESSOR和PREDECESSOR使用紅黑樹都可以在O(logn)時間內(nèi)實現(xiàn)，而接下來要說的RB-TREE-INSERT和RB-TREE-DELETE操作也能在O(logn)時間內(nèi)實現(xiàn)，總之就是說用紅黑樹實現(xiàn)動態(tài)集合操作在時間復(fù)雜性方面很不錯，很穩(wěn)定，魯棒性好，抗擊打能力強，bulabulabula...所以STL里的set就是用紅黑樹實現(xiàn)的

下面我主要說RB-TREE-INSERT和RB-TREE-DELETE，以《算法導(dǎo)論》里的偽代碼為例吧

第一個偽代碼是旋轉(zhuǎn)，至于這個什么用，請慢慢往下看。好比，想學(xué)好一門武功，總要練些基本功，嗯，就當(dāng)先練扎馬步吧

//LEFT-ROTATE(T,?x)
??y?←?right[x]?????????Set?y.
??right[x]?←?left[y]???Turn?y's?left?subtree?into?x's?right?subtree
??if?left[y]?!=?nil[T?]
?????then?p[left[y]]?←?x
??p[y]?←?p[x]??????????Link?x's?parent?to?y.
??if?p[x]?=?nil[T]
?????then?root[T]?←?y
?????else?if?x?=?left[p[x]]
?????????????then?left[p[x]]?←?y
?????????????else?right[p[x]]?←?y
??left[y]?←?x??????????Put?x?on?y's?left.
??p[x]?←?y

結(jié)合下圖，我解釋下這段偽代碼到底干啥的

現(xiàn)在我要把上圖經(jīng)過左旋后變成下圖。仔細觀察，我們發(fā)現(xiàn)實現(xiàn)上只需要改變四個結(jié)點的關(guān)系即可：結(jié)點7,11,18,14。所以，我們需要斷開7和11的聯(lián)系，11和18的聯(lián)系，18和14的聯(lián)系，重接7和18的聯(lián)系，11和14的聯(lián)系，11和18的聯(lián)系，這實際上就是上面那段偽代碼在說的事兒~

現(xiàn)在我們的結(jié)點是11，偽代碼第1行，y為11的右孩子18，第3、4行是將14的父指針指向11，這樣就斷開了14和18的聯(lián)系，重接11和14的聯(lián)系，但沒有斷完，因為18的右孩子仍然指向14，但接下來會說這個。第5行斷開7和11的聯(lián)系，使7和18產(chǎn)生聯(lián)系，第7~10行斷開原有的11和18的聯(lián)系，并重建二者的聯(lián)系（父子輪流做，爺孫天天有?。：昧?，似乎是事情辦完了，但是，別忘記了，我們斷開的聯(lián)系只是斷了一方面，就是某個結(jié)點的父結(jié)點換了，但是他原有的父結(jié)點的孩子結(jié)點仍然指向它，或者它的原有的孩子結(jié)點的父結(jié)點仍然指向它。那么，11~12兩行代碼，就是為了徹底斷絕父子關(guān)系（從此，你就是路人甲，我就是路人乙，互不相欠），很簡單，大家一看就懂，就不說了。

有了LEFT-ROTATE，那么RIGHT-ROTATE我就不說了，如果有問題，請給我留言！回去睡一覺，明早起來接著寫

休息一晚，精神飽滿。咱們繼續(xù)往下說。上回說到旋轉(zhuǎn)斷絕父子關(guān)系，曾相識之人變?yōu)槁啡?。這個旋轉(zhuǎn)的作用就在于，使得曾經(jīng)的結(jié)點互不相認，為了之后紅黑樹插入和刪除結(jié)點修正紅黑樹的屬性服務(wù)。

下面先看RB-INSERT偽代碼

//RB-INSERT(T,?z)
??y?←?nil[T]
??x?←?root[T]
??while?x?≠?nil[T]
??????do?y?←?x?
??????????if?key[z]?<?key[x]
???????????????then?x?←?left[x]?
???????????????else?x?←?right[x]
???p[z]?←?y
???if?y?=?nil[T]
??????then?root[T]?←?z?
??????else?if?key[z]?<?key[y]?
??????????then?left[y]?←?z?
??????????else?right[y]?←?z?
??left[z]?←?nil[T]?
??right[z]?←?nil[T]
??color[z]?←?RED?
??RB-INSERT-FIXUP(T,?z)

RB-INSERT-FIXUP偽代碼，既然是FIXUP，想必是在RB-INSERT里出了什么叉子，要來修正一下，使紅黑樹的5點性質(zhì)繼續(xù)得以保持嘍！

//RB-INSERT-FIXUP(T,?z)
????while?color[p[z]]?=?RED
????????do?if?p[z]?=?left[p[p[z]]]
????????????????then?y?←?right[p[p[z]]]
????????????????????????if?color[y]?=?RED
???????????????????????????then?color[p[z]]?←?BLACK????????????//?Case?1
????????????????????????????????color[y]?←?BLACK???????????????//?Case?1
????????????????????????????????color[p[p[z]]]?←?RED???????????//?Case?1
????????????????????????????????z?←?p[p[z]]????????????????????//?Case?1
???????????????????????????else?if?z?=?right[p[z]]
?????????????????????????????????????then?z?←?p[z]?????????????//?Case?2
?????????????????????????????????????????????LEFT-ROTATE(T,?z)??//?Case?2
????????????????????????????????color[p[z]]?←?BLACK????????????//?Case?3
????????????????????????????????color[p[p[z]]]?←?RED???????????//?Case?3
????????????????????????????????RIGHT-ROTATE(T,?p[p[z]])????????//?Case?3
????????????????else?(same?as?then?clause?with?“right”?and?“l(fā)eft”?exchanged)
color[root[T?]]←?BLACK

代碼好多，甭急，咱們結(jié)合下面幾個圖，一起慢慢看。

RB-INSERT第1行，定義一個y結(jié)點，并使其指向NIL，這個y的作用往下看才會知道（大俠總是埋得很深），定義結(jié)點x指向根結(jié)點。先結(jié)合下圖（這個圖是從上面那個博客里扒來的），我現(xiàn)在要在圖1中插入結(jié)點0，也就是RB-INSERT( T, z )里的z

現(xiàn)在x指向結(jié)點9，圖中黑色的NULL結(jié)點就是NIL。代碼3~7行，由于x不是NIL，因此執(zhí)行循環(huán)體，這個很簡單，就不細說了，最終，y指向紅色結(jié)點1（以后結(jié)點我就用[1]標(biāo)示），而x指向left[1]也就是NIL。代碼3~7行作用其實就是是給y賦值，而不是x，x也是為了y服務(wù)的，我們可以看到接下來的代碼里x再沒有出現(xiàn)過（狡兔死，走狗烹，飛鳥盡，良弓藏）這個y為什么要定位到[1]呢，因為我們要插入[0]，所以，自然，[0]應(yīng)該插入到[1]的左孩子結(jié)點處。于是，我們有了第8行代碼，p[0]指向[1]，這很顯然。然而，這和我們上面說旋轉(zhuǎn)時的代碼一樣，我們現(xiàn)在只是建立了[0]和[1]的一重關(guān)系，就是[0]承認[1]是我爹，但是[1]還沒說[0]你就是我兒。那么，9~13行代碼，就是為了交代這件事情。14~16行，把[0]染紅，并且找了兩個NIL當(dāng)自己的兒子(們)。

還記得我前面說過，插入的結(jié)點是紅色的嗎？這里我給出我自己的看法吧。如果，大家覺得有問題或建議，請給我留言！

我認為理由就是，如果你插入的結(jié)點是黑色的，那么必然會影響紅黑樹性質(zhì)5。那么，有人會問，如果插入結(jié)點是紅色的，那么會影響性質(zhì)4和2，這影響的還多一些呢。其實，仔細看一下，性質(zhì)2，如果插入的結(jié)點是根結(jié)點，那么很簡單，我們直接把這個結(jié)點染黑就行了。那么其實，就只剩下性質(zhì)4和性質(zhì)5的影響之間的差別了。而，這兩個性質(zhì)影響了，要修正過來都是挺麻煩的。但是，在我看來，如果插入的結(jié)點是紅色的話，在有些情況下是不需要做任何修正的，就比如我們現(xiàn)在插入[0]，直接插入，整個操作就完成了。所以，我的意思是說，插入結(jié)點如果是黑色，那么就一定要修正，因為它100%地影響性質(zhì)5，但是如果結(jié)點是紅色，并不一定要修正，比如我們在說的這個例子。這就是我對插入的結(jié)點為什么要是紅色的一些個人意見，如果大家還有什么好的意見，說來聽聽

插入完[0]后，插入就結(jié)束了，紅黑樹的5條性質(zhì)得以保持，請看下圖。

那么，我們的FIXUP沒有用到，因為color[ p[0] ] == Black。所以，我再在上圖的基礎(chǔ)上接著插入，還是按照那篇博客里提到的順序插入吧。我現(xiàn)在插入[11]，現(xiàn)在大家一眼能看出來了，怎么辦。直接插到12的左孩子處即可，so easy！插好后的圖如下。

好，我再接著插入，現(xiàn)在插入[7]，好了，我們想一下[7]應(yīng)該放在何處，根據(jù)RB-INSERT的偽代碼，那么顯然是在2的右孩子處，現(xiàn)在問題來了，color[2] == Red，color[7] == Red，違反了性質(zhì)4.所以，就需要FIXUP了。

是時候分析FXIUP了！

首先，第1行代碼，這個必須滿足，不滿足就不用修正了。我們從第2行開始看，如果插入的結(jié)點[z]的父結(jié)點是它祖父結(jié)點的左孩子，很不幸，我們這里的[2]是[1]的右孩子，那么，我們只能到最后的else里去走一遭了——else (same as then clause?with "right" and "left" exchanged)。啊，原來就是把if里的right和left互換即可，這太好辦了。咱們就按照這個意思來吧?。ò裄B-INSERT-FIXUP的2~14行代碼的left和right互換）

從第2行看起，現(xiàn)在p[z]也就是[2]是[1]的右孩子，那么y就是z的叔叔，[2]的兄弟，[1]的左孩子——[0]，當(dāng)當(dāng)當(dāng)當(dāng)，閃亮登場。

color[0] == Red，所以，執(zhí)行5~8，《算法導(dǎo)論》里叫case1，case1是什么呢，通俗地說，就是：

case1: 插入的結(jié)點的叔叔結(jié)點是紅色;

處理辦法: 把插入結(jié)點的叔叔結(jié)點和父結(jié)點染黑，把其祖父結(jié)點染紅，并將插入結(jié)點上升兩層，指向其祖父結(jié)點

處理完后，圖形如下（手畫的，很粗糙，請見諒）

然后再次進入while循環(huán)，由于p[z] == [9]，而color[9] == Black，所以，循環(huán)結(jié)束，打印輸出結(jié)點，如下圖所示，紅黑樹性質(zhì)得以保持

我們的case2和case3還沒有遇到，別急，等我喝口水，再接著說。

好了，現(xiàn)在開始研究case2，我們先在上圖中插入[19]，這個大家一眼看出來了，如果沒看出來，我也不再說了，很簡單，見下圖

現(xiàn)在，我再插入結(jié)點4，想必大家現(xiàn)在也知道了，[4]的位置是left[7]，但是卻違反了性質(zhì)4，所以需要修正，開始修正吧?。ㄗ⒁猓捎谶@里p[z] == right [p[ p[z] ] ]，屬于else ( ... "right" and "left" exchanged)）

[7] == right[2]，所以，y就是[7]的兄弟，要插入的結(jié)點[4]的叔叔（左叔叔）——NIL。color[y] == Black，所以，執(zhí)行RB-INSERT-FIXUP的9~14行代碼，是否符合case2呢，我們來看看case2：z的叔叔結(jié)點y是黑色，且z是左孩子，是case2，所以，我們z結(jié)點上升一層，指向[7]，然后以[7]為支點進行右旋，得到下圖中的右圖（手畫的）

之后，由于color[ p[z] ] == Red，再次進入while循環(huán)，z的叔叔結(jié)點是NIL，不符合case1，z == right[ p[z] ]，所以是case3的情況，那么，就把[2]和[4]的顏色互換，然后以[2]為支點進行右旋（如上圖中右圖的紅箭頭所示），就得到了下圖，紅黑樹性質(zhì)又得以保持，我們又可以得瑟了...

好了，上邊的三個case我都用圖的形式提及了，相信大家仔細看的話應(yīng)該明白了。唯一不足之處就是，實際上不是三個case，而是6個case，當(dāng)p[z] == left[ p[ p[z] ] ]時是三個，而p[z] == right[ p[ p[z] ] ]時又是三個，這里我就不細說了，聰明的你，一定會知道。

到這里，紅黑樹的結(jié)點插入操作就基本說完了，那么我們也可以總結(jié)下：

1) 結(jié)點插入，首先要找到要插入的結(jié)點的位置，插入完后，要檢查紅黑樹的5條性質(zhì)是否都滿足，不滿足就需要fix up；

2) fix up視兩大類，每一大類有三種情況，一共是六種情況，他們分別是:

①如果插入結(jié)點的父結(jié)點是其祖父結(jié)點的左孩子：

case 1: 插入結(jié)點的叔叔結(jié)點是紅色;

case 2: 插入結(jié)點的叔叔結(jié)點是黑色，且插入結(jié)點是右孩子

case 3: 插入結(jié)點的叔叔結(jié)點是黑色，且插入結(jié)點是左孩子

②如果插入結(jié)點的父結(jié)點是其祖父結(jié)點的右孩子：

case 4: 插入結(jié)點的叔叔結(jié)點是紅色;

case 5: 插入結(jié)點的叔叔結(jié)點是黑色，且插入結(jié)點是右孩子

case 6: 插入結(jié)點的叔叔結(jié)點是黑色，且插入結(jié)點是左孩子

這里要說一下，就是，通過上面一個插入[4]的例子我們可以看到，case 5轉(zhuǎn)化為了case 6，而在插入[0]時，也就是case 1的情況，其實也可以找到case 4的情況，他們是互通的，并沒有轉(zhuǎn)換到case 2, case 3。實際上，我在上面舉的這些是不全面的，case 1可以轉(zhuǎn)化到case 2,而case 2也可以轉(zhuǎn)換到case 3（請參見《算法導(dǎo)論》書中圖13-4）.同時，case 4,5, 6也有類似的轉(zhuǎn)化，至于case 1, 2, 3, 4, 5, 6之間的轉(zhuǎn)換，我還沒有碰到過，如果有請指出。

至于插入結(jié)點操作的時間復(fù)雜度的計算，《算法導(dǎo)論》里有嚴(yán)格的證明，而且也是很容易懂的，這里就不再累述。

刪除結(jié)點的操作和插入想比，稍微復(fù)雜一些，正所謂請神容易送神難，但到底有多難，我們不妨看一下，其實，弄懂了，也是so easy!

咱們在第二部分里再見吧，這篇太長了，怕大家看久了視覺疲勞，歇一歇，喝口水，打個小盹，享受一下美好的人生