30張圖帶你徹底了解紅黑樹 侵删

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

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

二叉查找樹

完美平衡二叉樹

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

紅黑樹也是二叉查找樹，我們知道，二叉查找樹這一資料結構并不難，而紅黑樹之是以難是難在它是自平衡的二叉查找樹，在進行插入和删除等可能會破壞樹的平衡的操作時，需要重新自處理達到平衡狀态。現在在腦海想下怎麼實作？是不是太多情景需要考慮了？啧啧，先别急，通過本文的學習後，你會覺得，其實也不過如此而已。好吧，我們先來看下紅黑樹的定義和一些基本性質。

紅黑樹定義和性質

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

• 性質1：每個節點要麼是黑色，要麼是紅色。
• 性質2：根節點是黑色。
• 性質3：每個葉子節點（NIL）是黑色。
• 性質4：每個紅色結點的兩個子結點一定都是黑色。
• 性質5：任意一結點到每個葉子結點的路徑都包含數量相同的黑結點。

從性質5又可以推出：

• 性質5.1：如果一個結點存在黑子結點，那麼該結點肯定有兩個子結點

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

圖1 一顆簡單的紅黑樹

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

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

圖2 結點叫法約定

我們把正在處理(周遊)的結點叫做目前結點，如圖2中的D，它的父親叫做父結點，它的父親的另外一個子結點叫做兄弟結點，父親的父親叫做祖父結點。

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

• 左旋：以某個結點作為支點(旋轉結點)，其右子結點變為旋轉結點的父結點，右子結點的左子結點變為旋轉結點的右子結點，左子結點保持不變。如圖3。
• 右旋：以某個結點作為支點(旋轉結點)，其左子結點變為旋轉結點的父結點，左子結點的右子結點變為旋轉結點的左子結點，右子結點保持不變。如圖4。
• 變色：結點的顔色由紅變黑或由黑變紅。

圖3 左旋

圖4 右旋

上面所說的旋轉結點也即旋轉的支點，圖4和圖5中的P結點。

我們先忽略顔色，可以看到旋轉操作不會影響旋轉結點的父結點，父結點以上的結構還是保持不變的。

左旋隻影響旋轉結點和其右子樹的結構，把右子樹的結點往左子樹挪了。

右旋隻影響旋轉結點和其左子樹的結構，把左子樹的結點往右子樹挪了。

是以旋轉操作是局部的。另外可以看出旋轉能保持紅黑樹平衡的一些端詳了：當一邊子樹的結點少了，那麼向另外一邊子樹“借”一些結點；當一邊子樹的結點多了，那麼向另外一邊子樹“租”一些結點。

但要保持紅黑樹的性質，結點不能亂挪，還得靠變色了。怎麼變？具體情景又不同變法，後面會具體講到，現在隻需要記住紅黑樹總是通過旋轉和變色達到自平衡。

balabala了這麼多，相信你對紅黑樹有一定印象了，那麼現在來考考你：

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

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

紅黑樹查找

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

1. 從根結點開始查找，把根結點設定為目前結點；
2. 若目前結點為空，傳回null；
3. 若目前結點不為空，用目前結點的key跟查找key作比較；
4. 若目前結點key等于查找key，那麼該key就是查找目标，傳回目前結點；
5. 若目前結點key大于查找key，把目前結點的左子結點設定為目前結點，重複步驟2；
6. 若目前結點key小于查找key，把目前結點的右子結點設定為目前結點，重複步驟2；

如圖5所示：

 圖5 二叉樹查找流程圖

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

紅黑樹插入

插入操作包括兩部分工作：一查找插入的位置；二插入後自平衡。查找插入的父結點很簡單，跟查找操作差別不大：

1. 從根結點開始查找；
2. 若根結點為空，那麼插入結點作為根結點，結束。
3. 若根結點不為空，那麼把根結點作為目前結點；
4. 若目前結點為null，傳回目前結點的父結點，結束。
5. 若目前結點key等于查找key，那麼該key所在結點就是插入結點，更新結點的值，結束。
6. 若目前結點key大于查找key，把目前結點的左子結點設定為目前結點，重複步驟4；
7. 若目前結點key小于查找key，把目前結點的右子結點設定為目前結點，重複步驟4；

如圖6所示：

圖6 紅黑樹插入位置查找

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

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

圖7 紅黑樹插入情景

嗯，插入情景很多呢，8種插入情景！但情景1、2和3的處理很簡單，而情景4.2和情景4.3隻是方向反轉而已，懂得了一種情景就能推出另外一種情景，是以總體來看，并不複雜，後續我們将一個一個情景來看，把它徹底搞懂。

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

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

圖8 插入操作結點的叫法約定

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

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

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

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

處理：把插入結點作為根結點，并把結點設定為黑色。

插入情景2：插入結點的Key已存在

插入結點的Key已存在，既然紅黑樹總保持平衡，在插入前紅黑樹已經是平衡的，那麼把插入結點設定為将要替代結點的顔色，再把結點的值更新就完成插入。

處理：

• 把I設為目前結點的顔色
• 更新目前結點的值為插入結點的值

插入情景3：插入結點的父結點為黑結點

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

處理：直接插入。

插入情景4：插入結點的父結點為紅結點

再次回想下紅黑樹的性質2：根結點是黑色。如果插入的父結點為紅結點，那麼該父結點不可能為根結點，是以插入結點總是存在祖父結點。這點很重要，因為後續的旋轉操作肯定需要祖父結點的參與。

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

插入情景4.1：叔叔結點存在并且為紅結點

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

處理：

• 将P和S設定為黑色
• 将PP設定為紅色
• 把PP設定為目前插入結點

圖9 插入情景4.1_1

圖10 插入情景4.1_2

可以看到，我們把PP結點設為紅色了，如果PP的父結點是黑色，那麼無需再做任何處理；但如果PP的父結點是紅色，根據性質4，此時紅黑樹已不平衡了，是以還需要把PP當作新的插入結點，繼續做插入操作自平衡處理，直到平衡為止。

試想下PP剛好為根結點時，那麼根據性質2，我們必須把PP重新設為黑色，那麼樹的紅黑結構變為：黑黑紅。換句話說，從根結點到葉子結點的路徑中，黑色結點增加了。這也是唯一一種會增加紅黑樹黑色結點層數的插入情景。

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

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

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

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

插入情景4.2.1：插入結點是其父結點的左子結點

處理：

• 将P設為黑色
• 将PP設為紅色
• 對PP進行右旋

圖11 插入情景4.2.1

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

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

插入情景4.2.2：插入結點是其父結點的右子結點

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

處理：

• 對P進行左旋
• 把P設定為插入結點，得到情景4.2.1
• 進行情景4.2.1的處理

圖12 插入情景4.2.2

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

該情景對應情景4.2，隻是方向反轉，不做過多說明了，直接看圖。

插入情景4.3.1：插入結點是其父結點的右子結點

處理：

• 将P設為黑色
• 将PP設為紅色
• 對PP進行左旋

圖13 插入情景4.3.1

插入情景4.3.2：插入結點是其父結點的右子結點

處理：

• 對P進行右旋
• 把P設定為插入結點，得到情景4.3.1
• 進行情景4.3.1的處理

圖14 插入情景4.3.2

好了，講完插入的所有情景了。可能又同學會想：上面的情景舉例的都是第一次插入而不包含自底向上處理的情況，那麼上面所說的情景都适合自底向上的情況嗎？答案是肯定的。理由很簡單，但每棵子樹都能自平衡，那麼整棵樹最終總是平衡的。好吧，在出個習題，請大家拿出筆和紙畫下試試（請務必動手畫下，加深印象）：

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

圖15 習題1

紅黑樹删除

紅黑樹插入已經夠複雜了，但删除更複雜，也是紅黑樹最複雜的操作了。但穩住，勝利的曙光就在前面了！

紅黑樹的删除操作也包括兩部分工作：一查找目标結點；而删除後自平衡。查找目标結點顯然可以複用查找操作，當不存在目标結點時，忽略本次操作；當存在目标結點時，删除後就得做自平衡處理了。删除了結點後我們還需要找結點來替代删除結點的位置，不然子樹跟父輩結點斷開了，除非删除結點剛好沒子結點，那麼就不需要替代。

二叉樹删除結點找替代結點有3種情情景：

• 情景1：若删除結點無子結點，直接删除
• 情景2：若删除結點隻有一個子結點，用子結點替換删除結點
• 情景3：若删除結點有兩個子結點，用後繼結點（大于删除結點的最小結點）替換删除結點

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

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

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

圖17 删除結點換位思路

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

• 情景2：删除結點用其唯一的子結點替換，子結點替換為删除結點後，可以認為删除的是子結點，若子結點又有兩個子結點，那麼相當于轉換為情景3，一直自頂向下轉換，總是能轉換為情景1。（對于紅黑樹來說，根據性質5.1，隻存在一個子結點的結點肯定在樹末了）
• 情景3：删除結點用後繼結點（肯定不存在左結點），如果後繼結點有右子結點，那麼相當于轉換為情景2，否則轉為為情景1。

二叉樹删除結點情景關系圖如圖18所示。

圖18 二叉樹删除情景轉換

綜上所述，删除操作删除的結點可以看作删除替代結點，而替代結點最後總是在樹末。有了這結論，我們讨論的删除紅黑樹的情景就少了很多，因為我們隻考慮删除樹末結點的情景了。

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

圖19 紅黑樹删除情景

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

圖20 删除操作結點的叫法約定

圖20的字母并不代表結點Key的大小。R表示替代結點，P表示替代結點的父結點，S表示替代結點的兄弟結點，SL表示兄弟結點的左子結點，SR表示兄弟結點的右子結點。灰色結點表示它可以是紅色也可以是黑色。

值得特别提醒的是，R是即将被替換到删除結點的位置的替代結點，在删除前，它還在原來所在位置參與樹的子平衡，平衡後再替換到删除結點的位置，才算删除完成。

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

删除情景1：替換結點是紅色結點

我們把替換結點換到了删除結點的位置時，由于替換結點時紅色，删除也了不會影響紅黑樹的平衡，隻要把替換結點的顔色設為删除的結點的顔色即可重新平衡。

處理：顔色變為删除結點的顔色

删除情景2：替換結點是黑結點

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

删除情景2.1：替換結點是其父結點的左子結點

删除情景2.1.1：替換結點的兄弟結點是紅結點

若兄弟結點是紅結點，那麼根據性質4，兄弟結點的父結點和子結點肯定為黑色，不會有其他子情景，我們按圖21處理，得到删除情景2.1.2.3（後續講解，這裡先記住，此時R仍然是替代結點，它的新的兄弟結點SL和兄弟結點的子結點都是黑色）。

處理：

• 将S設為黑色
• 将P設為紅色
• 對P進行左旋，得到情景2.1.2.3
• 進行情景2.1.2.3的處理

圖21 删除情景2.1.1

删除情景2.1.2：替換結點的兄弟結點是黑結點

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

删除情景2.1.2.1：替換結點的兄弟結點的右子結點是紅結點，左子結點任意顔色

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

處理：

• 将S的顔色設為P的顔色
• 将P設為黑色
• 将SR設為黑色
• 對P進行左旋

圖22 删除情景2.1.2.1

平衡後的圖怎麼不滿足紅黑樹的性質？前文提醒過，R是即将替換的，它還參與樹的自平衡，平衡後再替換到删除結點的位置，是以R最終可以看作是删除的。另外圖2.1.2.1是考慮到第一次替換和自底向上處理的情況，如果隻考慮第一次替換的情況，根據紅黑樹性質，SL肯定是紅色或為Nil，是以最終結果樹是平衡的。如果是自底向上處理的情況，同樣，每棵子樹都保持平衡狀态，最終整棵樹肯定是平衡的。後續的情景同理，不做過多說明了。

删除情景2.1.2.2：替換結點的兄弟結點的右子結點為黑結點，左子結點為紅結點

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

處理：

• 将S設為紅色
• 将SL設為黑色
• 對S進行右旋，得到情景2.1.2.1
• 進行情景2.1.2.1的處理

圖23 删除情景2.1.2.2

删除情景2.1.2.3：替換結點的兄弟結點的子結點都為黑結點

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

處理：

• 将S設為紅色
• 把P作為新的替換結點
• 重新進行删除結點情景處理

圖24 情景2.1.2.3

删除情景2.2：替換結點是其父結點的右子結點

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

删除情景2.2.1：替換結點的兄弟結點是紅結點

處理：

• 将S設為黑色
• 将P設為紅色
• 對P進行右旋，得到情景2.2.2.3
• 進行情景2.2.2.3的處理

圖25 删除情景2.2.1

删除情景2.2.2：替換結點的兄弟結點是黑結點

删除情景2.2.2.1：替換結點的兄弟結點的左子結點是紅結點，右子結點任意顔色

處理：

• 将S的顔色設為P的顔色
• 将P設為黑色
• 将SL設為黑色
• 對P進行右旋

圖26 删除情景2.2.2.1

删除情景2.2.2.2：替換結點的兄弟結點的左子結點為黑結點，右子結點為紅結點

處理：

• 将S設為紅色
• 将SR設為黑色
• 對S進行左旋，得到情景2.2.2.1
• 進行情景2.2.2.1的處理

圖27 删除情景2.2.2.2

删除情景2.2.2.3：替換結點的兄弟結點的子結點都為黑結點

處理：

• 将S設為紅色
• 把P作為新的替換結點
• 重新進行删除結點情景處理

圖28 删除情景2.2.2.3

綜上，紅黑樹删除後自平衡的處理可以總結為：

1. 自己能搞定的自消化（情景1）
2. 自己不能搞定的叫兄弟幫忙（除了情景1、情景2.1.2.3和情景2.2.2.3）
3. 兄弟都幫忙不了的，通過父母，找遠方親戚（情景2.1.2.3和情景2.2.2.3）

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

最後再做個習題加深了解（請不熟悉的同學務必動手畫下）：

習題2：請畫出圖29的删除自平衡處理過程。

寫在後面

耗時良久，終于寫完了～自己加深了紅黑樹的了解的同時，也希望能幫助大家。如果你之前沒學習過紅黑樹，看完這篇文章後可能還存在很多疑問，如果有疑問可以在評論區寫出來，我會盡自己所能解答。另外給大家推薦一個支援紅黑樹線上生成的網站，來做各種情景梳理很有幫助：

線上生成紅黑樹

https://sandbox.runjs.cn/show/2nngvn8w

（删除操作那個把替代結點看作删除結點思路就是我自己在用這個網站時自己頓悟的，我覺得這樣講解更容易了解。）

少了代碼是不是覺得有點空虛？哈哈，後續我會寫關于Java和HashMap和TreeMap的文章，裡面都有紅黑樹相關的知識。相信看了這篇文章後，再去看Java和HashMap和TreeMap的源碼絕對沒難度！

最後來看下思考題和習題的答案吧。

思考題和習題答案

思考題1：黑結點可以同時包含一個紅子結點和一個黑子結點嗎？

答：可以。如下圖的F結點：

習題1：請畫出圖15的插入自平衡處理過程。

習題2：請畫出圖29的删除自平衡處理過程。

（完）