傻瓜都能看懂，30張圖徹底理解紅黑樹！

作者：安卓大叔 2019-01-22 09:37:47

當(dāng)在 10 億數(shù)據(jù)中只需要進(jìn)行十幾次比較就能查找到目標(biāo)時(shí)，不禁感嘆編程之魅力!人類之偉大呀!

—學(xué)紅黑樹有感

終于，在學(xué)習(xí)了幾天的紅黑樹相關(guān)的知識(shí)后，我想把我所學(xué)所想和所感分享給大家。

紅黑樹是一種比較難的數(shù)據(jù)結(jié)構(gòu)，要完全搞懂非常耗時(shí)耗力，紅黑樹怎么自平衡?什么時(shí)候需要左旋或右旋?插入和刪除破壞了樹的平衡后怎么處理?等等一連串的問題在學(xué)習(xí)前困擾著我。

如果你在學(xué)習(xí)過程中也會(huì)存在我的疑問，那么本文對(duì)你會(huì)有幫助，本文幫助你全面、徹底地理解紅黑樹!

本文將通過圖文的方式講解紅黑樹的知識(shí)點(diǎn)，并且不會(huì)涉及到任何代碼，相信我，在懂得紅黑樹實(shí)現(xiàn)原理前，看代碼會(huì)一頭霧水的，當(dāng)原理懂了，代碼也就按部就班寫而已，沒任何難度。

閱讀本文你需具備知識(shí)點(diǎn)：

二叉查找樹
完美平衡二叉樹

紅黑樹也是二叉查找樹，我們知道，二叉查找樹這一數(shù)據(jù)結(jié)構(gòu)并不難，而紅黑樹之所以難是難在它是自平衡的二叉查找樹，在進(jìn)行插入和刪除等可能會(huì)破壞樹的平衡的操作時(shí)，需要重新自處理達(dá)到平衡狀態(tài)。

現(xiàn)在在腦海想下怎么實(shí)現(xiàn)?是不是太多情景需要考慮了?嘖嘖，先別急，通過本文的學(xué)習(xí)后，你會(huì)覺得，其實(shí)也不過如此而已。好吧，我們先來看下紅黑樹的定義和一些基本性質(zhì)。

紅黑樹定義和性質(zhì)

紅黑樹是一種含有紅黑結(jié)點(diǎn)并能自平衡的二叉查找樹。它必須滿足下面性質(zhì)：

每個(gè)節(jié)點(diǎn)要么是黑色，要么是紅色。
根節(jié)點(diǎn)是黑色。
每個(gè)葉子節(jié)點(diǎn)(Nil)是黑色。
每個(gè)紅色結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)一定都是黑色。
任意一結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)的路徑都包含數(shù)量相同的黑結(jié)點(diǎn)。

從性質(zhì) 5 又可以推出：如果一個(gè)結(jié)點(diǎn)存在黑子結(jié)點(diǎn)，那么該結(jié)點(diǎn)肯定有兩個(gè)子結(jié)點(diǎn)。

圖 1：一棵簡(jiǎn)單的紅黑樹

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

紅黑樹并不是一個(gè)完美平衡二叉查找樹，從圖 1 可以看到，根結(jié)點(diǎn) P 的左子樹顯然比右子樹高。

但左子樹和右子樹的黑結(jié)點(diǎn)的層數(shù)是相等的，也即任意一個(gè)結(jié)點(diǎn)到到每個(gè)葉子結(jié)點(diǎn)的路徑都包含數(shù)量相同的黑結(jié)點(diǎn)(性質(zhì) 5)。所以我們叫紅黑樹這種平衡為黑色完美平衡。

介紹到此，為了后面講解不至于混淆，我們還需要來約定下紅黑樹一些結(jié)點(diǎn)的叫法，如圖 2 所示：

圖 2：結(jié)點(diǎn)叫法約定

我們把正在處理(遍歷)的結(jié)點(diǎn)叫做當(dāng)前結(jié)點(diǎn)，如圖 2 中的 D，它的父親叫做父結(jié)點(diǎn)，它的父親的另外一個(gè)子結(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)保持不變。如圖 3。

右旋：以某個(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)保持不變。如圖 4。

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

圖 3：左旋

圖 4：右旋

上面所說的旋轉(zhuǎn)結(jié)點(diǎn)也即旋轉(zhuǎn)的支點(diǎn)，圖 4 和圖 5 中的 P 結(jié)點(diǎn)。我們先忽略顏色，可以看到旋轉(zhuǎn)操作不會(huì)影響旋轉(zhuǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)，父結(jié)點(diǎn)以上的結(jié)構(gòu)還是保持不變的。

左旋只影響旋轉(zhuǎn)結(jié)點(diǎn)和其右子樹的結(jié)構(gòu)，把右子樹的結(jié)點(diǎn)往左子樹挪了;右旋只影響旋轉(zhuǎn)結(jié)點(diǎn)和其左子樹的結(jié)構(gòu)，把左子樹的結(jié)點(diǎn)往右子樹挪了。

所以旋轉(zhuǎn)操作是局部的。另外可以看出旋轉(zhuǎn)能保持紅黑樹平衡的一些端詳了：當(dāng)一邊子樹的結(jié)點(diǎn)少了，那么向另外一邊子樹“借”一些結(jié)點(diǎn);當(dāng)一邊子樹的結(jié)點(diǎn)多了，那么向另外一邊子樹“租”一些結(jié)點(diǎn)。

但要保持紅黑樹的性質(zhì)，結(jié)點(diǎn)不能亂挪，還得靠變色了。怎么變?具體情景有不同變法，后面會(huì)具體講到，現(xiàn)在只需要記住紅黑樹總是通過旋轉(zhuǎn)和變色達(dá)到自平衡。

Balabala 了這么多，相信你對(duì)紅黑樹有一定印象了，那么現(xiàn)在來考考你。

思考題 1：黑結(jié)點(diǎn)可以同時(shí)包含一個(gè)紅子結(jié)點(diǎn)和一個(gè)黑子結(jié)點(diǎn)嗎? (答案見文末)

接下來先講解紅黑樹的查找熱熱身。

紅黑樹查找

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

從根結(jié)點(diǎn)開始查找，把根結(jié)點(diǎn)設(shè)置為當(dāng)前結(jié)點(diǎn)。

若當(dāng)前結(jié)點(diǎn)為空，返回 null。
若當(dāng)前結(jié)點(diǎn)不為空，用當(dāng)前結(jié)點(diǎn)的 key 跟查找 key 作比較。
若當(dāng)前結(jié)點(diǎn) key 等于查找 key，那么該 key 就是查找目標(biāo)，返回當(dāng)前結(jié)點(diǎn)。
若當(dāng)前結(jié)點(diǎn) key 大于查找 key，把當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)設(shè)置為當(dāng)前結(jié)點(diǎn)，重復(fù)步驟 2。
若當(dāng)前結(jié)點(diǎn) key 小于查找 key，把當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)設(shè)置為當(dāng)前結(jié)點(diǎn)，重復(fù)步驟 2。

如圖 5 所示：

圖 5：二叉樹查找流程圖

非常簡(jiǎn)單，但簡(jiǎn)單不代表它效率不好。正由于紅黑樹總保持黑色完美平衡，所以它的查找最壞時(shí)間復(fù)雜度為 O(2lgN)，也即整顆樹剛好紅黑相隔的時(shí)候。

能有這么好的查找效率得益于紅黑樹自平衡的特性，而這背后的付出，紅黑樹的插入操作功不可沒。

紅黑樹插入

插入操作包括兩部分工作：一是查找插入的位置;二是插入后自平衡。

查找插入的父結(jié)點(diǎn)很簡(jiǎn)單，跟查找操作區(qū)別不大：

從根結(jié)點(diǎn)開始查找。
若根結(jié)點(diǎn)為空，那么插入結(jié)點(diǎn)作為根結(jié)點(diǎn)，結(jié)束。
若根結(jié)點(diǎn)不為空，那么把根結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)。
若當(dāng)前結(jié)點(diǎn)為 null，返回當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)，結(jié)束。
若當(dāng)前結(jié)點(diǎn) key 等于查找 key，那么該 key 所在結(jié)點(diǎn)就是插入結(jié)點(diǎn)，更新結(jié)點(diǎn)的值，結(jié)束。
若當(dāng)前結(jié)點(diǎn) key 大于查找 key，把當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)設(shè)置為當(dāng)前結(jié)點(diǎn)，重復(fù)步驟 4。
若當(dāng)前結(jié)點(diǎn) key 小于查找 key，把當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)設(shè)置為當(dāng)前結(jié)點(diǎn)，重復(fù)步驟 4。

如圖 6 所示：

圖 6：紅黑樹插入位置查找

OK，插入位置已經(jīng)找到，把插入結(jié)點(diǎn)放到正確的位置就可以啦，但插入結(jié)點(diǎn)應(yīng)該是什么顏色呢?

答案是紅色。理由很簡(jiǎn)單，紅色在父結(jié)點(diǎn)(如果存在)為黑色結(jié)點(diǎn)時(shí)，紅黑樹的黑色平衡沒被破壞，不需要做自平衡操作。

但如果插入結(jié)點(diǎn)是黑色，那么插入位置所在的子樹黑色結(jié)點(diǎn)總是多 1，必須做自平衡。

所有插入情景如圖 7 所示：

圖 7：紅黑樹插入情景

嗯，插入情景很多呢，8 種插入情景!但情景 1、2 和 3 的處理很簡(jiǎn)單，而情景 4.2 和情景 4.3 只是方向反轉(zhuǎn)而已。

懂得了一種情景就能推出另外一種情景，所以總體來看，并不復(fù)雜，后續(xù)我們將一個(gè)一個(gè)情景來看，把它徹底搞懂。

另外，根據(jù)二叉樹的性質(zhì)，除了情景 2，所有插入操作都是在葉子結(jié)點(diǎn)進(jìn)行的。這點(diǎn)應(yīng)該不難理解，因?yàn)椴檎也迦胛恢脮r(shí)，我們就是在找子結(jié)點(diǎn)為空的父結(jié)點(diǎn)的。

在開始每個(gè)情景的講解前，我們還是先來約定下，如圖 8 所示：

圖 8：插入操作結(jié)點(diǎn)的叫法約定

圖 8 的字母并不代表結(jié)點(diǎn) Key 的大小。I 表示插入結(jié)點(diǎn)，P 表示插入結(jié)點(diǎn)的父結(jié)點(diǎn)，S 表示插入結(jié)點(diǎn)的叔叔結(jié)點(diǎn)，PP 表示插入結(jié)點(diǎn)的祖父結(jié)點(diǎn)。

好了，下面讓我們一個(gè)一個(gè)來分析每個(gè)插入的情景以及處理。

情景 1：紅黑樹為空樹

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

處理：把插入結(jié)點(diǎn)作為根結(jié)點(diǎn)，并把結(jié)點(diǎn)設(shè)置為黑色。

情景 2：插入結(jié)點(diǎn)的 Key 已存在

插入結(jié)點(diǎn)的 Key 已存在，既然紅黑樹總保持平衡，在插入前紅黑樹已經(jīng)是平衡的，那么把插入結(jié)點(diǎn)設(shè)置為將要替代結(jié)點(diǎn)的顏色，再把結(jié)點(diǎn)的值更新就完成插入。

處理：把 I 設(shè)為當(dāng)前結(jié)點(diǎn)的顏色，更新當(dāng)前結(jié)點(diǎn)的值為插入結(jié)點(diǎn)的值。

情景 3：插入結(jié)點(diǎn)的父結(jié)點(diǎn)為黑結(jié)點(diǎn)

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

處理：直接插入。

情景 4：插入結(jié)點(diǎn)的父結(jié)點(diǎn)為紅結(jié)點(diǎn)

再次回想下紅黑樹的性質(zhì) 2：根結(jié)點(diǎn)是黑色。如果插入的父結(jié)點(diǎn)為紅結(jié)點(diǎn)，那么該父結(jié)點(diǎn)不可能為根結(jié)點(diǎn)，所以插入結(jié)點(diǎn)總是存在祖父結(jié)點(diǎn)。這點(diǎn)很重要，因?yàn)楹罄m(xù)的旋轉(zhuǎn)操作肯定需要祖父結(jié)點(diǎn)的參與。

情景 4 又分為很多子情景，下面將進(jìn)入重點(diǎn)部分，各位看官請(qǐng)留神了。

插入情景 4.1：叔叔結(jié)點(diǎn)存在并且為紅結(jié)點(diǎn)。

從紅黑樹性質(zhì) 4 可以，祖父結(jié)點(diǎn)肯定為黑結(jié)點(diǎn)，因?yàn)椴豢梢酝瑫r(shí)存在兩個(gè)相連的紅結(jié)點(diǎn)。

那么此時(shí)該插入子樹的紅黑層數(shù)的情況是：黑紅紅。顯然最簡(jiǎn)單的處理方式是把其改為：紅黑紅。如圖 9 和圖 10 所示。

處理：將 P 和 S 設(shè)置為黑色，將 PP 設(shè)置為紅色，把 PP 設(shè)置為當(dāng)前插入結(jié)點(diǎn)。

圖 9：插入情景 4.1_1

圖 10：插入情景 4.1_2

可以看到，我們把 PP 結(jié)點(diǎn)設(shè)為紅色了，如果 PP 的父結(jié)點(diǎn)是黑色，那么無需再做任何處理。

但如果 PP 的父結(jié)點(diǎn)是紅色，根據(jù)性質(zhì) 4，此時(shí)紅黑樹已不平衡了，所以還需要把 PP 當(dāng)作新的插入結(jié)點(diǎn)，繼續(xù)做插入操作自平衡處理，直到平衡為止。

試想下 PP 剛好為根結(jié)點(diǎn)時(shí)，那么根據(jù)性質(zhì) 2，我們必須把 PP 重新設(shè)為黑色，那么樹的紅黑結(jié)構(gòu)變?yōu)椋汉诤诩t。

換句話說，從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑中，黑色結(jié)點(diǎn)增加了。這也是唯一一種會(huì)增加紅黑樹黑色結(jié)點(diǎn)層數(shù)的插入情景。

我們還可以總結(jié)出另外一個(gè)經(jīng)驗(yàn)：紅黑樹的生長(zhǎng)是自底向上的。這點(diǎn)不同于普通的二叉查找樹，普通的二叉查找樹的生長(zhǎng)是自頂向下的。

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

單純從插入前來看，也即不算情景 4.1 自底向上處理時(shí)的情況，叔叔結(jié)點(diǎn)非紅即為葉子結(jié)點(diǎn)(Nil)。

因?yàn)槿绻迨褰Y(jié)點(diǎn)為黑結(jié)點(diǎn)，而父結(jié)點(diǎn)為紅結(jié)點(diǎn)，那么叔叔結(jié)點(diǎn)所在的子樹的黑色結(jié)點(diǎn)就比父結(jié)點(diǎn)所在子樹的多了，這不滿足紅黑樹的性質(zhì) 5。后續(xù)情景同樣如此，不再多做說明了。

前文說了，需要旋轉(zhuǎn)操作時(shí)，肯定一邊子樹的結(jié)點(diǎn)多了或少了，需要租或借給另一邊。插入顯然是多的情況，那么把多的結(jié)點(diǎn)租給另一邊子樹就可以了。

插入情景 4.2.1：插入結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子結(jié)點(diǎn)。

處理：將 P 設(shè)為黑色，將 PP 設(shè)為紅色，對(duì) PP 進(jìn)行右旋。

圖 11：插入情景 4.2.1

由圖 11 可得，左邊兩個(gè)紅結(jié)點(diǎn)，右邊不存在，那么一邊一個(gè)剛剛好，并且因?yàn)闉榧t色，肯定不會(huì)破壞樹的平衡。

咦，可以把 PP 設(shè)為紅色，I 和 P 設(shè)為黑色嗎?答案是可以!看過《算法：第 4 版》的同學(xué)可能知道，書中講解的就是把 PP 設(shè)為紅色，I 和 P 設(shè)為黑色。

但把 PP 設(shè)為紅色，顯然又會(huì)出現(xiàn)情景 4.1 的情況，需要自底向上處理，做多了無謂的操作，既然能自己消化就不要麻煩祖輩們啦。

插入情景 4.2.2：插入結(jié)點(diǎn)是其父結(jié)點(diǎn)的右子結(jié)點(diǎn)。

這種情景顯然可以轉(zhuǎn)換為情景 4.2.1，如圖 12 所示，不做過多說明了。

圖 12：插入情景 4.2.2

處理：對(duì) P 進(jìn)行左旋，把 P 設(shè)置為插入結(jié)點(diǎn)，得到情景 4.2.1，進(jìn)行情景 4.2.1 的處理。

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

該情景對(duì)應(yīng)情景 4.2，只是方向反轉(zhuǎn)，不做過多說明了，直接看圖。

插入情景 4.3.1：插入結(jié)點(diǎn)是其父結(jié)點(diǎn)的右子結(jié)點(diǎn)。

圖 13：插入情景 4.3.1

處理：將 P 設(shè)為黑色，將 PP 設(shè)為紅色，對(duì) PP 進(jìn)行左旋。

插入情景 4.3.2：插入結(jié)點(diǎn)是其父結(jié)點(diǎn)的右子結(jié)點(diǎn)。

圖 14：插入情景 4.3.2

處理：對(duì) P 進(jìn)行右旋，把 P 設(shè)置為插入結(jié)點(diǎn)，得到情景 4.3.1，進(jìn)行情景 4.3.1 的處理。

好了，講完插入的所有情景了?？赡苡型瑢W(xué)會(huì)想：上面的情景舉例的都是第一次插入而不包含自底向上處理的情況，那么上面所說的情景都適合自底向上的情況嗎?答案是肯定的。

理由很簡(jiǎn)單，只要每棵子樹都能自平衡，那么整棵樹最終總是平衡的。好吧，在出個(gè)習(xí)題，請(qǐng)大家拿出筆和紙畫下試試(請(qǐng)務(wù)必動(dòng)手畫下，加深印象)。

習(xí)題 1：請(qǐng)畫出圖 15 的插入自平衡處理過程。(答案見文末)

圖 15：習(xí)題 1

紅黑樹刪除

紅黑樹插入已經(jīng)夠復(fù)雜了，但刪除更復(fù)雜，也是紅黑樹最復(fù)雜的操作了。但穩(wěn)住，勝利的曙光就在前面了!

紅黑樹的刪除操作也包括兩部分工作：一是查找目標(biāo)結(jié)點(diǎn);二是刪除后自平衡。

查找目標(biāo)結(jié)點(diǎn)顯然可以復(fù)用查找操作，當(dāng)不存在目標(biāo)結(jié)點(diǎn)時(shí)，忽略本次操作;當(dāng)存在目標(biāo)結(jié)點(diǎn)時(shí)，刪除后就得做自平衡處理了。

刪除了結(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 種情景：

若刪除結(jié)點(diǎn)無子結(jié)點(diǎn)，直接刪除。
若刪除結(jié)點(diǎn)只有一個(gè)子結(jié)點(diǎn)，用子結(jié)點(diǎn)替換刪除結(jié)點(diǎn)。
若刪除結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，用后繼結(jié)點(diǎn)(大于刪除結(jié)點(diǎn)的最小結(jié)點(diǎn))替換刪除結(jié)點(diǎn)。

補(bǔ)充說明下，情景 3 的后繼結(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í)慣上大多都是拿后繼結(jié)點(diǎn)來替代，后文的講解也是用后繼結(jié)點(diǎn)來替代。

另外告訴大家一種找前繼和后繼結(jié)點(diǎn)的直觀的方法(不知為何沒人提過，大家都知道?)：把二叉樹所有結(jié)點(diǎn)投射在X軸上，所有結(jié)點(diǎn)都是從左到右排好序的，所有目標(biāo)結(jié)點(diǎn)的前后結(jié)點(diǎn)就是對(duì)應(yīng)前繼和后繼結(jié)點(diǎn)。

如圖 16 所示：

圖 16：二叉樹投射 x 軸后有序

接下來，講一個(gè)重要的思路：刪除結(jié)點(diǎn)被替代后，在不考慮結(jié)點(diǎn)的鍵值的情況下，對(duì)于樹來說，可以認(rèn)為刪除的是替代結(jié)點(diǎn)!話很蒼白，我們看圖 17。

圖 17：刪除結(jié)點(diǎn)換位思路

在不看鍵值對(duì)的情況下，圖 17 的紅黑樹最終結(jié)果是刪除了 Q 所在位置的結(jié)點(diǎn)!這種思路非常重要，大大簡(jiǎn)化了后文講解紅黑樹刪除的情景!

基于此，上面所說的 3 種二叉樹的刪除情景可以相互轉(zhuǎn)換并且最終都是轉(zhuǎn)換為情景 1。

情景 2：刪除結(jié)點(diǎn)用其唯一的子結(jié)點(diǎn)替換，子結(jié)點(diǎn)替換為刪除結(jié)點(diǎn)后，可以認(rèn)為刪除的是子結(jié)點(diǎn)，若子結(jié)點(diǎn)又有兩個(gè)子結(jié)點(diǎn)，那么相當(dāng)于轉(zhuǎn)換為情景 3，一直自頂向下轉(zhuǎn)換，總是能轉(zhuǎn)換為情景 1。(對(duì)于紅黑樹來說，根據(jù)性質(zhì) 5.1，只存在一個(gè)子結(jié)點(diǎn)的結(jié)點(diǎn)肯定在樹末了)

情景 3：刪除結(jié)點(diǎn)用后繼結(jié)點(diǎn)(肯定不存在左結(jié)點(diǎn))，如果后繼結(jié)點(diǎn)有右子結(jié)點(diǎn)，那么相當(dāng)于轉(zhuǎn)換為情景 2，否則轉(zhuǎn)為情景 1。

二叉樹刪除結(jié)點(diǎn)情景關(guān)系圖如圖 18 所示：

圖 18：二叉樹刪除情景轉(zhuǎn)換

綜上所述，刪除操作刪除的結(jié)點(diǎn)可以看作刪除替代結(jié)點(diǎn)，而替代結(jié)點(diǎn)最后總是在樹末。

有了這結(jié)論，我們討論的刪除紅黑樹的情景就少了很多，因?yàn)槲覀冎豢紤]刪除樹末結(jié)點(diǎn)的情景了。

同樣的，我們也是先來總體看下刪除操作的所有情景，如圖 19 所示：

圖 19：紅黑樹刪除情景

哈哈，是的，即使簡(jiǎn)化了還是有 9 種情景!但跟插入操作一樣，存在左右對(duì)稱的情景，只是方向變了，沒有本質(zhì)區(qū)別。同樣的，我們還是來約定下，如圖 20 所示：

圖 20：刪除操作結(jié)點(diǎn)的叫法約定

圖 20 的字母并不代表結(jié)點(diǎn) Key 的大小。R 表示替代結(jié)點(diǎn)，P 表示替代結(jié)點(diǎn)的父結(jié)點(diǎn)，S 表示替代結(jié)點(diǎn)的兄弟結(jié)點(diǎn)，SL 表示兄弟結(jié)點(diǎn)的左子結(jié)點(diǎn)，SR 表示兄弟結(jié)點(diǎn)的右子結(jié)點(diǎn)?；疑Y(jié)點(diǎn)表示它可以是紅色也可以是黑色。

值得特別提醒的是，R 是即將被替換到刪除結(jié)點(diǎn)的位置的替代結(jié)點(diǎn)，在刪除前，它還在原來所在位置參與樹的子平衡，平衡后再替換到刪除結(jié)點(diǎn)的位置，才算刪除完成。

萬事俱備，我們進(jìn)入最后的也是最難的講解。

刪除情景 1：替換結(jié)點(diǎn)是紅色結(jié)點(diǎn)。

我們把替換結(jié)點(diǎn)換到了刪除結(jié)點(diǎn)的位置時(shí)，由于替換結(jié)點(diǎn)是紅色，刪除了也不會(huì)影響紅黑樹的平衡，只要把替換結(jié)點(diǎn)的顏色設(shè)為刪除的結(jié)點(diǎn)的顏色即可重新平衡。

處理：顏色變?yōu)閯h除結(jié)點(diǎn)的顏色。

刪除情景 2：替換結(jié)點(diǎn)是黑結(jié)點(diǎn)。

當(dāng)替換結(jié)點(diǎn)是黑色時(shí)，我們就不得不進(jìn)行自平衡處理了。我們必須還得考慮替換結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子結(jié)點(diǎn)還是右子結(jié)點(diǎn)，來做不同的旋轉(zhuǎn)操作，使樹重新平衡。

刪除情景 2.1：替換結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子結(jié)點(diǎn)。

刪除情景 2.1.1：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)是紅結(jié)點(diǎn)。

圖 21：刪除情景 2.1.1

若兄弟結(jié)點(diǎn)是紅結(jié)點(diǎn)，那么根據(jù)性質(zhì) 4，兄弟結(jié)點(diǎn)的父結(jié)點(diǎn)和子結(jié)點(diǎn)肯定為黑色，不會(huì)有其他子情景，我們按圖 21 處理，得到刪除情景 2.1.2.3(后續(xù)講解，這里先記住，此時(shí) R 仍然是替代結(jié)點(diǎn)，它的新的兄弟結(jié)點(diǎn) SL 和兄弟結(jié)點(diǎn)的子結(jié)點(diǎn)都是黑色)。

處理：將 S 設(shè)為黑色，將 P 設(shè)為紅色，對(duì) P 進(jìn)行左旋，得到情景 2.1.2.3，進(jìn)行情景 2.1.2.3 的處理。

刪除情景 2.1.2：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)是黑結(jié)點(diǎn)。

當(dāng)兄弟結(jié)點(diǎn)為黑色時(shí)，其父結(jié)點(diǎn)和子結(jié)點(diǎn)的具體顏色也無法確定(如果也不考慮自底向上的情況，子結(jié)點(diǎn)非紅即為葉子結(jié)點(diǎn)Nil，Nil結(jié)點(diǎn)為黑結(jié)點(diǎn))，此時(shí)又得考慮多種子情景。

刪除情景 2.1.2.1：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)的右子結(jié)點(diǎn)是紅結(jié)點(diǎn)，左子結(jié)點(diǎn)任意顏色。

圖 22：刪除情景 2.1.2.1

即將刪除的左子樹的一個(gè)黑色結(jié)點(diǎn)，顯然左子樹的黑色結(jié)點(diǎn)少 1 了，然而右子樹又有紅色結(jié)點(diǎn)，那么我們直接向右子樹“借”個(gè)紅結(jié)點(diǎn)來補(bǔ)充黑結(jié)點(diǎn)就好啦，此時(shí)肯定需要用旋轉(zhuǎn)處理了，如圖 22 所示。

處理：將 S 的顏色設(shè)為 P 的顏色，將 P 設(shè)為黑色，將 SR 設(shè)為黑色，對(duì) P 進(jìn)行左旋。

平衡后的圖怎么不滿足紅黑樹的性質(zhì)?前文提醒過，R 是即將替換的，它還參與樹的自平衡，平衡后再替換到刪除結(jié)點(diǎn)的位置，所以 R 最終可以看作是刪除的。

另外圖 2.1.2.1 是考慮到第一次替換和自底向上處理的情況，如果只考慮第一次替換的情況，根據(jù)紅黑樹性質(zhì)，SL 肯定是紅色或?yàn)? Nil，所以最終結(jié)果樹是平衡的。

如果是自底向上處理的情況，同樣，每棵子樹都保持平衡狀態(tài)，最終整棵樹肯定是平衡的。后續(xù)的情景同理，不做過多說明了。

刪除情景 2.1.2.2：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)的右子結(jié)點(diǎn)為黑結(jié)點(diǎn)，左子結(jié)點(diǎn)為紅結(jié)點(diǎn)。

兄弟結(jié)點(diǎn)所在的子樹有紅結(jié)點(diǎn)，我們總是可以向兄弟子樹借個(gè)紅結(jié)點(diǎn)過來，顯然該情景可以轉(zhuǎn)換為情景 2.1.2.1。如圖 23 所示：

圖 23：刪除情景 2.1.2.2

處理：將 S 設(shè)為紅色，將 SL 設(shè)為黑色，對(duì) S 進(jìn)行右旋，得到情景 2.1.2.1，進(jìn)行情景 2.1.2.1 的處理。

刪除情景 2.1.2.3：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)的子結(jié)點(diǎn)都為黑結(jié)點(diǎn)。

好了，此次兄弟子樹都沒紅結(jié)點(diǎn)“借”了，兄弟幫忙不了，找父母唄，這種情景我們把兄弟結(jié)點(diǎn)設(shè)為紅色，再把父結(jié)點(diǎn)當(dāng)作替代結(jié)點(diǎn)，自底向上處理，去找父結(jié)點(diǎn)的兄弟結(jié)點(diǎn)去“借”。

但為什么需要把兄弟結(jié)點(diǎn)設(shè)為紅色呢?顯然是為了在 P 所在的子樹中保證平衡(R 即將刪除，少了一個(gè)黑色結(jié)點(diǎn)，子樹也需要少一個(gè))，后續(xù)的平衡工作交給父輩們考慮了，還是那句，當(dāng)每棵子樹都保持平衡時(shí)，最終整棵總是平衡的。