作者 | 安卓大叔

成都創(chuàng)新互聯(lián)一直通過網(wǎng)站建設(shè)和網(wǎng)站營銷幫助企業(yè)獲得更多客戶資源。 以"深度挖掘，量身打造，注重實效"的一站式服務(wù)，以成都網(wǎng)站制作、網(wǎng)站建設(shè)、移動互聯(lián)產(chǎn)品、網(wǎng)絡(luò)營銷推廣服務(wù)為核心業(yè)務(wù)。十載網(wǎng)站制作的經(jīng)驗，使用新網(wǎng)站建設(shè)技術(shù)，全新開發(fā)出的標(biāo)準(zhǔn)網(wǎng)站，不但價格便宜而且實用、靈活，特別適合中小公司網(wǎng)站制作。網(wǎng)站管理系統(tǒng)簡單易用，維護方便，您可以完全操作網(wǎng)站資料，是中小公司快速網(wǎng)站建設(shè)的選擇。

來源 | www.jianshu.com/u/1d933ff900e7

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

閱讀本文你需具備知識點：

二叉查找樹

完美平衡二叉樹

事不宜遲，讓我們進入正題吧。

紅黑樹也是二叉查找樹，我們知道，二叉查找樹這一數(shù)據(jù)結(jié)構(gòu)并不難，而紅黑樹之所以難是難在它是自平衡的二叉查找樹，在進行插入和刪除等可能會破壞樹的平衡的操作時，需要重新自處理達到平衡狀態(tài)?，F(xiàn)在在腦海想下怎么實現(xiàn)？是不是太多情景需要考慮了？嘖嘖，先別急，通過本文的學(xué)習(xí)后，你會覺得，其實也不過如此而已。好吧，我們先來看下紅黑樹的定義和一些基本性質(zhì)。

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

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

• 性質(zhì)1：每個節(jié)點要么是黑色，要么是紅色。

• 性質(zhì)2：根節(jié)點是黑色。

• 性質(zhì)3：每個葉子節(jié)點（NIL）是黑色。

• 性質(zhì)4：每個紅色結(jié)點的兩個子結(jié)點一定都是黑色。

• 性質(zhì)5：任意一結(jié)點到每個葉子結(jié)點的路徑都包含數(shù)量相同的黑結(jié)點。

從性質(zhì)5又可以推出：

• 性質(zhì)5.1：如果一個結(jié)點存在黑子結(jié)點，那么該結(jié)點肯定有兩個子結(jié)點

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

圖1 一顆簡單的紅黑樹

紅黑樹并不是一個完美平衡二叉查找樹，從圖1可以看到，根結(jié)點P的左子樹顯然比右子樹高，但左子樹和右子樹的黑結(jié)點的層數(shù)是相等的，也即任意一個結(jié)點到到每個葉子結(jié)點的路徑都包含數(shù)量相同的黑結(jié)點(性質(zhì)5)。所以我們叫紅黑樹這種平衡為黑色完美平衡。

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

圖2 結(jié)點叫法約定

我們把正在處理(遍歷)的結(jié)點叫做當(dāng)前結(jié)點，如圖2中的D，它的父親叫做父結(jié)點，它的父親的另外一個子結(jié)點叫做兄弟結(jié)點，父親的父親叫做祖父結(jié)點。

前面講到紅黑樹能自平衡，它靠的是什么？三種操作：左旋、右旋和變色。

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

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

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

圖3 左旋

圖4 右旋

上面所說的旋轉(zhuǎn)結(jié)點也即旋轉(zhuǎn)的支點，圖4和圖5中的P結(jié)點。

我們先忽略顏色，可以看到旋轉(zhuǎn)操作不會影響旋轉(zhuǎn)結(jié)點的父結(jié)點，父結(jié)點以上的結(jié)構(gòu)還是保持不變的。

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

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

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

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

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

思考題1：黑結(jié)點可以同時包含一個紅子結(jié)點和一個黑子結(jié)點嗎？ (答案見文末)

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

紅黑樹查找

因為紅黑樹是一顆二叉平衡樹，并且查找不會破壞樹的平衡，所以查找跟二叉平衡樹的查找無異：

1. 從根結(jié)點開始查找，把根結(jié)點設(shè)置為當(dāng)前結(jié)點；

2. 若當(dāng)前結(jié)點為空，返回null；

3. 若當(dāng)前結(jié)點不為空，用當(dāng)前結(jié)點的key跟查找key作比較；

4. 若當(dāng)前結(jié)點key等于查找key，那么該key就是查找目標(biāo)，返回當(dāng)前結(jié)點；

5. 若當(dāng)前結(jié)點key大于查找key，把當(dāng)前結(jié)點的左子結(jié)點設(shè)置為當(dāng)前結(jié)點，重復(fù)步驟2；

6. 若當(dāng)前結(jié)點key小于查找key，把當(dāng)前結(jié)點的右子結(jié)點設(shè)置為當(dāng)前結(jié)點，重復(fù)步驟2；

如圖5所示：

 圖5 二叉樹查找流程圖

非常簡單，但簡單不代表它效率不好。正由于紅黑樹總保持黑色完美平衡，所以它的查找最壞時間復(fù)雜度為O(2lgN)，也即整顆樹剛好紅黑相隔的時候。能有這么好的查找效率得益于紅黑樹自平衡的特性，而這背后的付出，紅黑樹的插入操作功不可沒～

紅黑樹插入

插入操作包括兩部分工作：一查找插入的位置；二插入后自平衡。查找插入的父結(jié)點很簡單，跟查找操作區(qū)別不大：

1. 從根結(jié)點開始查找；

2. 若根結(jié)點為空，那么插入結(jié)點作為根結(jié)點，結(jié)束。

3. 若根結(jié)點不為空，那么把根結(jié)點作為當(dāng)前結(jié)點；

4. 若當(dāng)前結(jié)點為null，返回當(dāng)前結(jié)點的父結(jié)點，結(jié)束。

5. 若當(dāng)前結(jié)點key等于查找key，那么該key所在結(jié)點就是插入結(jié)點，更新結(jié)點的值，結(jié)束。

6. 若當(dāng)前結(jié)點key大于查找key，把當(dāng)前結(jié)點的左子結(jié)點設(shè)置為當(dāng)前結(jié)點，重復(fù)步驟4；

7. 若當(dāng)前結(jié)點key小于查找key，把當(dāng)前結(jié)點的右子結(jié)點設(shè)置為當(dāng)前結(jié)點，重復(fù)步驟4；

如圖6所示：

圖6 紅黑樹插入位置查找

ok，插入位置已經(jīng)找到，把插入結(jié)點放到正確的位置就可以啦，但插入結(jié)點是應(yīng)該是什么顏色呢？答案是紅色。理由很簡單，紅色在父結(jié)點（如果存在）為黑色結(jié)點時，紅黑樹的黑色平衡沒被破壞，不需要做自平衡操作。但如果插入結(jié)點是黑色，那么插入位置所在的子樹黑色結(jié)點總是多1，必須做自平衡。

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

圖7 紅黑樹插入情景

嗯，插入情景很多呢，8種插入情景！但情景1、2和3的處理很簡單，而情景4.2和情景4.3只是方向反轉(zhuǎn)而已，懂得了一種情景就能推出另外一種情景，所以總體來看，并不復(fù)雜，后續(xù)我們將一個一個情景來看，把它徹底搞懂。

另外，根據(jù)二叉樹的性質(zhì)，除了情景2，所有插入操作都是在葉子結(jié)點進行的。這點應(yīng)該不難理解，因為查找插入位置時，我們就是在找子結(jié)點為空的父結(jié)點的。

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

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

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

好了，下面讓我們一個一個來分析每個插入的情景以其處理。

插入情景1：紅黑樹為空樹

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

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

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

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

處理：

• 把I設(shè)為當(dāng)前結(jié)點的顏色

• 更新當(dāng)前結(jié)點的值為插入結(jié)點的值

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

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

處理：直接插入。

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

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

情景4又分為很多子情景，下面將進入重點部分，各位看官請留神了。

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

從紅黑樹性質(zhì)4可以，祖父結(jié)點肯定為黑結(jié)點，因為不可以同時存在兩個相連的紅結(jié)點。那么此時該插入子樹的紅黑層數(shù)的情況是：黑紅紅。顯然最簡單的處理方式是把其改為：紅黑紅。如圖9和圖10所示。

處理：

• 將P和S設(shè)置為黑色

• 將PP設(shè)置為紅色

• 把PP設(shè)置為當(dāng)前插入結(jié)點

圖9 插入情景4.1_1

圖10 插入情景4.1_2

可以看到，我們把PP結(jié)點設(shè)為紅色了，如果PP的父結(jié)點是黑色，那么無需再做任何處理；但如果PP的父結(jié)點是紅色，根據(jù)性質(zhì)4，此時紅黑樹已不平衡了，所以還需要把PP當(dāng)作新的插入結(jié)點，繼續(xù)做插入操作自平衡處理，直到平衡為止。

試想下PP剛好為根結(jié)點時，那么根據(jù)性質(zhì)2，我們必須把PP重新設(shè)為黑色，那么樹的紅黑結(jié)構(gòu)變?yōu)椋汉诤诩t。換句話說，從根結(jié)點到葉子結(jié)點的路徑中，黑色結(jié)點增加了。這也是唯一一種會增加紅黑樹黑色結(jié)點層數(shù)的插入情景。

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

插入情景4.2：叔叔結(jié)點不存在或為黑結(jié)點，并且插入結(jié)點的父親結(jié)點是祖父結(jié)點的左子結(jié)點

單純從插入前來看，也即不算情景4.1自底向上處理時的情況，叔叔結(jié)點非紅即為葉子結(jié)點(Nil)。因為如果叔叔結(jié)點為黑結(jié)點，而父結(jié)點為紅結(jié)點，那么叔叔結(jié)點所在的子樹的黑色結(jié)點就比父結(jié)點所在子樹的多了，這不滿足紅黑樹的性質(zhì)5。后續(xù)情景同樣如此，不再多做說明了。

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

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

處理：

• 將P設(shè)為黑色

• 將PP設(shè)為紅色

• 對PP進行右旋

圖11 插入情景4.2.1

由圖11可得，左邊兩個紅結(jié)點，右邊不存在，那么一邊一個剛剛好，并且因為為紅色，肯定不會破壞樹的平衡。

咦，可以把PP設(shè)為紅色，I和P設(shè)為黑色嗎？答案是可以！看過《算法：第4版》的同學(xué)可能知道，書中講解的就是把PP設(shè)為紅色，I和P設(shè)為黑色。但把PP設(shè)為紅色，顯然又會出現(xiàn)情景4.1的情況，需要自底向上處理，做多了無謂的操作，既然能自己消化就不要麻煩祖輩們啦～

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

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

處理：

• 對P進行左旋

• 把P設(shè)置為插入結(jié)點，得到情景4.2.1

• 進行情景4.2.1的處理

圖12 插入情景4.2.2

插入情景4.3：叔叔結(jié)點不存在或為黑結(jié)點，并且插入結(jié)點的父親結(jié)點是祖父結(jié)點的右子結(jié)點

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

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

處理：

• 將P設(shè)為黑色

• 將PP設(shè)為紅色

• 對PP進行左旋

圖13 插入情景4.3.1

插入情景4.3.2：插入結(jié)點是其父結(jié)點的右子結(jié)點
處理：

• 對P進行右旋

• 把P設(shè)置為插入結(jié)點，得到情景4.3.1

• 進行情景4.3.1的處理

圖14 插入情景4.3.2

好了，講完插入的所有情景了?？赡苡滞瑢W(xué)會想：上面的情景舉例的都是第一次插入而不包含自底向上處理的情況，那么上面所說的情景都適合自底向上的情況嗎？答案是肯定的。理由很簡單，但每棵子樹都能自平衡，那么整棵樹最終總是平衡的。好吧，在出個習(xí)題，請大家拿出筆和紙畫下試試（請務(wù)必動手畫下，加深印象）：

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

圖15 習(xí)題1

紅黑樹刪除

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

紅黑樹的刪除操作也包括兩部分工作：一查找目標(biāo)結(jié)點；而刪除后自平衡。查找目標(biāo)結(jié)點顯然可以復(fù)用查找操作，當(dāng)不存在目標(biāo)結(jié)點時，忽略本次操作；當(dāng)存在目標(biāo)結(jié)點時，刪除后就得做自平衡處理了。刪除了結(jié)點后我們還需要找結(jié)點來替代刪除結(jié)點的位置，不然子樹跟父輩結(jié)點斷開了，除非刪除結(jié)點剛好沒子結(jié)點，那么就不需要替代。

二叉樹刪除結(jié)點找替代結(jié)點有3種情情景：

• 情景1：若刪除結(jié)點無子結(jié)點，直接刪除

• 情景2：若刪除結(jié)點只有一個子結(jié)點，用子結(jié)點替換刪除結(jié)點

• 情景3：若刪除結(jié)點有兩個子結(jié)點，用后繼結(jié)點（大于刪除結(jié)點的最小結(jié)點）替換刪除結(jié)點

補充說明下，情景3的后繼結(jié)點是大于刪除結(jié)點的最小結(jié)點，也是刪除結(jié)點的右子樹種最右結(jié)點。那么可以拿前繼結(jié)點（刪除結(jié)點的左子樹最左結(jié)點）替代嗎？可以的。但習(xí)慣上大多都是拿后繼結(jié)點來替代，后文的講解也是用后繼結(jié)點來替代。另外告訴大家一種找前繼和后繼結(jié)點的直觀的方法（不知為何沒人提過，大家都知道？）：把二叉樹所有結(jié)點投射在X軸上，所有結(jié)點都是從左到右排好序的，所有目標(biāo)結(jié)點的前后結(jié)點就是對應(yīng)前繼和后繼結(jié)點。如圖16所示。

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

接下來，講一個重要的思路：刪除結(jié)點被替代后，在不考慮結(jié)點的鍵值的情況下，對于樹來說，可以認為刪除的是替代結(jié)點！話很蒼白，我們看圖17。在不看鍵值對的情況下，圖17的紅黑樹最終結(jié)果是刪除了Q所在位置的結(jié)點！這種思路非常重要，大大簡化了后文講解紅黑樹刪除的情景！

圖17 刪除結(jié)點換位思路

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

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

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

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

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

綜上所述，刪除操作刪除的結(jié)點可以看作刪除替代結(jié)點，而替代結(jié)點最后總是在樹末。有了這結(jié)論，我們討論的刪除紅黑樹的情景就少了很多，因為我們只考慮刪除樹末結(jié)點的情景了。

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

圖19 紅黑樹刪除情景

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

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

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

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

萬事具備，我們進入最后的也是最難的講解。

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

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

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

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

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

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

處理：

• 將S設(shè)為黑色

• 將P設(shè)為紅色

• 對P進行左旋，得到情景2.1.2.3

• 進行情景2.1.2.3的處理

圖21 刪除情景2.1.1

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

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

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

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

處理：

• 將S的顏色設(shè)為P的顏色

• 將P設(shè)為黑色

• 將SR設(shè)為黑色

• 對P進行左旋

圖22 刪除情景2.1.2.1

平衡后的圖怎么不滿足紅黑樹的性質(zhì)？前文提醒過，R是即將替換的，它還參與樹的自平衡，平衡后再替換到刪除結(jié)點的位置，所以R最終可以看作是刪除的。另外圖2.1.2.1是考慮到第一次替換和自底向上處理的情況，如果只考慮第一次替換的情況，根據(jù)紅黑樹性質(zhì)，SL肯定是紅色或為Nil，所以最終結(jié)果樹是平衡的。如果是自底向上處理的情況，同樣，每棵子樹都保持平衡狀態(tài)，最終整棵樹肯定是平衡的。后續(xù)的情景同理，不做過多說明了。

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

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

處理：

• 將S設(shè)為紅色

• 將SL設(shè)為黑色

• 對S進行右旋，得到情景2.1.2.1

• 進行情景2.1.2.1的處理

圖23 刪除情景2.1.2.2

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

好了，此次兄弟子樹都沒紅結(jié)點“借”了，兄弟幫忙不了，找父母唄，這種情景我們把兄弟結(jié)點設(shè)為紅色，再把父結(jié)點當(dāng)作替代結(jié)點，自底向上處理，去找父結(jié)點的兄弟結(jié)點去“借”。但為什么需要把兄弟結(jié)點設(shè)為紅色呢？顯然是為了在P所在的子樹中保證平衡（R即將刪除，少了一個黑色結(jié)點，子樹也需要少一個），后續(xù)的平衡工作交給父輩們考慮了，還是那句，當(dāng)每棵子樹都保持平衡時，最終整棵總是平衡的。

處理：

• 將S設(shè)為紅色

• 把P作為新的替換結(jié)點

• 重新進行刪除結(jié)點情景處理

圖24 情景2.1.2.3

刪除情景2.2：替換結(jié)點是其父結(jié)點的右子結(jié)點

好啦，右邊的操作也是方向相反，不做過多說明了，相信理解了刪除情景2.1后，肯定可以理解2.2。

刪除情景2.2.1：替換結(jié)點的兄弟結(jié)點是紅結(jié)點

處理：

• 將S設(shè)為黑色

• 將P設(shè)為紅色

• 對P進行右旋，得到情景2.2.2.3

• 進行情景2.2.2.3的處理

圖25 刪除情景2.2.1

刪除情景2.2.2：替換結(jié)點的兄弟結(jié)點是黑結(jié)點

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

處理：

• 將S的顏色設(shè)為P的顏色

• 將P設(shè)為黑色

• 將SL設(shè)為黑色

• 對P進行右旋

圖26 刪除情景2.2.2.1

刪除情景2.2.2.2：替換結(jié)點的兄弟結(jié)點的左子結(jié)點為黑結(jié)點，右子結(jié)點為紅結(jié)點

處理：

• 將S設(shè)為紅色

• 將SR設(shè)為黑色

• 對S進行左旋，得到情景2.2.2.1

• 進行情景2.2.2.1的處理

圖27 刪除情景2.2.2.2

刪除情景2.2.2.3：替換結(jié)點的兄弟結(jié)點的子結(jié)點都為黑結(jié)點

處理：

• 將S設(shè)為紅色

• 把P作為新的替換結(jié)點

• 重新進行刪除結(jié)點情景處理

圖28 刪除情景2.2.2.3

綜上，紅黑樹刪除后自平衡的處理可以總結(jié)為：

1. 自己能搞定的自消化（情景1）

2. 自己不能搞定的叫兄弟幫忙（除了情景1、情景2.1.2.3和情景2.2.2.3）

3. 兄弟都幫忙不了的，通過父母，找遠方親戚（情景2.1.2.3和情景2.2.2.3）

哈哈，是不是跟現(xiàn)實中很像，當(dāng)我們有困難時，首先先自己解決，自己無力了總兄弟姐妹幫忙，如果連兄弟姐妹都幫不上，再去找遠方的親戚了。這里記憶應(yīng)該會好記點～

最后再做個習(xí)題加深理解（請不熟悉的同學(xué)務(wù)必動手畫下）：

習(xí)題2：請畫出圖29的刪除自平衡處理過程。

當(dāng)前名稱：這30張圖帶你讀懂紅黑樹-創(chuàng)新互聯(lián)
標(biāo)題網(wǎng)址：http://jinyejixie.com/article2/dpccic.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供做網(wǎng)站、網(wǎng)站改版、域名注冊、品牌網(wǎng)站建設(shè)、Google、營銷型網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)