資訊專欄INFORMATION COLUMN
摘要：強調一下，紅黑樹中的葉子節點指的都是節點。故刪除之后紅黑樹平衡不用調整。將達到紅黑樹平衡。到此關于紅黑樹的基礎已經介紹完畢，下一章我將就源碼中的進行講解說明，看一看紅黑樹是如何在源碼中實現的。
說到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進行講解說明，看一看紅黑樹是如何在源碼中實現的。
參考資料：
https://zh.wikipedia.org/wiki...
https://en.wikipedia.org/wiki...
https://my.oschina.net/hosee/...
https://www.cnblogs.com/tongy...
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/77576.html
摘要：用這種范例表示紅黑樹是可能的，但是這會改變一些性質并使算法復雜。插入會出現種情況為根節點，即紅黑樹的根節點。 說到HashMap，就一定要說到紅黑樹，紅黑樹作為一種自平衡二叉查找樹，是一種用途較廣的數據結構，在jdk1.8中使用紅黑樹提升HashMap的性能，今天就來說一說紅黑樹。 前言 限于篇幅，本文只對紅黑樹的基礎進行說明，暫不涉及源碼部分，大部分摘抄自維基百科，這里也貼出對應鏈接...
摘要：接下來就來說下我眼中的。鏈表轉換為樹的閾值，超過這個長度的鏈表會被轉換為紅黑樹，當然，不止這一個條件，在下面的源碼部分會看到。 源碼部分從HashMap說起是因為筆者看了很多遍這個類的源碼部分，同時感覺網上很多都是粗略的介紹，有些可能還不正確，最后只能自己看源碼來驗證理解，寫下這篇文章一方面是為了促使自己能深入，另一方面也是給一些新人一些指導，不求有功，但求無過。有錯誤的地方請在評論中...
摘要：前言版本以為例是因為之前的紅黑樹操作在文章省略了，這里進行一個解釋，其實源碼里并不是只有這個地方用紅黑樹結構，但是總體上都大同小異，故只說明這一部分就好，舉一反三的能力相信各位都應該擁有。紅黑樹類型遞歸左右子樹遍歷，直到值相等。 前面幾篇文章已經講解過HashMap內部實現以及紅黑樹的基礎知識，今天這篇文章就講解之前HashMap中未講解的紅黑樹操作部分，如果沒了解紅黑樹，請去閱讀前面...
前面已經說明了HashMap以及紅黑樹的一些基本知識，對JDK8的HashMap也有了一定的了解，本篇就開始看看并發包下的ConcurrentHashMap，說實話，還是比較復雜的，筆者在這里也不會過多深入，源碼層次上了解一些主要流程即可，清楚多線程環境下整個Map的運作過程就算是很大進步了，更細的底層部分需要時間和精力來研究，暫不深入 前言 jdk版本：1.8 JDK7中，ConcurrentH...
摘要：上一篇文章已經就進行了部分說明，介紹了其中涉及的常量和變量的含義，有些部分需要結合方法源碼來理解，今天這篇文章就繼續講解并發前言本文主要介紹中的一些重要方法，結合上篇文章中的講解部分進行更進一步的介紹回顧下上篇文章，我們應該已經知道的整體結 上一篇文章已經就ConcurrentHashMap進行了部分說明，介紹了其中涉及的常量和變量的含義，有些部分需要結合方法源碼來理解，今天這篇文章就...
閱讀 2232·2021-09-22 15:25
閱讀 3617·2019-08-30 12:48
閱讀 2205·2019-08-30 11:25
閱讀 2338·2019-08-30 11:05
閱讀 725·2019-08-29 17:28
閱讀 3284·2019-08-26 12:16
閱讀 2608·2019-08-26 11:31
閱讀 1701·2019-08-23 17:08
