1. 前言

一個(gè)紅黑樹是一種自平衡的二叉查找樹。二叉樹的每個(gè)節(jié)點(diǎn)都有一個(gè)額外的位，該位通常被解釋為節(jié)點(diǎn)的顏色（紅色或黑色）。這些顏色位用于確保樹在插入和刪除期間保持近似平衡。

通過以滿足某些屬性的方式用兩種顏色之一繪制樹的每個(gè)節(jié)點(diǎn)來保留平衡，這些屬性共同限制樹在最壞情況下的不平衡。修改樹時(shí)，隨后重新排列新樹并重新繪制以恢復(fù)著色屬性。這些屬性的設(shè)計(jì)使得這種重新排列和重新著色可以有效地進(jìn)行。

樹的平衡并不完美，但它足以保證在O（log n）時(shí)間內(nèi)進(jìn)行搜索，其中n是樹中元素的總數(shù)。插入和刪除操作以及樹重新排列和重新著色也在O（log n）時(shí)間內(nèi)執(zhí)行。

2. 性質(zhì)

★重點(diǎn) 紅黑樹的五條性質(zhì)

• 1.每個(gè)節(jié)點(diǎn)都是紅色或黑色。
• 2.根是黑色的。有時(shí)會(huì)省略此規(guī)則。由于根始終可以從紅色變?yōu)楹谏?，但不一定相反，因此該?guī)則對(duì)分析幾乎沒有影響。
• 3.所有葉子（NIL）都是黑色的。
• 4.如果節(jié)點(diǎn)為紅色，則其子節(jié)點(diǎn)均為黑色。
• 5.從給定節(jié)點(diǎn)到其任何后代NIL節(jié)點(diǎn)的每條路徑都包含相同數(shù)量的黑色節(jié)點(diǎn)。

一些定義：從根到節(jié)點(diǎn)的黑節(jié)點(diǎn)數(shù)是節(jié)點(diǎn)的黑色深度 ; 從根到葉子的所有路徑中的黑色節(jié)點(diǎn)的統(tǒng)一數(shù)量被稱為紅黑樹的黑色高度。

這些約束強(qiáng)制執(zhí)行紅黑樹的關(guān)鍵屬性：從根到最遠(yuǎn)葉子的路徑不超過從根到最近葉子的路徑的兩倍。結(jié)果是樹大致高度平衡。

3. 主要通過分析TreeMap源碼了解紅黑樹的插入和刪除

主要分析的不是具體的插入和刪除操作，而是插入和刪除操作成功后節(jié)點(diǎn)顏色如何進(jìn)行修整，以重新滿足紅黑樹的五種性質(zhì)。

3.1 插入

插入開始于以與標(biāo)準(zhǔn)二進(jìn)制搜索樹插入非常類似的方式添加節(jié)點(diǎn)并將其著色為紅色。最大的區(qū)別在于，在二叉搜索樹中，新節(jié)點(diǎn)被添加為葉子，而葉子在紅黑樹中不包含任何信息，因此新節(jié)點(diǎn)替換現(xiàn)有葉子，然后添加兩個(gè)自己的黑葉子。
紅黑樹插入的幾種情況：
說明：N是新插入的節(jié)點(diǎn) P是N的父節(jié)點(diǎn) U是P的兄弟節(jié)點(diǎn)也即是N的叔叔節(jié)點(diǎn) N為新插入節(jié)點(diǎn)默認(rèn)是紅色的

情況1. N是根節(jié)點(diǎn)

方案：直接將N變成黑色即可 滿足性質(zhì)2 也不違反性質(zhì)5

情況2. P是黑色節(jié)點(diǎn)

方案：什么都不用做 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色的，所以性質(zhì)4不會(huì)失效 性質(zhì)5也不會(huì)有影響

情況3. P是紅色節(jié)點(diǎn)，U也是紅色節(jié)點(diǎn)

方案：將P和U變成黑色，將祖父節(jié)點(diǎn)G變成紅色，性質(zhì)5依然保持，但是祖父節(jié)點(diǎn)G有可能違反性質(zhì)2，如果G就是根節(jié)點(diǎn)，就把G變成黑色，否則進(jìn)行向上遞歸調(diào)整。

情況4. 步驟一：P是紅色節(jié)點(diǎn)，U是黑色節(jié)點(diǎn)，N是P的右子節(jié)點(diǎn)。

方案：先對(duì)N進(jìn)行左旋(將任意節(jié)點(diǎn)通過旋轉(zhuǎn)變成其右子節(jié)點(diǎn)的左子節(jié)點(diǎn))操作，然后進(jìn)行步驟二繼續(xù)調(diào)整。

情況4. 步驟二：P是紅色節(jié)點(diǎn)，U是黑色節(jié)點(diǎn)，N是P的左子節(jié)點(diǎn)。

方案：對(duì)G進(jìn)行右旋，調(diào)整P和G的位置并互換顏色，此時(shí)性質(zhì)4被恢復(fù)，性質(zhì)5也沒有受到影響。

代碼來自JDK11 TreeMap源碼，為了方便與圖示進(jìn)行參照，特意改了一下變量名

3.2 刪除

在刪除具有兩個(gè)非葉子節(jié)點(diǎn)的節(jié)點(diǎn)D時(shí)，在常規(guī)二叉搜索樹中，我們找到其左子樹中的最大元素或其右子樹中的最小元素X，然后移動(dòng)X的值寫入被刪除節(jié)點(diǎn)D中，最后將X節(jié)點(diǎn)刪除，這樣就將要?jiǎng)h除有兩個(gè)孩子節(jié)點(diǎn)的情況轉(zhuǎn)化為刪除只有一個(gè)孩子節(jié)點(diǎn)的情況，至于最終刪除的是節(jié)點(diǎn)X，而不是最初要?jiǎng)h除的D并無大礙，D的值已經(jīng)刪除了，X的值也移到了D節(jié)點(diǎn)只是紅黑樹內(nèi)部結(jié)構(gòu)變化了，數(shù)據(jù)并沒有丟失。接下來討論的就是刪除節(jié)點(diǎn)后，紅黑樹顏色調(diào)整問題，需要注意的是現(xiàn)在X只有一個(gè)孩子節(jié)點(diǎn)N。

首先聲明要?jiǎng)h除的節(jié)點(diǎn)是X，X的孩子節(jié)點(diǎn)是N，
現(xiàn)在N替換了X的位置,
N的父節(jié)點(diǎn)是P并且N是P的左孩子節(jié)點(diǎn)，
N的兄弟節(jié)點(diǎn)是S，
S的左孩子節(jié)點(diǎn)是S<sub>L</sub>,S的右孩子節(jié)點(diǎn)是S<sub>R</sub>

先來粗略討論幾種大概的情況:

• 刪除節(jié)點(diǎn)X是紅色。 因?yàn)閄是紅色，根據(jù)性質(zhì)4，N和P必定是都是黑色，直接刪除X并不會(huì)影響性質(zhì)5
• 刪除節(jié)點(diǎn)X是黑色，子節(jié)點(diǎn)N是紅色。 將N變成黑色即可
• 刪除節(jié)點(diǎn)X是黑色，子節(jié)點(diǎn)N也是黑色。 此時(shí)比較復(fù)雜，可以再細(xì)分為以下5種情況。

情況1. N是新的根節(jié)點(diǎn)

方案：這種情況刪除了原先的根，只剩一個(gè)新根N，滿足性質(zhì)2

情況2. S是紅色

方案：交換S和P的顏色，并將P左旋
然后N的兄弟節(jié)點(diǎn)變成了S_L，此時(shí)S_L一定是黑色(它曾是紅色節(jié)點(diǎn)S的孩子)，然后以P為根節(jié)點(diǎn)的子樹繼續(xù)向下遞歸處理

情況3. S和S的孩子節(jié)點(diǎn)都是黑色 P可紅可黑

方案：將S變成紅色，如果P為紅色，就將P也變成黑色
然后會(huì)將N變成它的父節(jié)點(diǎn)P，向上進(jìn)行遞歸處理，如果P是紅色，結(jié)束平衡過程，將P變成黑色；如果P是黑色，然后重新執(zhí)行平衡過程，從情況1開始
如果此時(shí)P是紅色，正好符合情況2處理之后的情形

情況4. S是黑色 S的左孩子是紅色 S的右孩子是黑色

方案：在S處右旋，并將S節(jié)點(diǎn)置黑，S_L節(jié)點(diǎn)置紅，繼續(xù)情況5進(jìn)行處理

情況5. S是黑色 S的右孩子是紅色 S的左孩子可紅可黑

方案：將S_R置黑，并交換S和P的顏色，然后再P節(jié)點(diǎn)處進(jìn)行左旋
這樣S→N彌補(bǔ)了刪除的一個(gè)黑色節(jié)點(diǎn)，S→S_R和S→_L的黑色節(jié)點(diǎn)數(shù)不變

下面代碼也是來自JDK11 TreeMap源碼，為了方便與圖示進(jìn)行參照，特意改了一下變量名

總結(jié)

相信根據(jù)代碼邏輯和圖的對(duì)照進(jìn)行思考，紅黑樹的插入刪除操作之后的平衡調(diào)整也就不在話下了??

參考

• 紅黑樹 – 維基百科
• 紅黑樹詳細(xì)分析