?2016-2026 Matools All rights reserved,
粵ICP備17059708號
一、簡述
紅黑樹是一種特殊的二叉樹，并且是優(yōu)秀的自平衡查找樹，下圖為紅黑樹的示例：
紅黑樹具有以下幾大特性：
1、根節(jié)點為黑色。
2、所有節(jié)點都是黑色或紅色。
3、所有葉子節(jié)點（Null）都是黑色。
4、紅色節(jié)點的子節(jié)點一定是黑色的。
5、任意一個節(jié)點到其葉子節(jié)點的所有路徑上的黑色節(jié)點數(shù)量相同（黑色完美平衡二叉樹）。
以上的五大特定也是維持紅黑樹結構的基本規(guī)則，但是明白了這些規(guī)則，不代表我們就明白了紅黑樹的設計原理及規(guī)則維持算法。
在我們日常的工作中多多少少都會接觸到紅黑樹，特別是JDK1.8之后hashmap的底層采用了紅黑樹機構，接下來的博文中我們會一點點弄明白以下幾個問題，也是筆者在學習之前不明白的兩個問題：
1、紅黑樹為什么要維持自平衡、自平衡的好處是什么？
2、什么是左旋，右旋，變色？
3、什么條件下需要進行左旋、右旋、變色？
二、紅黑樹的自平衡
根據(jù)上一節(jié)紅黑樹特性第5點可以知道，紅黑樹是一顆黑色完美平衡二叉樹，紅黑樹從根節(jié)點到葉子結點的最長路徑不會超過最短路徑的2倍；
這就保證了紅黑樹優(yōu)秀的查找性能，其查找的時間復雜度為O(logn)；
當插入或刪除階段操作過程中，會破壞此平衡結構，當平衡遭到破壞，程序會進行一系列操作來重新維持平衡，這一過程就是自平衡；這一系列操作就是左旋、右旋、變色。?
1、左旋：
對當前節(jié)點進行左旋：當前節(jié)點的右子節(jié)點變?yōu)楦腹?jié)點，原右子節(jié)點的左子節(jié)點變?yōu)楫斍肮?jié)點的右子節(jié)點，如圖演示（對150節(jié)點進行左旋）：
上圖對150節(jié)點左旋：
* 把150節(jié)點的右子節(jié)點170變?yōu)槠涓腹?jié)點（170變?yōu)?50的父節(jié)點）。
* 把150節(jié)點的原右子節(jié)點170的左子節(jié)點160變?yōu)槠溆易庸?jié)點（160變?yōu)?50的右子節(jié)點）。
注意：
*
* 圖中只是示意圖，在第一步之后，170節(jié)點并沒有三個指向其他節(jié)點的指針，這里只是為了理解起來更清晰
* 圖中只是進行左旋，還沒有涉及變色問題，所以會看到父節(jié)點與子節(jié)點同色問題。
* 左旋操作涉及到的節(jié)點只是當前節(jié)點的右子節(jié)點和右子節(jié)點的左子節(jié)點兩個節(jié)點，其他節(jié)點不變。
2、右旋：
對當前節(jié)點進行右旋：當前節(jié)點的左子節(jié)點變?yōu)楦腹?jié)點，原左子節(jié)點的右子節(jié)點變?yōu)楫斍肮?jié)點的左子節(jié)點，如圖演示（對150節(jié)點進行右旋）：
上圖對150節(jié)點進行右旋：
* 把150節(jié)點的左子節(jié)點130變?yōu)槠涓腹?jié)點（130變?yōu)?50的父節(jié)點）。
* 把150節(jié)點的原左子節(jié)點130的右子節(jié)點null節(jié)點變?yōu)槠渥笞庸?jié)點（130的原右子節(jié)點null變?yōu)?50的左子節(jié)點）。
?注意：
*
* 圖中只是示意圖，在第一步之后，130節(jié)點并沒有三個指向其他節(jié)點的指針，這里只是為了理解起來更清晰
* 圖中只是進行左旋，還沒有涉及變色問題，所以會看到父節(jié)點與子節(jié)點同色問題。
* 右旋操作涉及到的節(jié)點只是當前節(jié)點的左子節(jié)點和左子節(jié)點的右子節(jié)點兩個節(jié)點，其他節(jié)點不變。
3、變色：
節(jié)點的變色：就是節(jié)點由紅色變成黑色或有黑色變成紅色。
而在實際的維持自平衡的過程中變色過程有可能是一個連鎖反應，而破壞平衡結果的操作有插入和刪除。?
三、節(jié)點的插入
紅黑樹新節(jié)點的插入有可能會破壞現(xiàn)有的平衡結構，所以就需要進行節(jié)點的變色、左旋或者右旋操作來保持紅黑樹的平衡；但插入操作的情況區(qū)分比較多，這也正是紅黑樹自平衡結構不容易理解的地方之一；
下圖就是插入的所有情況，接下來會有針對每種情況進行詳細講解：
其他3種情況非常簡單，這里詳細說明第四種情況：
C -?current?當前節(jié)點，P -?parent?父節(jié)點，PP -?祖父節(jié)點，U -?uncle?叔叔節(jié)點， O -?其他節(jié)點?
情況4、P?為紅色
4.1、P?為紅色且?U?為紅色 （如圖 4.1）
（1）將 P 設為黑色
（2）將 U 設為黑色
（3）將 PP 設為紅色
（4）將 PP 設為當前節(jié)點（這時 PP?就為 C?節(jié)點了），重復情況4判斷
?
?
4.2、P?為紅色且 U?不存在或為黑色?
4.2.1、P?是左節(jié)點，C?左節(jié)點 （P?為紅色且 U?不存在或為黑色）（如圖4.2.1）
（1）將 P 設為黑色
（2）將 PP 設為紅色
（3）對 PP?進行右旋
?
4.2.2、P?是左節(jié)點，C?右節(jié)點 （P?為紅色且 U?不存在或為黑色）（如圖4.2.2）
（1）對 P?進行左旋
（2）設 PP?為當前節(jié)點
（3）此時結構變?yōu)?4.2.1?結構，繼續(xù)進行 4.2.1 操作
?
4.2.3、P?是右節(jié)點，C?右節(jié)點?（P?為紅色且 U?不存在或為黑色）（如圖4.2.3）
（1）將 P 設為黑色
（2）將 PP 設為紅色
（3）對 PP?進行左旋
4.2.4、P?是右節(jié)點，C?左節(jié)點?（P?為紅色且 U?不存在或為黑色）（如圖4.2.4）
（1）對 P?進行右旋
（2）設 PP?為當前節(jié)點
（3）此時結構變?yōu)?4.2.3 結構，繼續(xù)進行 4.2.3 操作
?
節(jié)點插入總結：
*
*
當前節(jié)點（新插入的節(jié)點）會在旋轉變色之前就設置為紅色；為什么插入節(jié)點為紅色？因為根據(jù)紅黑樹的特性，當父節(jié)點為黑色時，不需要做自平衡操作，如果為黑色，那么插入后褐色層次增加了，破壞特性5。
*
在4.1情況中(P為紅色且U為紅色)如果重復遞歸判斷到根節(jié)點，把根節(jié)點設置成了紅色，則根據(jù)特性1，必須把根節(jié)點變回黑色，此時紅黑樹的黑色節(jié)點層次就增加了一層（自底向上生長）。
?四、節(jié)點的刪除
紅黑樹的節(jié)點插入比較復雜，刪除操作更加復雜，但掌握了規(guī)律理解起來就簡單多了；
說到節(jié)點刪除之前，需要先了解一下前繼節(jié)點和后繼節(jié)點的概念，筆者學習過程中看到一個非常容易理解的描述，如下圖：
把所有的節(jié)點投射到X軸上，這時所有的節(jié)點都是自左至右排好的，這樣某個節(jié)點的左邊的節(jié)點就是它的前繼節(jié)點，右邊的節(jié)點就是它的后繼節(jié)點。
由上圖可以看到，后繼節(jié)點是右子樹的最左節(jié)點，前繼節(jié)點是左子樹的最右節(jié)點。
如150節(jié)點的前繼節(jié)點就是130，后繼節(jié)點就是160。
節(jié)點刪除后空出的位置需要找到其后繼節(jié)點或前繼節(jié)點進行補位，如果被刪除的節(jié)點沒有子節(jié)點還好，要是有子節(jié)點，不補位的話樹就散了；并且補位之后有可能會破壞紅黑樹的平衡結構，這時就需要進行自平衡了。
所以節(jié)點的刪除過程可以理解為尋找后繼節(jié)點或前繼節(jié)點（一般習慣用后繼幾點）進行補位后進行自平衡的過程；
這樣理解，節(jié)點刪除問題就可以轉換為補位節(jié)點（后繼節(jié)點）的問題，補位完成后節(jié)點的顏色變?yōu)楸粍h除的顏色。
而這一結果再簡單就可以理解為：補位節(jié)點（后繼節(jié)點）的刪除的自平衡問題，后繼節(jié)點總是在樹的最底層。
這樣一來就可以區(qū)分補位節(jié)點的幾種情況：
?
R -?replace?補位節(jié)點，P -?parent?父節(jié)點，PP -?祖父節(jié)點，B -?brother?兄弟節(jié)點，BL -?brother
left?兄弟節(jié)點左子節(jié)點，BR -?brother right?兄弟節(jié)點右子節(jié)點， O -?其他節(jié)點?
情況1：?R?為紅色
情況1比較簡單，紅色節(jié)點不影響紅黑樹的自平衡結構，所以直接補位，并把顏色轉換為被刪除節(jié)點的顏色。
情況2： R?為黑色
2.1、R?為左子節(jié)點
2.1.1、R?為黑色且為左子節(jié)點，B?為紅色（如圖 2.1.1）
(1)、將 B 設為黑色
(2)、將 P 設為紅色
(3)、對 P 進行左旋，得到 2.1.2.3 情況
(4)、按照 2.1.2.3 情況進行處理
2.1.2、R?為黑色且為左子節(jié)點，B?為黑色
2.1.2.1、R?為黑色且為左子節(jié)點，B?為黑色，BR?為紅色，BL?為任意（如圖 2.1.2.1）
(1)、將 B 設為 P 的顏色
(2)、將 P 設為黑色
(3)、將 BR 設為黑色
(4)、對 P 進行左旋
在此處有幾個問題，注意上圖框出的部分
1、為什么此處不符合自平衡結構？
回答：節(jié)點的刪除是先找到補位節(jié)點（后繼節(jié)點），然后自平衡處理，然后才進行補位，所以此處的 R?之后會移走的，所以還是符合自平衡結構。
2、BL?可能為黑色節(jié)點么？
回答：BL?不可能為黑色節(jié)點，但其可能為黑色葉子節(jié)點（NULL節(jié)點），下邊用窮舉法進行證明；
我們知道，在節(jié)點刪除之前（第一次刪除），紅黑樹是保持平衡結構的，那么如果 BL?為黑色，那么有一下幾種情況：
1）P?為黑色，BL?為黑色，如下圖（1），不平衡，不成立。
2）P?為紅色，BL?為黑色，如下圖（2），不平衡，不成立。
3）P?為紅色，BL?為黑色葉子節(jié)點（NULL），如下圖（3），平衡，成立。
4）P?為黑色，BL?為黑色葉子節(jié)點（NULL），如下圖（4），平衡，成立。
5）BL?為紅色，如下圖（5），平衡，成立。
綜上：BL?只可能為紅色節(jié)點或黑色葉子節(jié)點（NULL）。
2.1.2.2、R?為黑色且為左子節(jié)點，B?為黑色，BR?為黑色，BL?為紅色（如圖 2.1.2.2）
(1)、將 B 設為紅色
(2)、將 BL 設為黑色
(3)、對 B 進行右旋，得到 2.1.2.1 情況
(4)、按照 2.1.2.1 情況進行處理
??
2.1.2.3、R?為黑色且為左子節(jié)點，B?為黑色，BR?為黑色（NULL），BL?為黑色（NULL）（如圖 2.1.2.3）
(1)、將 B 設為紅色
(2)、將 P 作為新的補位節(jié)點
(3)、重新進行刪除節(jié)點處理
?
需要注意：
*
* 這時 P?就是?將要被移走的 R?的補位節(jié)點（后繼節(jié)點）。
* 此種情況下其實 BL，BR?都是黑色的葉子節(jié)點（NULL）。
* B?變?yōu)榧t色是的原因是整顆子樹都是黑色的節(jié)點，R?移走后，無論如何操作都沒辦法在子樹內自平衡，所以，最簡單的操作把
B?變?yōu)榧t色，這樣就自平衡了；但是這樣一來?子樹內部的黑色節(jié)點層數(shù)少了一層，這樣從 P?子樹的上一層數(shù)來看就是不平衡的了，所以要將
P?看成新的補位節(jié)點，進行自平衡操作，自底向上，直至根節(jié)點。
2.2、R為右子節(jié)點
2.2.1、R?為黑色且為右子節(jié)點，B?為紅色（如圖 2.2.1）
(1)、將 B 設為黑色
(2)、將 P 設為紅色
(3)、對 P 進行右旋，得到 2.2.2.3 情況
(4)、按照 2.2.2.3 情況進行處理
2.2.2、R?為黑色且為右子節(jié)點，B 為黑色
2.2.2.1、R?為黑色且為右子節(jié)點，B?為黑色，BL 為紅色，BR 為任意（如圖 2.2.2.1）
(1)、將 B 設為 P 的顏色
(2)、將 P 設為黑色
(3)、將 BL 設為黑色
(4)、對 P 進行右旋
注意：
此種情況請參考 2.1.2.1中的問題與回答。?
2.2.2.2、R?為黑色且為右子節(jié)點，B?為黑色，BL 為黑色，BR 為紅色（如圖 2.2.2.2）
(1)、將 B 設為紅色
(2)、將 BR 設為黑色
(3)、對 B 進行左旋，得到 2.2.2.1 情況
(4)、按照 2.2.2.1 情況進行處理
?
2.2.2.3、R?為黑色且為右子節(jié)點，B?為黑色，BL 為黑色（NULL），BR 為黑色（NULL）（如圖 2.2.2.3）
(1)、將 B 設為紅色
(2)、將 P 作為新的補位節(jié)點
(3)、重新進行刪除節(jié)點處理
?
需要注意：
參考 2.1.2.3?下方的需要注意說明
節(jié)點刪除總結：
* 節(jié)點的刪除情況比較多，但左右子節(jié)點情況是對稱的，理解了其中一種，另一種也很快會理解。
* 補位節(jié)點可以用前繼節(jié)點代替，也可以用后繼節(jié)點代替，一般習慣用后繼節(jié)點。
* 節(jié)點刪除過程是先找到補位節(jié)點，然后進行自平衡處理，然后才會移除補位節(jié)點，即帶補位節(jié)點的自平衡。
* 在全黑節(jié)點的情況下，可能發(fā)類似遞歸的生自底向上的尋找補位節(jié)點的過程，到根節(jié)點為止。
* 自平衡的順序可以理解為，先自己處理，處理不了找兄弟節(jié)點參與，還處理不了找父節(jié)點參與，還處理不了讓父節(jié)點找父節(jié)點的兄弟處理，以此類推。
五、紅黑樹總結?
通過上邊對紅黑樹的詳細諒解，我們就可以回答開始提出的問題了。
1、紅黑樹為什么要維持自平衡、自平衡的好處是什么？
答：紅黑樹是一個高效的查詢樹，保持平衡結構，可以保證從根節(jié)點到葉子節(jié)點的最長路徑不超過最短路徑的兩倍，可以保證查詢效率。
2、什么是左旋，右旋，變色？
答：左旋、右旋、變色都是對節(jié)點所在子樹的操作，以節(jié)點為基進行變化保持樹的平衡的操作。
3、什么條件下需要進行左旋、右旋、變色？
答：當發(fā)生節(jié)點插入或刪除操作時，紅黑樹的平衡被破壞，這是就要根據(jù)具體的情況進行自平衡操作，即左旋、右旋或變色。
* 紅黑樹的結構比較復雜，無論是節(jié)點的插入還是刪除，都有可能破壞自平衡結構，而自平衡過程最復雜情況可能是自底向上處理，直到根節(jié)點。
* 紅黑樹是平衡二叉樹，但不是完美的平衡二叉樹，只是黑色完美的平衡二叉樹（性質5）
* 紅黑樹的五條性質任意一套被破壞都觸發(fā)自平衡操作。
* 紅色節(jié)點的子節(jié)點一定是黑色，但黑色節(jié)點的子節(jié)點則可以是紅色和黑色任意一種，即可以有相鄰的兩層節(jié)點都是黑色的情況，如圖：
?
?
?此博客為筆者參考網(wǎng)絡上各類文章總結性書寫，原創(chuàng)手打，如有錯誤歡迎指正。
熱門工具 換一換