JDK原始碼那些事兒之紅黑樹基礎下篇
說到HashMap，就一定要說到紅黑樹，紅黑樹作為一種自平衡二叉查詢樹，是一種用途較廣的資料結構，在jdk1.8中使用紅黑樹提升HashMap的效能，今天就來說一說紅黑樹，上一講已經給出插入平衡的調整操作，這一講就說說更為複雜的刪除平衡操作。
前言
限於篇幅，本文只對紅黑樹的基礎進行說明，暫不涉及原始碼部分，大部分摘抄自維基百科，這裡也貼出對應連結：
維基百科(中文)： https://zh.wikipedia.org/wiki...
維基百科： https://en.wikipedia.org/wiki...
筆者這裡會根據維基百科的講解做些說明，方便初學者理解。
刪除平衡
在正式進入紅黑樹的刪除說明之前，想下二叉搜尋樹中的刪除是如何做的？
參照二叉搜尋樹的刪除調整原理：
如果需要刪除的節點有兩個兒子，那麼問題可以被轉化成刪除另一個只有一個兒子的節點的問題（為了表述方便，這裡所指的兒子，為非葉子節點的兒子）。對於二叉查詢樹，在刪除帶有兩個非葉子兒子的節點的時候，我們要麼找到它左子樹中的最大元素、要麼找到它右子樹中的最小元素，並把它的值轉移到要刪除的節點中（如在這裡所展示的那樣）。我們接著刪除我們從中複製出值的那個節點，它必定有少於兩個非葉子的兒子。因為只是複製了一個值（沒有複製顏色），不違反任何性質，這就把問題簡化為如何刪除最多有一個兒子的節點的問題。它不關心這個節點是最初要刪除的節點還是我們從中複製出值的那個節點。
那麼紅黑樹中會出現哪些情況呢？
- 刪除節點的左右子樹都非空
- 刪除節點的左子樹為空，右子樹非空
- 刪除節點的右子樹為空，左子樹非空
- 刪除節點的左右子樹都為空
對於第一種情況，我們可以找到刪除節點的後繼節點，將值替換，然後刪除後繼節點，這樣保證了該樹仍然是一棵二叉樹，但是在刪除後繼節點時可能破壞了紅黑樹的特性，故需要進行調整。強調一下，紅黑樹中的葉子節點指的都是NIL節點。
這樣來看，被刪除的節點一定有一個右子樹，可能為NIL也可能為非空子樹，接下來就具體看看情況。
1.如果刪除節點E為紅色，則E子節點F則必為黑色（紅黑樹特性），這種情況只有在E的兩個節點都為葉子節點時才會發生。故刪除之後紅黑樹平衡不用調整。可以自行畫圖驗證：
- 刪除節點E有兩個非葉子節點，這不可能，因為E已經是後繼節點。
- E有一個非葉子節點（右子節點），則這個非葉子節點F為黑色，通過E的兩條黑色路徑不同，不滿足特性5
2.如果刪除節點E為黑色，F為紅色，這種情況下，F節點有兩個葉子節點（需保證紅黑樹特性，黑色路徑需保持一致）則F放置到E處時只需要變色就可以使得紅黑樹平衡
3.如果刪除節點E為黑色，F也為黑色，這種情況只有在E的兩個節點都為葉子節點時才會發生。參考上邊情況1的驗證。這裡刪除了一個黑色節點，紅黑樹平衡被破壞（黑色路徑不同了），需要進行調整
針對3這裡就又會有以下幾種情況：
N為刪除的位置節點，現在被刪除的節點的子節點取代(這裡子節點對應上邊的F，即刪除後，N的位置為葉子節點)，N為黑色，P為N的父母，S為P的右子，SL代表S的左子，SR代表S的右子。
S必不為葉子節點，反推下，如果為葉子節點，在未刪除之前P的兩邊黑色路徑就不一致了（未刪除之前是P->E->F這種，自行畫圖理解）。注意，下面列舉的情況都是在刪除E節點後，子節點取代E形成的情況，在此基礎上進行紅黑樹的調整。 按照順序每種情況進行判斷處理 。注意每種情況處理之後會重新標記，以適應下次情況的對比調整，並且下列過程只以第一次呼叫時說明，遞迴呼叫下列順序過程時將葉子節點當成一個已經平衡的區域性紅黑樹即可。和之前的插入平衡調整類似，每次都是區域性化調整。
第一種情況：如果N為根節點，不需要調整平衡了，原有樹只有一個非葉子節點，兩個葉子節點，刪除了根節點，相當於刪除了紅黑樹。繼續第二種情況判斷。
第二種情況：如果N(這裡是葉子節點NIL)是其父P的左子節點，S為紅色，P必為黑色，參照下圖，反轉P和S的顏色，然後在P處向左旋轉，將S轉換為N的祖父母。這裡N處的黑色路徑少一個，還未平衡。N是其父P的右子節點參照相似處理。SL標記為新的S繼續以N,P,S這塊區域性樹進行處理。繼續第三種情況處理。
第三種情況：如果P，S和S的孩子都是黑色，左圖顯示了出現的情況，在N替換掉之前的父節點後形成的狀態，這裡重新繪製S為紅色，變為右圖，在這個區域性中滿足平衡紅黑樹的特性4和5，但是通過P節點的黑色路徑相比原有結構減少了1，還需要進行調整，需重新進行平衡。這裡重新平衡即從第一種情況再次順序執行，以P節點進行重新平衡，相當於以P為新的N，黑色路徑少1，再次進行平衡調整。不滿足當前情況，再繼續執行第4種情況處理。
第四種情況：如果S和S的孩子是黑色，但P是紅色的。在這種情況下，我們只需交換S和P的顏色。這不會影響通過S的路徑上的黑色節點數量，但它確實會在通過N的路徑上新增一個黑色節點數，從而彌補這些路徑上已刪除的黑色節點。將達到紅黑樹平衡。不滿足當前情況，則繼續第五種情況的處理。
第五種情況：如果S是黑色，S的左孩子是紅色，S的右孩子是黑色，N是其父母的左孩子。在這種情況下，我們在S處右轉，這樣S的左邊孩子就成了S的父母和N的新兄弟。然後我們交換S及其新父母的顏色。所有路徑仍然有相同數量的黑色結點，但是P的左子樹因為刪除一個節點導致黑色路徑少1，還未完全平衡。這裡進行調整主要是為了滿足第六種情況，繼續第六種情況的處理。
第六種情況： 如果S是黑色，S的右子是紅色，N是其父P的左子。在這種情況下，我們向左旋轉P，這樣S成為P和S的右子的父親。然後，我們交換P和S的顏色，並使S的右子節點變黑。比較刪除前與N替換調整後的屬性，滿足4和5，與刪除前是一致的。
總結
刪除操作相對插入操作之後的平衡要複雜的多，不過按照情況一步步處理也是比較明瞭的，同樣為了方便初學者理解，從上邊的過程我們也可以發現，在一次區域性平衡調整中，最多進行3次旋轉操作，我這裡再進行一個流程梳理，幫助各位更好的理解紅黑樹的刪除操作。
到此關於紅黑樹的基礎已經介紹完畢，下一章我將就JDK原始碼中的TreeNode進行講解說明，看一看紅黑樹是如何在原始碼中實現的。
參考資料：