算法--我的紅黑樹學習過程
其他更多java基礎文章：
java基礎學習(目錄)
學習資料：紅黑樹詳細分析，看了都說好紅黑樹刪除操作碼圖並茂紅黑樹紅黑樹從頭至尾插入和刪除結點的全程演示圖
閱讀前提
在研究集合類源碼的時候，發現Map，Set裡面不少用到紅黑樹，為了能夠更順利的學習源碼。我決定把紅黑樹知識惡補一下。如果不瞭解樹、二叉樹、平衡二叉樹定義的同學先了解一下這些前提知識。 由於能力時間有限，我就不復述學習資料裡大神寫的內容了。關於一些基礎知識和概念請大家先讀一遍學習資料裡的文章。我接下來的講解都將基於這三篇的基礎之上，進行更細緻的講解，把我在學習過程中遇到的一些比較難理解的點嘗試用文字或圖例變得更容易理解。
我強烈建議大家的閱讀順序為：先讀紅黑樹詳細分析，看了都說好。這篇文章講的比較全，但是刪除部分對我來說，文字上有點難理解。接著閱讀紅黑樹刪除操作。這篇文章把刪除講解的比較細緻。最後再閱讀紅黑樹從頭至尾插入和刪除結點的全程演示圖或碼圖並茂紅黑樹。前者格式不好，後者漏了一步，可以主要以後者為主。兩篇文章就是來學以致用的，文章以圖來全程演示此紅黑樹的所有插入，和刪除情況。但是缺點是沒有任何講解，所以正適合檢驗一下前兩篇的學習和理解，建議大家可以先自己推理一步，然後再看與文章中的下一步的結果圖是否一致。
OK，現在就當大家已經按上面步驟閱讀完了。如果此時還有疑問或不懂的地方，可以繼續往下閱讀，也可以在評論中詢問我，我會盡力回答。由於個人只是對紅黑樹的刪除部分覺得有難點，所以下面主要講的是紅黑樹刪除部分。
紅黑樹刪除
前提知識
1. 紅黑樹的定義
- 任何一個節點非紅即黑；
- 樹的根為黑色；
- 葉子節點為黑色(注意：紅黑樹的所有葉子節點都指的是Nil節點)；
- 任何兩個父子節點不可能同時為紅色；
- 任何節點到其所有分枝葉子的簡單路徑上的黑節點個數相同；
2. 節點命名約定
D表示要被刪除的節點。即：取 Delete 的首字母；
P 表示父節點。即：取 Parent 的首字母；
S表示兄弟姐妹節點。即：取 Sibling的首字母；
U表示叔伯節點。即：取Uncle的首字母；
G表示祖父節點。即：取 Grandfather的首字母；
L表示左樹。即：取Left的首字母 ；
R表示右樹。即：取Right的首字母；
Nil表示葉子節點。即所謂的空節點；注意：紅黑樹中的葉子節點與其他樹中所述說的葉子節點不是同一概念。而且紅黑樹中的葉子節點(即：Nil節點)永遠是被定義為黑色的。
下文的節點命名錶示將會使用以上這些命名約定或它們的組合表示。因此，請先牢記這些命名約定。舉例：
DR表示要被刪除的節點的右子樹，即：右子節點； SL表示兄弟節點的左子樹，即：左子節點；
3. 刪除操作宏觀分析
在紅黑樹中，刪除一個節點往大的說，只有以下四種情況。
情況一：刪除的節點的左、右子樹都非空；
情況二：刪除的節點的左子樹為空樹，右子樹非空；
情況三：刪除的節點的右子樹為空樹，左子樹非空；
情況四：刪除的節點的左、右子樹都為空樹；
其中情況一，可以按與其他二叉搜索樹的刪除方式一樣處理，最終可以轉換到後面的三種情況。具體為：找到(Old)D節點的直接後繼節點(暫且稱為X節點)，然後將X的值轉移到D節點，最後將X節點作為真正要被刪除掉的節點(即：(Real)D節點)。 這樣刪除操作後，可以保證該樹仍然為一棵二叉搜索樹。但由於紅黑樹的定義(即：紅黑樹的性質)約定。這樣刪除(Real)D節點後，可能會破壞紅黑樹的性質。所以需要額外做一些調整處理，這便是下面將要詳細討論的內容。 說明：下文中所提到的D，除非有特別說明，否則都將指的是(Real)D。
刪除情況分類
通過閱讀紅黑樹詳細分析，看了都說好、紅黑樹刪除操作 兩篇文章，可以發現雖然說法不同，但是絕大多數應對的情形是一樣，我整理為下列表格：
圖例《紅黑樹刪除操作》《紅黑樹詳細分析》備註
被刪除D為紅只需要直接將D節點刪除，並將DR作為P的左子節點即可。
D為黑，DR不為Nil、DR必為紅由於紅黑樹定義5，（P-D-Nil）和（P-D-DR-Nil）的黑點數一樣，所以DR必為紅
D黑、DR為Nil、S紅情況二仍需繼續平衡
D黑、S黑、SL紅情況五（後續為情況六）這裡兩篇文章有些不同，《刪除操作》中單獨處理，《詳細分析》將與情況六搭配起來處理平衡，但是結果是一樣的。個人喜歡使用情況五六搭配起來使用方式
D黑、S黑、SR紅情況六
D黑、S黑、P紅、SL黑、SR黑情況四
D黑、S黑、P黑、SL黑、SR黑情況三可能仍需繼續平衡，此時經過P的路徑的黑節點個數將會比不經過它的路徑少一個。因此，我們將P作為待平衡的節點(即：此時的P相當於DR的角色)往上繼續上溯，直到P為根節點為止。
D黑、DR為Nil、S紅（情況二）詳解
在紅黑樹刪除操作中D黑、DR為Nil、S紅這個分支個人認為講的有點太繞了。圖畫的容易讓人混淆。我重新畫個圖方便大家理解。其實作者省略了SL和SR的葉子節點，準確的紅黑樹圖應該如下：
當刪除結點D後通過旋轉變色，得到的結果如下：
可以發現，此時乍看一下好像是平衡了，但是把葉子結點加上後，就會發現（S-P-DR）這條線比其他線少一個黑結點。此時需要繼續平衡，這個時候我們的DR結點的兄弟結點是SL，所以匹配D黑、S黑、P紅、SL黑、SR黑的情況。
所以最終平衡結果如下：
在刪除結點演示圖中的刪除結點16，就是這個情況。紅黑樹刪除結點演示圖部分詳解
這裡我們根據紅黑樹從頭至尾插入和刪除結點的全程演示圖的刪除演示圖，詳解其中的幾步。
刪除結點12
先尋找到結點12的後繼結點13，然後將13的值複製到結點12處，將結點13刪除，此時可以發現匹配D黑、S黑、SR紅的情況（因為是鏡像的原因，所以是SR紅不是SL紅），根據匹配的結果旋轉變色，最後得到結果紅黑樹：
刪除結點13
此時紅黑樹為，我們將刪除結點13
把注意力集中在13-16-17這棵紅黑樹上，發現匹配D黑、S黑、P黑、SL黑、SR黑情形，根據匹配結果著色為下圖（右）：
此時以結點16為根的紅黑樹平衡了，但是我們把目光放在整棵紅黑樹上，會發現所有經過結點16的黑節點數會比不經過結點16的少1，所以根據D黑、S黑、P黑、SL黑、SR黑的備註，我們將原P（結點16）作為待平衡的節點(DR)往上繼續上溯，直到P為根節點為止。如下圖所示（結點16連線斷開僅是為了防止匹配時被紅結點17干擾）：
最後
最後，如果你也在學習紅黑樹，希望這篇文章能夠幫助到你。另外，由於紅黑樹本身比較複雜，加之本人水平有限，難免會出一些錯誤。如果有錯或者有疑問，還望大家指出來，我們共同討論。參考文獻：K碼農-http://kmanong.top/kmn/qxw/form/home?top_cate=28
閱讀更多 AI科技園 的文章
