紅黑樹(shù)之我見(jiàn)（一）

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

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

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

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

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

1）每個(gè)結(jié)點(diǎn)要么是紅的，要么是黑色；

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

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

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

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

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

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

第一個(gè)偽代碼是旋轉(zhuǎn)，至于這個(gè)什么用，請(qǐng)慢慢往下看。好比，想學(xué)好一門(mén)武功，總要練些基本功，嗯，就當(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)過(guò)左旋后變成下圖。仔細(xì)觀察，我們發(fā)現(xiàn)實(shí)現(xiàn)上只需要改變四個(gè)結(jié)點(diǎn)的關(guān)系即可：結(jié)點(diǎn)7,11,18,14。所以，我們需要斷開(kāi)7和11的聯(lián)系，11和18的聯(lián)系，18和14的聯(lián)系，重接7和18的聯(lián)系，11和14的聯(lián)系，11和18的聯(lián)系，這實(shí)際上就是上面那段偽代碼在說(shuō)的事兒~

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

有了LEFT-ROTATE，那么RIGHT-ROTATE我就不說(shuō)了，如果有問(wèn)題，請(qǐng)給我留言！回去睡一覺(jué)，明早起來(lái)接著寫(xiě)

休息一晚，精神飽滿(mǎn)。咱們繼續(xù)往下說(shuō)。上回說(shuō)到旋轉(zhuǎn)斷絕父子關(guān)系，曾相識(shí)之人變?yōu)槁啡?。這個(gè)旋轉(zhuǎn)的作用就在于，使得曾經(jīng)的結(jié)點(diǎn)互不相認(rèn)，為了之后紅黑樹(shù)插入和刪除結(jié)點(diǎn)修正紅黑樹(shù)的屬性服務(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里出了什么叉子，要來(lái)修正一下，使紅黑樹(shù)的5點(diǎn)性質(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é)合下面幾個(gè)圖，一起慢慢看。

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

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

還記得我前面說(shuō)過(guò)，插入的結(jié)點(diǎn)是紅色的嗎？這里我給出我自己的看法吧。如果，大家覺(jué)得有問(wèn)題或建議，請(qǐng)給我留言！

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

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

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

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

是時(shí)候分析FXIUP了！

首先，第1行代碼，這個(gè)必須滿(mǎn)足，不滿(mǎn)足就不用修正了。我們從第2行開(kāi)始看，如果插入的結(jié)點(diǎn)[z]的父結(jié)點(diǎn)是它祖父結(jié)點(diǎn)的左孩子，很不幸，我們這里的[2]是[1]的右孩子，那么，我們只能到最后的else里去走一遭了——else (same as then clause?with "right" and "left" exchanged)。啊，原來(lái)就是把if里的right和left互換即可，這太好辦了。咱們就按照這個(gè)意思來(lái)吧?。ò裄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)，閃亮登場(chǎng)。

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

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

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

處理完后，圖形如下（手畫(huà)的，很粗糙，請(qǐng)見(jiàn)諒）

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

我們的case2和case3還沒(méi)有遇到，別急，等我喝口水，再接著說(shuō)。

好了，現(xiàn)在開(kāi)始研究case2，我們先在上圖中插入[19]，這個(gè)大家一眼看出來(lái)了，如果沒(méi)看出來(lái)，我也不再說(shuō)了，很簡(jiǎn)單，見(jiàn)下圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

咱們?cè)诘诙糠掷镌僖?jiàn)吧，這篇太長(zhǎng)了，怕大家看久了視覺(jué)疲勞，歇一歇，喝口水，打個(gè)小盹，享受一下美好的人生