紅黑樹的理解與Java實現

轉自：xyk_1021，

https://blog.csdn.net/weixin_42786274/article/details/86557922

前言

 

前段時間在研究 JDK1.8 的 hashmap 原始碼，看到 put 方法的插入環節，遇到了紅黑樹，不得不停止閱讀原始碼的過程，因為還沒掌握紅黑樹是無法完全讀透 hashmap 原始碼的。紅黑樹作為一種資料結構，它被應用得非常多，可能很多人不認識它，但其實它已經在默默為我們的程式碼在發光發熱。例如，你只要在 Java 中用到 map，基本上就是在用紅黑樹（當元素個數到達八個時連結串列轉紅黑樹）。

PS：在看這篇文章前，必須先瞭解普通的二叉查詢樹和平衡查詢樹（AVL）樹、2-3-4樹。不然看起來會非常吃力。

 

紅黑樹的性質

紅黑樹是一種自平衡樹，它也是一顆二叉樹。既然能保持平衡，說明它和 AVL 樹類似，在插入或者刪除時肯定有調整的過程，只不過這個調整過程並不像 AVL 樹那樣繁瑣。為何紅黑樹使用得比 AVL 樹更多，就是因為紅黑樹它的調整過程迅速且簡介。紅黑樹有以下五個特性：

 

• 性質1：節點是紅色或黑色
• 性質2：根是黑色
• 性質3：所有葉子都是黑色。葉子是 NIL 節點，也就是 Null 節點
• 性質4：如果一個節點是紅的，則它的兩個兒子都是黑的
• 性質5：從任一節點到其葉子的所有簡單路徑都包含相同數目的黑色節點。

 

下圖展示了一棵紅黑樹。

 

 

分析：

註意理解上，葉子並不等價於黑色節點，但是他們的顏色都是黑色。

為何要給節點指定紅或者黑的顏色？

 

作者這種設計，只是為了從程式設計上達到一種便利的效果。另外可以讓它們在插入時達到近似的平衡，並不像 AVL 樹那樣絕對平衡。實際上，紅黑樹是2-3樹的一種變體，某種情況下，它又相當於2-3-4樹。因為2-3樹在程式設計上需要比較多的程式碼量，所以誕生了紅黑樹這種巧妙的設計。透過加了顏色來區分結點，這樣程式設計上就可以當成二叉樹來寫程式，不用分別用三個指標表示左、中、右孩子了。

看一下紅黑樹和2-3樹的等價性聯絡

 

 

從上面可以看到，把紅色節點放到與父親齊平，就是2-3樹中的一個2-3節點。

 

紅黑樹的操作

 

資料結構的性質看完之後，就要掌握它到底會存在哪種操作？例如 hashmap，它最常見的操作就是 get 和 put、擴容。同理，紅黑樹也有它的基本操作。因為它本身上也是一棵二叉查詢樹，所以重點關註的操作無非就是查詢、插入、刪除。

 

1. 查詢操作

 

紅黑樹的查詢方式很簡單，只要是樹，查詢的過程無非就是一個遞迴過程。如果查詢的元素小於當前節點，那麼查詢其左子樹；如果查詢的元素大於當前元素，則查詢其右子樹。

 

2. 插入操作

 

插入操作首先需要透過查詢操作找到合適的插入點，然後插入新節點。如果在插入節點後，發生了違背紅黑樹特性的情況時，需要對紅黑樹進行旋轉染色等操作，使其重新滿足特性。

 

2.1 插入新節點

為了在插入新節點時盡可能少的違反紅黑樹特性且更容易調整紅黑樹，就先將新節點染成紅色。這樣就只可能會違反特性4。如果這裡沒有違反特性4，那麼就不需要對紅黑樹進行調整，插入操作完成。

2.2 調整子樹

那麼，在違反了特性4的時候，新節點的父節點為紅色節點。根據特性2可知，父節點不是根節點，則新節點必有祖父節點。又根據特性3可推論出紅色節點必有兩個黑色子節點（空節點為黑色）。此時會出現兩種情況：叔節點為紅色、叔節點為黑色。

 

圖例：C 表示當前節點，P 表示父節點，U 表示叔節點，G 表示祖父節點

（1）父節點與叔節點都為紅色的情況

在這種情況下，需要將父節點和叔節點變為黑色，再將祖父節點變為紅色。這樣，圖上所展示的子樹就滿足了紅黑樹的特性。如下圖所示。

 

但是這裡又可能會產生新的違反特性情況，因為祖父節點變成了紅色，那麼它可能會造成違反特性4的情況。所以，這裡就將祖父節點作為當前節點，進行新一輪的調整操作。

（2）父節點為紅色，叔節點為黑色的情況

 

在這種情況下，對其調整的核心就是保持父節點分支符合特性4，而叔節點分支保持符合特性5。

 

• 第一步，旋轉。對祖父節點進行左旋或者右旋。如果父節點是祖父節點的右子節點，那麼對祖父節點進行左旋；否則，對祖父節點進行右旋。
• 第二步，染色。將祖父節點染為紅色，而父節點染為黑色。

進過這兩步，上圖的情況會轉換為下圖所示。

可以看出，父節點這一分支進過調整後，當前節點與父節點的顏色不再是連續紅色，滿足特性4。而叔節點這一分支的黑色節點數目沒有發生變化，滿足特性5。對原祖父節點的父節點來說，該子樹沒有發生違反特性的變化。該子樹調整完成。

2.3 檢查根節點

當上述調整執行完後，還有最後一步，就是檢查是否滿足特性2。這一步只需要將根節點染成黑色就可以，無需再多加判斷。

 

3. 刪除操作

需要重點理解的就是刪除操作，這個也是我覺得是紅黑樹中最難的部分。

刪除操作要比插入操作略微複雜一些。因為刪除的節點可能是出現在樹的中間層的節點，此時刪除該節點會遇到很複雜的情況。所以，在刪除節點的時候，需要先對紅黑樹進行一些調整，使得刪除節點對整個樹的影響降到最低。

3.1 替換刪除節點

首先根據 BST 刪除節點的規則，使用當前節點左子樹的最大值節點或者右子樹的最小值節點代替其刪除。這兩個節點是其子樹中數值上最貼近當前節點數值的節點）。 這一點，只要懂了二叉查詢樹的刪除操作就明白了，在這裡不多說了。如下圖所示：

圖例：D 表示當前節點，P 表示父節點，B 表示兄弟節點，BR 表示兄弟節點的右子節點，BL 表示兄弟節點的左子節點

既然待刪除節點是要被移走的，那肯定有一個節點要替換到它的位置上去。如何找到這個替換節點，這個過程和二叉查詢樹一模一樣，要麼在它的左子樹下一直往右找到最大節點，要麼在右子樹下找到最小節點。

 

下麵的描述過程採用的是右子樹的最小值節點代替

當找到替換節點之後，現在需要考慮的情況就減少了，只可能會出現以下幾種情況（因為需要滿足紅黑樹特性）：

1. 無子節點，節點為紅色
2. 無子節點，節點為黑色
3. 只有右子節點，右子節點為紅色，節點本身為黑色

上面這三種情況，說的是新待刪除節點。新待刪除節點，就是即將被替換到待刪除位置的節點。

 

因為 D 節點就是即將要替換到待刪節點位置的節點，它同時又是右子樹的最小值，既然是最小值了，它就不再可能擁有左子樹了，所以只有可能有右子節點。另外，假如它有右節點且右節點的顏色是黑色，它自身顏色是紅色，根本不成立。因為假如它自身為紅色且又有黑孩子，那它必須要有兩個黑孩子才滿足紅黑樹性質，所以不滿足。 那有沒有可能，它自身是黑色且右孩子也為黑色呢？也不可能！因為它左孩子已經為空了，說明它從自身出發到左子樹的葉子的距離就是1，假如它右孩子也為黑色，那它從自身出發到右子樹葉子的距離肯定大於等於2了，明顯不可能。

所以總的來說只可能有下麵三種情況：

 

• 情況1：只需要直接刪除節點就可以。刪了一個紅色新待刪節點，不會影響紅黑樹性質。
• 情況2：刪除該 D 節點後，違反了紅黑樹特性5，需要調整（不考慮待刪除節點為根節點的情況）
• 情況3：用右子節點 R 佔據待刪除節點 D，再將其染成黑色即可，不違反紅黑樹特性。因為左邊本來就是空了，其實右子樹下即使有多少個黑色節點，也不會影響整體特性。

在這三種情況中，情況1和情況3比較簡單，不需要多餘的調整。情況2則需要後續的調整步驟使其滿足紅黑樹特性。

 

3.2 調整紅黑樹

上述情況2的調整比較複雜。下麵對各種情況進行講解。

根據紅黑樹的特性5，待刪除節點必然有兄弟節點。

 

為什麼這麼說呢？因為我們已經假設上面的 D 節點不為根了，那說明它肯定有父親。首先它是沒有孩子的，它下麵直接就是葉子了，既然有父親，不論它是父親的左孩子或者右孩子，從父親出發到它自身，黑色節點的個數為1。反證法：假如父親只有它一個孩子，那說明父親到另一邊子樹的葉子距離就為0，因為0個節點。這明顯不符合，所以說明父親肯定有兩個孩子，那從而得知待刪節點D必有兄弟。

下麵根據其兄弟節點所在分支的不同，來分情況討論。

以下是以關註待刪節點為父節點的左子節點進行描述，如果遇到關註節點為父節點的右子節點的情況，則映象處理。

思路：下麵的任何調整隻有一個目的，就是不斷調整，直到調整到可以直接將 D 移除又不會影響紅黑樹特性的情況。但關鍵是調整過程中紅黑樹特性也不會發生改變。

 

圖例：D 表示當前節點，P 表示父節點，B 表示兄弟節點，BR 表示兄弟節點的右子節點，BL 表示兄弟節點的左子節點

 

（1）兄弟節點為紅色

 

將父節點染成紅色，兄弟節點染成黑色，然後對父節點進行左旋操作。此時就轉換為了下麵的（4），之後按照（4）繼續進行調整。

分析：這種情況，樹的整體高度為2，變色左旋之後，整體高度還是保持在2。

 

（2）兄弟節點為黑色，遠侄節點為紅色

 

這種情況下，不需要考慮父節點的顏色。

 

1. 將父節點 P 與兄弟節點 B 的顏色互換 ，這個過程父親染黑
2. 將兄弟節點的右子節點 BR 染成黑色
3. 對父節點 P 進行左旋操作

可以看到，原本高度就是符合紅黑樹特性的，左右子樹的高度都為1，因為黑色節點只有一個。經過這三步的調整後，直接刪除節點 D 後仍然滿足紅黑樹的特性，調整完成，跳出演演算法迴圈。

 

（3）兄弟節點為黑色，遠侄節點為黑色，近侄節點為紅色

 

這種情況下，兄弟節點的左節點染成黑色。兄弟節點染紅。然後對兄弟節點做右旋。此時的狀況就和（2）一樣了。之後就透過（2）的調整方式進行調整。

 

（4）父節點為紅色，兄弟節點為黑色，兄弟節點無子節點

 

這種情況下，將父節點P染成黑色，再將兄弟節點染成紅色。經過這樣的操作後，除去節點D後，以P為根節點的子樹的黑節點深度並沒有發生變化。調整完成。

怎麼理解這個操作？

 

可以看左邊，沒調整前，P 的左右子樹的黑色結點的數目都是1，是相同的，符合紅黑樹的性質：從任一節點到其葉子的所有簡單路徑都包含相同數目的黑色節點。然後再看右邊，調整後，刪掉 D 之後，P 結點的左右子樹的黑色結點都是0個，仍然滿足性質，所以調整完成。

（5）父節點為黑色，兄弟節點為黑色，兄弟節點無子節點

這種情況下，為了在刪除節點 D 後使以 P 為根節點的子樹能滿足紅黑樹特性5，將兄弟節點 B 染成紅色。但是這樣操作後，以 P 為根節點的子樹的黑色節點深度變小了。所以需要繼續調整。

因為P節點子樹的黑色深度發生了減少，可以把其當作待刪除節點，那麼此時就以 P 節點為關註節點進行進一步調整（繼續向上調整）。 這句話的意思我們再以 P 為起始點，繼續根據情況進行平衡操作。就是把 P 當成 D，只是不要再刪除 P 了。再看是這五種中的哪種情況，再進行對應的調整，這樣一直向上，直到新的起始點為根節點或者關註節點不為黑色。

第五種情況，不會一直連續回溯的。假如能一直回溯，指標向上走之後，兄弟節點會一直都沒有右孩子嗎？不存在的。假如有這種情況，說明樹的路徑長度已經嚴重往左傾斜，肯定不可能。所以回溯這個情況只會回溯一次，不會連續回溯。第五個這種情況出現之後，下一次進入演演算法迴圈，肯定就是進入其他情況，直到遇到 break，跳出迴圈，終止整個演演算法過程。

3.3 檢查根節點及刪除節點

經過上述的調整後，此時基本滿足了紅黑樹的特性。但是存在根節點變成紅色的情況。所以需要將根節點染成黑色的操作。 最後，執行刪除操作，將待刪除節點刪掉。

 

當然從程式設計的角度，你也可以調整指標先把待刪除節點移掉，然後再開始平衡調整過程。註意這裡說的平衡調整，並不是 AVL 樹的絕對平衡調整，而是滿足紅黑樹特性的平衡調整。紅黑樹的平衡和 AVL 的平衡是有區別的。

Java實現

上面的操作篇幅比較長，假如沒看明白，可以透過下麵的程式碼繼續看。

 

由於篇幅限制，原始碼請到原文連結檢視 Java 實現

https://blog.csdn.net/weixin_42786274/article/details/86557922 

總結

紅黑樹的刪除操作是整個紅黑樹中最複雜的一部分，理解了這部分，紅黑樹就算基本拿下了。理解完一種資料結構，要能 get 到作者當初設計時的點，才算是一次積累。紅黑樹的刪除操作，它非常地巧妙，整一個演演算法迴圈過程，它不會超過三次，調整過程基本都在子樹內完成，指標不需要一直向上回溯，相比 AVL 樹，AVL 樹在刪除節點時，指標有可能會一直回溯到根為止。