上一章我們介紹了二叉搜索樹(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)的顏色于置。同人類的家族樹(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)行分類展示，方便有一個(gè)宏觀的印象研乒。

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í)

解答