上一章我們介紹了二叉搜索樹(shù)，文末說(shuō)了二叉搜索樹(shù)的不足，如果搜索樹(shù)的高度較低時(shí)，這些集合操作會(huì)執(zhí)行的較快，然而，如果樹(shù)的高度較高時(shí)，這些集合操作可能并不比在鏈表上執(zhí)行的快，紅黑樹(shù)（red-black tree）是許多"平衡"搜索樹(shù)的一種，可以保證在最壞的情況下基本動(dòng)態(tài)集合操作的時(shí)間復(fù)雜度為O(lgn)。

性質(zhì)

紅黑樹(shù)是一顆二叉搜索樹(shù)，它在每個(gè)節(jié)點(diǎn)上增加一個(gè)存儲(chǔ)位來(lái)表示節(jié)點(diǎn)顏色（red或black），通過(guò)對(duì)任何一條從根到葉子節(jié)點(diǎn)的簡(jiǎn)單路徑上各個(gè)節(jié)點(diǎn)的顏色來(lái)進(jìn)行約束，紅黑樹(shù)確保沒(méi)有一條路徑會(huì)比其他路徑長(zhǎng)出2倍，因?yàn)槭?strong>近似平衡的。
樹(shù)中每個(gè)節(jié)點(diǎn)包含5個(gè)屬性：color、key、left、right、和p。

性質(zhì)1：節(jié)點(diǎn)是紅色或黑色。
性質(zhì)2：根節(jié)點(diǎn)是黑色。
性質(zhì)3：所有葉子都是黑色（葉子是NIL節(jié)點(diǎn)）。
性質(zhì)4：每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))
性質(zhì)5：從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

下圖就是一顆簡(jiǎn)單的紅黑樹(shù)。其中Nil為葉子結(jié)點(diǎn)，并且它是黑色的。(值得提醒注意的是，在Java中，葉子結(jié)點(diǎn)是為null的結(jié)點(diǎn)。)

為了后面講解不至于混淆，我們還需要來(lái)約定下紅黑樹(shù)一些結(jié)點(diǎn)的叫法，如下圖所示。

旋轉(zhuǎn)

當(dāng)我們?cè)趯?duì)紅黑樹(shù)進(jìn)行插入和刪除等操作時(shí)，對(duì)樹(shù)做了修改，那么可能會(huì)違背紅黑樹(shù)的性質(zhì)。為了保持紅黑樹(shù)的性質(zhì)，前面講到紅黑樹(shù)能自平衡，它靠的是什么？三種操作：左旋、右旋和變色。

• 左旋：以某個(gè)結(jié)點(diǎn)作為支點(diǎn)(旋轉(zhuǎn)結(jié)點(diǎn))，其右子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)，右子結(jié)點(diǎn)的左子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的右子結(jié)點(diǎn)，左子結(jié)點(diǎn)保持不變。如圖。
  

• 右旋：以某個(gè)結(jié)點(diǎn)作為支點(diǎn)(旋轉(zhuǎn)結(jié)點(diǎn))，其左子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)，左子結(jié)點(diǎn)的右子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的左子結(jié)點(diǎn)，右子結(jié)點(diǎn)保持不變。如圖。
  

• 變色：結(jié)點(diǎn)的顏色由紅變黑或由黑變紅。

可以看到旋轉(zhuǎn)操作不會(huì)影響旋轉(zhuǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)，父結(jié)點(diǎn)以上的結(jié)構(gòu)還是保持不變的。
所以旋轉(zhuǎn)操作是局部的。另外可以看出旋轉(zhuǎn)能保持紅黑樹(shù)平衡的一些端詳了：當(dāng)一邊子樹(shù)的結(jié)點(diǎn)少了，那么向另外一邊子樹(shù)“借”一些結(jié)點(diǎn)；當(dāng)一邊子樹(shù)的結(jié)點(diǎn)多了，那么向另外一邊子樹(shù)“租”一些結(jié)點(diǎn)。
但要保持紅黑樹(shù)的性質(zhì)，結(jié)點(diǎn)不能亂挪，還得靠變色了。怎么變？具體情景又不同變法，后面會(huì)具體講到，現(xiàn)在只需要記住紅黑樹(shù)總是通過(guò)旋轉(zhuǎn)和變色達(dá)到自平衡。

紅黑樹(shù)查找

因?yàn)榧t黑樹(shù)是一顆二叉平衡樹(shù)，并且查找不會(huì)破壞樹(shù)的平衡，所以查找跟二叉平衡樹(shù)的查找無(wú)異：

1、從根結(jié)點(diǎn)開(kāi)始查找，把根結(jié)點(diǎn)設(shè)置為當(dāng)前結(jié)點(diǎn)；
2、若當(dāng)前結(jié)點(diǎn)為空，返回null；
3、若當(dāng)前結(jié)點(diǎn)不為空，用當(dāng)前結(jié)點(diǎn)的key跟查找key作比較；
4、若當(dāng)前結(jié)點(diǎn)key等于查找key，那么該key就是查找目標(biāo)，返回當(dāng)前結(jié)點(diǎn)；
5、若當(dāng)前結(jié)點(diǎn)key大于查找key，把當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)設(shè)置為當(dāng)前結(jié)點(diǎn)，重復(fù)步驟2；
6、若當(dāng)前結(jié)點(diǎn)key小于查找key，把當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)設(shè)置為當(dāng)前結(jié)點(diǎn)，重復(fù)步驟2；
如下圖所示：

紅黑樹(shù)插入

插入操作包括兩部分工作：一查找插入的位置；二插入后自平衡。
我們首先以二叉查找樹(shù)的方法增加節(jié)點(diǎn)并標(biāo)記為紅色。（如果設(shè)為黑色，就會(huì)導(dǎo)致根到葉子的路徑上有一條路上，多一個(gè)額外的黑節(jié)點(diǎn)，這個(gè)是很難調(diào)整的。但是設(shè)為紅色節(jié)點(diǎn)后，可能會(huì)導(dǎo)致出現(xiàn)兩個(gè)連續(xù)紅色節(jié)點(diǎn)的沖突，那么可以通過(guò)顏色調(diào)換（color flips）和樹(shù)旋轉(zhuǎn)來(lái)調(diào)整。）下面要進(jìn)行什么操作取決于其他臨近節(jié)點(diǎn)的顏色。同人類(lèi)的家族樹(shù)中一樣，我們將使用術(shù)語(yǔ)叔父節(jié)點(diǎn)來(lái)指一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)。

情形1： 紅黑樹(shù)為空樹(shù)
最簡(jiǎn)單的一種情景，直接把插入結(jié)點(diǎn)作為根結(jié)點(diǎn)就行，但注意，根據(jù)紅黑樹(shù)性質(zhì)2：根節(jié)點(diǎn)是黑色。還需要把插入結(jié)點(diǎn)設(shè)為黑色。

情形2： 插入結(jié)點(diǎn)的父結(jié)點(diǎn)為黑色結(jié)點(diǎn)
由于插入的結(jié)點(diǎn)是紅色的，當(dāng)插入結(jié)點(diǎn)的黑色時(shí)，并不會(huì)影響紅黑樹(shù)的平衡，直接插入即可，無(wú)需做自平衡。

情形3： 插入結(jié)點(diǎn)的父結(jié)點(diǎn)為紅色結(jié)點(diǎn)
這種情況的子情況比較多，下面用腦圖進(jìn)行分類(lèi)展示，方便有一個(gè)宏觀(guān)的印象。

3.1：叔叔結(jié)點(diǎn)存在并且為紅結(jié)點(diǎn)
從紅黑樹(shù)性質(zhì)4可以，祖父結(jié)點(diǎn)肯定為黑結(jié)點(diǎn)，因?yàn)椴豢梢酝瑫r(shí)存在兩個(gè)相連的紅結(jié)點(diǎn)。那么此時(shí)該插入子樹(shù)的紅黑層數(shù)的情況是：黑紅紅。顯然最簡(jiǎn)單的處理方式是把其改為：紅黑紅。

3.2：叔叔結(jié)點(diǎn)不存在或?yàn)楹诮Y(jié)點(diǎn)，并且插入結(jié)點(diǎn)的父親結(jié)點(diǎn)是祖父結(jié)點(diǎn)的左子結(jié)點(diǎn),插入結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子結(jié)點(diǎn)

3.3：叔叔結(jié)點(diǎn)不存在或?yàn)楹诮Y(jié)點(diǎn)，并且插入結(jié)點(diǎn)的父親結(jié)點(diǎn)是祖父結(jié)點(diǎn)的左子結(jié)點(diǎn),插入結(jié)點(diǎn)是其父結(jié)點(diǎn)的右子結(jié)點(diǎn)
這種情景顯然可以轉(zhuǎn)換為情景3.2

3.4：叔叔結(jié)點(diǎn)不存在或?yàn)楹诮Y(jié)點(diǎn)，并且插入結(jié)點(diǎn)的父親結(jié)點(diǎn)是祖父結(jié)點(diǎn)的右子結(jié)點(diǎn),插入結(jié)點(diǎn)是其父結(jié)點(diǎn)的右子結(jié)點(diǎn)

3.5：叔叔結(jié)點(diǎn)不存在或?yàn)楹诮Y(jié)點(diǎn)，并且插入結(jié)點(diǎn)的父親結(jié)點(diǎn)是祖父結(jié)點(diǎn)的右子結(jié)點(diǎn),插入結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子結(jié)點(diǎn)

綜合練習(xí)
請(qǐng)畫(huà)出下圖的插入自平衡處理過(guò)程。

練習(xí)

解答