JDK源碼那些事兒之紅黑樹基礎(chǔ)下篇

羅志環(huán) 發(fā)布于2019-08-19 11:38 / 678人閱讀

摘要：強(qiáng)調(diào)一下，紅黑樹中的葉子節(jié)點指的都是節(jié)點。故刪除之后紅黑樹平衡不用調(diào)整。將達(dá)到紅黑樹平衡。到此關(guān)于紅黑樹的基礎(chǔ)已經(jīng)介紹完畢，下一章我將就源碼中的進(jìn)行講解說明，看一看紅黑樹是如何在源碼中實現(xiàn)的。

說到HashMap，就一定要說到紅黑樹，紅黑樹作為一種自平衡二叉查找樹，是一種用途較廣的數(shù)據(jù)結(jié)構(gòu)，在jdk1.8中使用紅黑樹提升HashMap的性能，今天就來說一說紅黑樹，上一講已經(jīng)給出插入平衡的調(diào)整操作，這一講就說說更為復(fù)雜的刪除平衡操作。

前言

限于篇幅，本文只對紅黑樹的基礎(chǔ)進(jìn)行說明，暫不涉及源碼部分，大部分摘抄自維基百科，這里也貼出對應(yīng)鏈接：

維基百科(中文)：https://zh.wikipedia.org/wiki...

維基百科：https://en.wikipedia.org/wiki...

筆者這里會根據(jù)維基百科的講解做些說明，方便初學(xué)者理解。

刪除平衡

在正式進(jìn)入紅黑樹的刪除說明之前，想下二叉搜索樹中的刪除是如何做的？

參照二叉搜索樹的刪除調(diào)整原理：

如果需要刪除的節(jié)點有兩個兒子，那么問題可以被轉(zhuǎn)化成刪除另一個只有一個兒子的節(jié)點的問題（為了表述方便，這里所指的兒子，為非葉子節(jié)點的兒子）。對于二叉查找樹，在刪除帶有兩個非葉子兒子的節(jié)點的時候，我們要么找到它左子樹中的最大元素、要么找到它右子樹中的最小元素，并把它的值轉(zhuǎn)移到要刪除的節(jié)點中（如在這里所展示的那樣）。我們接著刪除我們從中復(fù)制出值的那個節(jié)點，它必定有少于兩個非葉子的兒子。因為只是復(fù)制了一個值（沒有復(fù)制顏色），不違反任何性質(zhì)，這就把問題簡化為如何刪除最多有一個兒子的節(jié)點的問題。它不關(guān)心這個節(jié)點是最初要刪除的節(jié)點還是我們從中復(fù)制出值的那個節(jié)點。

那么紅黑樹中會出現(xiàn)哪些情況呢？

刪除節(jié)點的左右子樹都非空

刪除節(jié)點的左子樹為空，右子樹非空

刪除節(jié)點的右子樹為空，左子樹非空

刪除節(jié)點的左右子樹都為空

對于第一種情況，我們可以找到刪除節(jié)點的后繼節(jié)點，將值替換，然后刪除后繼節(jié)點，這樣保證了該樹仍然是一棵二叉樹，但是在刪除后繼節(jié)點時可能破壞了紅黑樹的特性，故需要進(jìn)行調(diào)整。強(qiáng)調(diào)一下，紅黑樹中的葉子節(jié)點指的都是NIL節(jié)點。

這樣來看，被刪除的節(jié)點一定有一個右子樹，可能為NIL也可能為非空子樹，接下來就具體看看情況。

1.如果刪除節(jié)點E為紅色，則E子節(jié)點F則必為黑色（紅黑樹特性），這種情況只有在E的兩個節(jié)點都為葉子節(jié)點時才會發(fā)生。故刪除之后紅黑樹平衡不用調(diào)整。可以自行畫圖驗證：

刪除節(jié)點E有兩個非葉子節(jié)點，這不可能，因為E已經(jīng)是后繼節(jié)點。

E有一個非葉子節(jié)點（右子節(jié)點），則這個非葉子節(jié)點F為黑色，通過E的兩條黑色路徑不同，不滿足特性5

2.如果刪除節(jié)點E為黑色，F(xiàn)為紅色，這種情況下，F(xiàn)節(jié)點有兩個葉子節(jié)點（需保證紅黑樹特性，黑色路徑需保持一致）則F放置到E處時只需要變色就可以使得紅黑樹平衡

3.如果刪除節(jié)點E為黑色，F(xiàn)也為黑色，這種情況只有在E的兩個節(jié)點都為葉子節(jié)點時才會發(fā)生。參考上邊情況1的驗證。這里刪除了一個黑色節(jié)點，紅黑樹平衡被破壞（黑色路徑不同了），需要進(jìn)行調(diào)整

針對3這里就又會有以下幾種情況：

N為刪除的位置節(jié)點，現(xiàn)在被刪除的節(jié)點的子節(jié)點取代(這里子節(jié)點對應(yīng)上邊的F，即刪除后，N的位置為葉子節(jié)點)，N為黑色，P為N的父母，S為P的右子，SL代表S的左子，SR代表S的右子。

S必不為葉子節(jié)點，反推下，如果為葉子節(jié)點，在未刪除之前P的兩邊黑色路徑就不一致了（未刪除之前是P->E->F這種，自行畫圖理解）。注意，下面列舉的情況都是在刪除E節(jié)點后，子節(jié)點取代E形成的情況，在此基礎(chǔ)上進(jìn)行紅黑樹的調(diào)整。按照順序每種情況進(jìn)行判斷處理。注意每種情況處理之后會重新標(biāo)記，以適應(yīng)下次情況的對比調(diào)整，并且下列過程只以第一次調(diào)用時說明，遞歸調(diào)用下列順序過程時將葉子節(jié)點當(dāng)成一個已經(jīng)平衡的局部紅黑樹即可。和之前的插入平衡調(diào)整類似，每次都是局部化調(diào)整。

第一種情況：如果N為根節(jié)點，不需要調(diào)整平衡了，原有樹只有一個非葉子節(jié)點，兩個葉子節(jié)點，刪除了根節(jié)點，相當(dāng)于刪除了紅黑樹。繼續(xù)第二種情況判斷。

第二種情況：如果N(這里是葉子節(jié)點NIL)是其父P的左子節(jié)點，S為紅色，P必為黑色，參照下圖，反轉(zhuǎn)P和S的顏色，然后在P處向左旋轉(zhuǎn)，將S轉(zhuǎn)換為N的祖父母。這里N處的黑色路徑少一個，還未平衡。N是其父P的右子節(jié)點參照相似處理。SL標(biāo)記為新的S繼續(xù)以N,P,S這塊局部樹進(jìn)行處理。繼續(xù)第三種情況處理。

第三種情況：如果P，S和S的孩子都是黑色，左圖顯示了出現(xiàn)的情況，在N替換掉之前的父節(jié)點后形成的狀態(tài)，這里重新繪制S為紅色，變?yōu)橛覉D，在這個局部中滿足平衡紅黑樹的特性4和5，但是通過P節(jié)點的黑色路徑相比原有結(jié)構(gòu)減少了1，還需要進(jìn)行調(diào)整，需重新進(jìn)行平衡。這里重新平衡即從第一種情況再次順序執(zhí)行，以P節(jié)點進(jìn)行重新平衡，相當(dāng)于以P為新的N，黑色路徑少1，再次進(jìn)行平衡調(diào)整。不滿足當(dāng)前情況，再繼續(xù)執(zhí)行第4種情況處理。

第四種情況：如果S和S的孩子是黑色，但P是紅色的。在這種情況下，我們只需交換S和P的顏色。這不會影響通過S的路徑上的黑色節(jié)點數(shù)量，但它確實會在通過N的路徑上添加一個黑色節(jié)點數(shù)，從而彌補(bǔ)這些路徑上已刪除的黑色節(jié)點。將達(dá)到紅黑樹平衡。不滿足當(dāng)前情況，則繼續(xù)第五種情況的處理。

第五種情況：如果S是黑色，S的左孩子是紅色，S的右孩子是黑色，N是其父母的左孩子。在這種情況下，我們在S處右轉(zhuǎn)，這樣S的左邊孩子就成了S的父母和N的新兄弟。然后我們交換S及其新父母的顏色。所有路徑仍然有相同數(shù)量的黑色結(jié)點，但是P的左子樹因為刪除一個節(jié)點導(dǎo)致黑色路徑少1，還未完全平衡。這里進(jìn)行調(diào)整主要是為了滿足第六種情況，繼續(xù)第六種情況的處理。

第六種情況：如果S是黑色，S的右子是紅色，N是其父P的左子。在這種情況下，我們向左旋轉(zhuǎn)P，這樣S成為P和S的右子的父親。然后，我們交換P和S的顏色，并使S的右子節(jié)點變黑。比較刪除前與N替換調(diào)整后的屬性，滿足4和5，與刪除前是一致的。

總結(jié)

刪除操作相對插入操作之后的平衡要復(fù)雜的多，不過按照情況一步步處理也是比較明了的，同樣為了方便初學(xué)者理解，從上邊的過程我們也可以發(fā)現(xiàn)，在一次局部平衡調(diào)整中，最多進(jìn)行3次旋轉(zhuǎn)操作，我這里再進(jìn)行一個流程梳理，幫助各位更好的理解紅黑樹的刪除操作。

到此關(guān)于紅黑樹的基礎(chǔ)已經(jīng)介紹完畢，下一章我將就JDK源碼中的TreeNode進(jìn)行講解說明，看一看紅黑樹是如何在源碼中實現(xiàn)的。

參考資料：

https://zh.wikipedia.org/wiki...

https://en.wikipedia.org/wiki...

https://my.oschina.net/hosee/...

https://www.cnblogs.com/tongy...