首先，在閱讀文章之前，我希望讀者對(duì)二叉樹有一定的了解，因?yàn)榧t黑樹的本質(zhì)就是一顆二叉樹。所以本篇博客中不在將二叉樹的增刪查的基本操作了，需要了解的同學(xué)可以到我之前寫的一篇關(guān)于二叉樹基本操作的博客：https://www.cnblogs.com/rainple/p/9970760.html；

有隨機(jī)數(shù)節(jié)點(diǎn)組成的二叉樹的平均高度為logn，所以正常情況下二叉樹查找的時(shí)間復(fù)雜度為O(logn)。但是，根據(jù)二叉樹的特性，在最壞的情況下，比如存儲(chǔ)的是一個(gè)有序的數(shù)據(jù)的話，那么所以的數(shù)據(jù)都會(huì)形成一條鏈，此時(shí)二叉樹的深度為n，時(shí)間復(fù)雜度為O(n)。紅黑樹就是為了解決這個(gè)問(wèn)題的，它能夠保證在任何情況下樹的深度都保持在logn左右，紅黑樹通過(guò)一下約束來(lái)完成這個(gè)特性：

1、每個(gè)節(jié)點(diǎn)不是紅色就是黑色。

　　2、根節(jié)點(diǎn)為黑色。

　　3、每個(gè)葉子節(jié)點(diǎn)都是黑色的。

　　4、每個(gè)紅色節(jié)點(diǎn)的子節(jié)點(diǎn)都是黑色。

　　5、任意節(jié)點(diǎn)，到其任意葉節(jié)點(diǎn)的所有路徑都包含相同的黑色節(jié)點(diǎn)。

結(jié)構(gòu)如下圖：

　　紅黑樹的基本操作包括刪除和添加。在刪除或者添加一個(gè)節(jié)點(diǎn)的時(shí)候就有可能打破原有的紅黑樹維持的平衡，那么就需要通過(guò)著色和旋轉(zhuǎn)的方式來(lái)使紅黑樹重新達(dá)到平衡。著色是非常簡(jiǎn)單的，直接將節(jié)點(diǎn)的顏色改變就可以了，多以要理解紅黑樹，就必須需要懂得如何進(jìn)行旋轉(zhuǎn)，旋轉(zhuǎn)又分為左旋和右轉(zhuǎn)，兩個(gè)操作相反的，所以理解了一個(gè)旋轉(zhuǎn)的操作就很容易理解另一個(gè)旋轉(zhuǎn)了。

　　左旋：

　　如圖所示，紅色節(jié)點(diǎn)為旋轉(zhuǎn)支點(diǎn)，支點(diǎn)往左子樹移動(dòng)即為左旋。左旋之后我們可以看到原支點(diǎn)的位置被原支點(diǎn)的右子節(jié)點(diǎn)代替，新支點(diǎn)的左子節(jié)點(diǎn)變?yōu)榱嗽瓉?lái)為父節(jié)點(diǎn)的原支點(diǎn)，新支點(diǎn)的左子節(jié)點(diǎn)變?yōu)樵c(diǎn)的右子節(jié)點(diǎn)，因此左旋操作總共右3個(gè)節(jié)點(diǎn)，以為旋轉(zhuǎn)前的結(jié)構(gòu)舉例，分別為紅色節(jié)點(diǎn)（原支點(diǎn)），黃色節(jié)點(diǎn)（新支點(diǎn)）和L節(jié)點(diǎn)。Java代碼實(shí)現(xiàn)如下：

~~~

/**

? ? * 左旋

? ? * @param e 支點(diǎn)

? ? */privatevoidleftRotate(Entry e){

? ? ? ? //支點(diǎn)的右子節(jié)點(diǎn)Entry right = e.right;

? ? ? ? //支點(diǎn)右子節(jié)點(diǎn)的左子節(jié)點(diǎn)Entry rightOfLeft = right.left;

? ? ? ? //新舊支點(diǎn)的替換right.parent = e.parent;

? ? ? ? if(e.parent ==null){

? ? ? ? ? ? root = right;

? ? ? ? }else {

? ? ? ? ? ? if(e == e.parent.left)

? ? ? ? ? ? ? ? e.parent.left = right;

? ? ? ? ? ? else? ? ? ? ? ? ? ? e.parent.right = right;

? ? ? ? }

? ? ? ? //將原支點(diǎn)變?yōu)樾轮c(diǎn)的左節(jié)點(diǎn)right.left = e;

? ? ? ? e.parent = right;

? ? ? ? //將新支點(diǎn)的左節(jié)點(diǎn)變?yōu)榫椭c(diǎn)的右節(jié)點(diǎn)e.right = rightOfLeft;

? ? ? ? if(rightOfLeft !=null)

? ? ? ? ? ? rightOfLeft.parent = e;

? ? }

~~~

　　因?yàn)樵诩t黑樹中每個(gè)節(jié)點(diǎn)都有一個(gè)指針指向自己的父節(jié)點(diǎn)，父節(jié)點(diǎn)也有指針指向子節(jié)點(diǎn)，因?yàn)樵诟膭?dòng)一個(gè)節(jié)點(diǎn)的時(shí)候都需要分別改動(dòng)當(dāng)前節(jié)點(diǎn)和父節(jié)點(diǎn)的指向，結(jié)合左旋的示意圖，用Java代碼實(shí)現(xiàn)起來(lái)就不會(huì)很困難了。

　　右旋

　　　　右旋操作和左旋相反的，兩者互反。依然是紅色作為旋轉(zhuǎn)支點(diǎn)，右旋后黃色節(jié)點(diǎn)代替了紅色節(jié)點(diǎn)原來(lái)的位置，黃色節(jié)點(diǎn)的右節(jié)點(diǎn)旋轉(zhuǎn)后變?yōu)榧t色節(jié)點(diǎn)的左節(jié)點(diǎn)。Java 代碼實(shí)現(xiàn)如下：

/**

? ? * 右旋

? ? * @param e 旋轉(zhuǎn)支點(diǎn)

? ? */privatevoidrightRotate(Entry e){

? ? ? ? //原支點(diǎn)的左節(jié)點(diǎn)Entry left = e.left;

? ? ? ? //原支點(diǎn)的左節(jié)點(diǎn)的右節(jié)點(diǎn)Entry leftOfRight = left.right;

? ? ? ? //新舊支點(diǎn)的替換left.parent = e.parent;

? ? ? ? if(e.parent ==null){//支點(diǎn)的父節(jié)點(diǎn)為根節(jié)點(diǎn)的情況root = left;

? ? ? ? }else{//非跟節(jié)點(diǎn)if(e == e.parent.left)

? ? ? ? ? ? ? ? e.parent.left = left;

? ? ? ? ? ? else? ? ? ? ? ? ? ? e.parent.right = left;

? ? ? ? }

? ? ? ? //將原支點(diǎn)變?yōu)樾轮c(diǎn)的右節(jié)點(diǎn)left.right = e;

? ? ? ? e.parent = left;

? ? ? ? //將新支點(diǎn)未旋轉(zhuǎn)前的右節(jié)點(diǎn)變?yōu)檗D(zhuǎn)換后的原支點(diǎn)的左節(jié)點(diǎn)e.left = leftOfRight;

? ? ? ? if(leftOfRight !=null)

? ? ? ? ? ? leftOfRight.parent = e;

? ? }

　　添加節(jié)點(diǎn)

　　首先，在進(jìn)入主題之前我們?cè)賮?lái)回顧一下紅黑樹的5個(gè)特點(diǎn)：

　1、每個(gè)節(jié)點(diǎn)不是紅色就是黑色。

　　2、根節(jié)點(diǎn)為黑色。

　　3、每個(gè)葉子節(jié)點(diǎn)都是黑色的。

　　4、每個(gè)紅色節(jié)點(diǎn)的子節(jié)點(diǎn)都是黑色。

　　5、任意節(jié)點(diǎn)，到其任意葉節(jié)點(diǎn)的所有路徑都包含相同的黑色節(jié)點(diǎn)。

?　　紅黑樹插入節(jié)點(diǎn)與二叉樹是一致的，所以每次添加節(jié)點(diǎn)肯定是添加到葉子節(jié)點(diǎn)上，具體步驟如下：

?　　第一步：將新節(jié)點(diǎn)插入到紅黑樹中。

　　第二步：將新節(jié)點(diǎn)設(shè)置為紅色。這里為什么需要設(shè)置成紅色呢？主要是為了滿足特性5，這樣在插入節(jié)點(diǎn)后就少解決了一個(gè)沖突，也就少一點(diǎn)麻煩。插入完成后，我們來(lái)看一下還有那些特性是有可能發(fā)生沖突的，特性1每個(gè)節(jié)點(diǎn)不是紅色就是黑色的，這明顯沒(méi)有沖突，特性2根節(jié)點(diǎn)為黑色，當(dāng)插入節(jié)點(diǎn)為根節(jié)點(diǎn)的時(shí)候就會(huì)有沖突了，這種就很簡(jiǎn)單了，直接將根節(jié)點(diǎn)著色為黑色即可。特性3每個(gè)葉子節(jié)點(diǎn)都是黑色，這個(gè)明顯沒(méi)有沖突。特性4每個(gè)紅色節(jié)點(diǎn)的子節(jié)點(diǎn)都是黑色的，這個(gè)特性就有可能會(huì)沖突，因?yàn)樵诓迦胄鹿?jié)點(diǎn)的時(shí)候我們無(wú)法確定新節(jié)點(diǎn)的父節(jié)點(diǎn)的顏色是黑色的還是紅色，如果新節(jié)點(diǎn)的父節(jié)為黑色，那么就不會(huì)有沖突，否則就會(huì)違背了特性4。特性5任意節(jié)點(diǎn)，到其任意子節(jié)點(diǎn)的所有路徑都包含相同的黑色節(jié)點(diǎn)，因?yàn)槲覀儾迦氲男鹿?jié)點(diǎn)被著色為紅色，所以并不會(huì)影響到每個(gè)路徑的黑色節(jié)點(diǎn)的數(shù)量，因此也不會(huì)有沖突。綜上所訴，那么在插入新節(jié)點(diǎn)的時(shí)候，只有特性4有可能發(fā)生沖突。

　　第三步：平衡紅黑樹，使之成為新的紅黑樹。

　　根據(jù)第二部得到的結(jié)論，我們可以知道只有情況是需要解決沖突的，那就是新節(jié)點(diǎn)的父節(jié)點(diǎn)為紅色的時(shí)候違背了特性4。接下來(lái)我們將要討論這個(gè)問(wèn)題，因?yàn)樵谛虏迦胍粋€(gè)節(jié)點(diǎn)之前是一顆已經(jīng)平衡了的紅黑樹，因此根據(jù)特新4，新節(jié)點(diǎn)的祖父節(jié)點(diǎn)必定為黑色。根據(jù)這種情況，我們又可以分為以下四種情況：

　　情況1：新節(jié)點(diǎn)為左節(jié)點(diǎn)，叔叔節(jié)點(diǎn)為紅色；

　　情況2：新節(jié)點(diǎn)為左節(jié)點(diǎn)，叔叔節(jié)點(diǎn)為黑色；

　　情況3：新節(jié)點(diǎn)為右節(jié)點(diǎn)，叔叔節(jié)點(diǎn)為紅色；

　　情況4：新節(jié)點(diǎn)為右節(jié)點(diǎn)，叔叔節(jié)點(diǎn)為黑色；

　　情況1和情況3的情況是一樣的，所以我們可以將這兩種情況看作是一種情況，這個(gè)情況我們稍后再討論，然后看一下情況2和情況4，通過(guò)左旋就可以轉(zhuǎn)換成情況2。

　　綜上所述，我們可以歸結(jié)為3中情況：

　　情況1：叔叔節(jié)點(diǎn)是紅色節(jié)點(diǎn)；

　　情況2：叔叔節(jié)點(diǎn)是黑色節(jié)點(diǎn)，新節(jié)點(diǎn)為右節(jié)點(diǎn)；

　　情況3：叔叔節(jié)點(diǎn)是黑色節(jié)點(diǎn)，新節(jié)點(diǎn)為左節(jié)點(diǎn)；

　　上面我也有提到，當(dāng)插入新節(jié)點(diǎn)時(shí)肯定是屬于第一種情況的，然后2、3由1轉(zhuǎn)換而來(lái)，在此之前我希望你之前已經(jīng)了解過(guò)遞歸的原理和思想，把局部看作整體的思想，因?yàn)檫@將有助于下面討論的理解。下面我們將要繼續(xù)分析這三種情況，情況1這種情況處理起來(lái)比比較簡(jiǎn)單，只需要將祖父節(jié)點(diǎn)變?yōu)榧t色節(jié)點(diǎn)，父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)變?yōu)楹谏纯?，這僅僅只是當(dāng)整個(gè)紅黑樹只有這幾個(gè)節(jié)點(diǎn)的時(shí)候是可以了，但事實(shí)并非如此，這僅僅只是達(dá)到了局部平衡。

上圖，我們看到已經(jīng)達(dá)到了局部的平衡，但是，我們還會(huì)有其他的情況，那就是祖父節(jié)點(diǎn)有可能也會(huì)有父節(jié)點(diǎn)。那么又會(huì)有兩種情況，1是祖父節(jié)點(diǎn)的父節(jié)點(diǎn)可能是黑色的，2是可能是紅色的，如果黑色那么整個(gè)紅黑樹就達(dá)到平衡了。不知道大家根覺(jué)到了沒(méi)有，這兩種情況是不是跟新插入一個(gè)節(jié)點(diǎn)的情況是一致的，是不是又回到了插入新節(jié)點(diǎn)的問(wèn)題了？于是我將局部收到影響的部分畫出來(lái)，如圖：

　　圖a就是將情況1從新著色后的部分受影響的節(jié)點(diǎn)，當(dāng)然只是其中的一種情況，此時(shí)我們將已經(jīng)平衡的部分去掉就變成的圖b的情況，這種情況是不是很熟悉呢？我們的祖父節(jié)點(diǎn)當(dāng)成新節(jié)點(diǎn)，是不是相當(dāng)于上面討論的情況1呢？不過(guò)與上面討論的情況不同的是，這里3中可能情況都可能出現(xiàn)，因?yàn)槭迨骞?jié)點(diǎn)有可能為紅色或黑色。所以這時(shí)候才有可能出現(xiàn)真正的三種情況：

　　情況1：叔叔節(jié)點(diǎn)是紅色節(jié)點(diǎn)；

　　情況2：叔叔節(jié)點(diǎn)是黑色節(jié)點(diǎn)，新節(jié)點(diǎn)為右節(jié)點(diǎn)；

　　情況3：叔叔節(jié)點(diǎn)是黑色節(jié)點(diǎn)，新節(jié)點(diǎn)為左節(jié)點(diǎn)；

　　如果為情況1的話，我們一層一層的往上平衡就可以了，當(dāng)祖父節(jié)點(diǎn)為根節(jié)點(diǎn)的時(shí)候，我們直接將根節(jié)點(diǎn)著色為黑色即可，因?yàn)樽娓腹?jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色的，所以變?yōu)楹谏笕匀皇瞧胶獾?。接下?lái)我們來(lái)討論下情況2和3。

　　很明顯的，這兩種情況的右節(jié)點(diǎn)多出了一個(gè)黑色節(jié)點(diǎn)，這種情況是在情況1向上著色的時(shí)候造成的，即祖父節(jié)點(diǎn)由黑色節(jié)點(diǎn)變?yōu)榱思t色節(jié)點(diǎn)。情況2以父節(jié)點(diǎn)為支點(diǎn)左旋，然后將父節(jié)點(diǎn)和新節(jié)點(diǎn)互換可以得到情況3：

　　情況3進(jìn)行的操作是，首先將父節(jié)點(diǎn)著色為黑色，祖父節(jié)點(diǎn)著色為紅色，然后以祖父為支點(diǎn)進(jìn)行右旋

　　情況3旋轉(zhuǎn)結(jié)束后整棵紅黑也已經(jīng)重新恢復(fù)平衡了。單從部分其實(shí)并看不出已經(jīng)平衡了，我們可以將三個(gè)情況連起來(lái)就可以看到了，如下圖：

　　上圖中都是以n節(jié)點(diǎn)為參考點(diǎn)的，其余無(wú)關(guān)的節(jié)點(diǎn)就不標(biāo)出來(lái)了。n節(jié)點(diǎn)即為插入節(jié)點(diǎn)，但是除了第一次操作n節(jié)點(diǎn)為真正的新節(jié)點(diǎn)，此后的操作所指的n節(jié)點(diǎn)只是有助于我們的理解把他當(dāng)成新節(jié)點(diǎn)。當(dāng)然，這只是其中的一種情況，其他其他的情況可以通過(guò)不斷向上旋轉(zhuǎn)或著色，最終也會(huì)達(dá)到這種情況或者頂部是p節(jié)點(diǎn)為根節(jié)點(diǎn)的時(shí)候，第二種情況直接將根節(jié)點(diǎn)著色為黑色即可。

　　總結(jié)：

　　回顧一下紅黑樹的5個(gè)特性：

　　1、節(jié)點(diǎn)不是紅色就是黑色。

　　2、根節(jié)點(diǎn)為黑色。

　　3、葉子節(jié)點(diǎn)為黑色。

　　4、每個(gè)紅色節(jié)點(diǎn)其子節(jié)點(diǎn)必須是黑色節(jié)點(diǎn)。

　　5、任意節(jié)點(diǎn)到到其任意的子節(jié)點(diǎn)的所有路徑的黑色節(jié)點(diǎn)的數(shù)量相等。

　　在插入新節(jié)點(diǎn)的時(shí)候很顯然，不會(huì)違背1和3，如果插入的是根節(jié)點(diǎn)直接將根節(jié)點(diǎn)著色為黑色即可，這種情況可以忽略不計(jì)，所以插入節(jié)點(diǎn)時(shí)可能會(huì)違背了4和5，又因?yàn)椴迦氲氖羌t色節(jié)點(diǎn)因此5也不會(huì)違背，最后在插入新節(jié)點(diǎn)的時(shí)候我們只需要關(guān)注特性4就可以了。當(dāng)父節(jié)點(diǎn)為紅色的時(shí)候跟4有沖突，所以我們接下來(lái)討論的就是這種情況。我們知道，在插入新節(jié)點(diǎn)之前整顆紅黑樹是平衡的，因此可以得出一個(gè)結(jié)論就是祖父節(jié)點(diǎn)肯定肯定是黑色的。我們現(xiàn)在只關(guān)注相關(guān)的節(jié)點(diǎn)即可，目前，我們知道了祖父的節(jié)點(diǎn)為黑色，父節(jié)點(diǎn)為紅色，但是叔叔節(jié)點(diǎn)的顏色不知道，新節(jié)點(diǎn)的位置也不能確定，所以有2x2中情況，當(dāng)叔叔節(jié)點(diǎn)為紅色的時(shí)候，兩種情況的處理方式是一致的，所以最后我們可以總結(jié)為3中情況：

　　1、叔叔節(jié)點(diǎn)為紅色

　　2、新節(jié)點(diǎn)為右節(jié)點(diǎn)，叔叔節(jié)點(diǎn)為黑色

　　3、新節(jié)點(diǎn)為左節(jié)點(diǎn)，叔叔節(jié)點(diǎn)為黑色

類型描述步驟示意圖

情況1叔叔節(jié)點(diǎn)為紅色1、父節(jié)點(diǎn)設(shè)為黑色

2、叔叔節(jié)點(diǎn)設(shè)為黑色

3、祖父節(jié)點(diǎn)設(shè)為紅色

4、把祖父節(jié)點(diǎn)設(shè)置為新節(jié)點(diǎn)（當(dāng)前節(jié)點(diǎn)）

情況2新節(jié)點(diǎn)為右節(jié)點(diǎn)，叔叔節(jié)點(diǎn)為黑色1、以父節(jié)點(diǎn)為支點(diǎn)左旋

2、父節(jié)點(diǎn)和新節(jié)點(diǎn)互換位置

3、把父節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn)

情況3新節(jié)點(diǎn)為左節(jié)點(diǎn)，叔叔節(jié)點(diǎn)為黑色1、父節(jié)點(diǎn)設(shè)為黑色

2、祖父節(jié)點(diǎn)設(shè)為紅色

3、以祖父節(jié)點(diǎn)為支點(diǎn)右旋

整合

　　樹a就是表中的情況1，通過(guò)著色后直接轉(zhuǎn)換成了情況3，情況3進(jìn)行著色旋轉(zhuǎn)后達(dá)到了平衡，當(dāng)樹b中的叔叔節(jié)點(diǎn)為紅色的時(shí)候與樹a一致，循環(huán)調(diào)用樹a的處理方式，直至達(dá)到樹b的情況或者樹a中的祖父節(jié)點(diǎn)到達(dá)了根節(jié)點(diǎn)，這時(shí)候?qū)⒆娓腹?jié)點(diǎn)設(shè)為黑色即可。

　　這種情況就是由情況1轉(zhuǎn)情況2再轉(zhuǎn)情況3，由情況3重新著色旋轉(zhuǎn)后達(dá)到平衡。

　　需要注意的是：不是每次插入節(jié)點(diǎn)都會(huì)出現(xiàn)3中情況，有可能只出現(xiàn)了2和3，或者只出現(xiàn)了3一種情況。

　　上面是討論左子樹的問(wèn)題，因?yàn)榧t黑色具有堆成性，因此在處理右子樹的時(shí)候與處理左子樹相反即可。Java代碼示例如下：

/**

? ? * 插入新節(jié)點(diǎn)后平衡紅黑樹

? ? * @param e 新節(jié)點(diǎn)

? ? */privatevoidfixAfterInsertion(Entry e) {

? ? ? ? //將新插入節(jié)點(diǎn)設(shè)置為紅色? ? ? ? setRed(e);

? ? ? ? Entry p,g,u;//父節(jié)點(diǎn)和祖父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)Entry current = e;//新節(jié)點(diǎn)/**

? ? ? ? * 這里通過(guò)循環(huán)不斷向上平衡

? ? ? ? */while((p = parentOf(current)) !=null&& isRed(p)){

? ? ? ? ? ? g = parentOf(p);//祖父節(jié)點(diǎn)if(p == g.left){

? ? ? ? ? ? ? ? u = g.right;

? ? ? ? ? ? ? ? //情況1：叔叔節(jié)點(diǎn)為紅色if(u !=null&& isRed(u)){

? ? ? ? ? ? ? ? ? ? setBlack(p);//父節(jié)點(diǎn)設(shè)為黑色setBlack(u);//叔叔節(jié)點(diǎn)設(shè)為黑色setRed(g);//祖父節(jié)點(diǎn)設(shè)為紅色current = g;//把祖父節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn)

? ? ? ? ? ? ? ? ? ? //繼續(xù)向上平衡continue;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? //情況2：當(dāng)前節(jié)點(diǎn)為右節(jié)點(diǎn)，叔叔節(jié)點(diǎn)為黑色if(current == p.right){

? ? ? ? ? ? ? ? ? ? leftRotate(p);//父節(jié)點(diǎn)為支點(diǎn)左旋Entry tmp = p;

? ? ? ? ? ? ? ? ? ? p = current;//父節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)互換current = tmp;//父節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn)? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? //情況3：當(dāng)前節(jié)點(diǎn)為左節(jié)點(diǎn)，叔叔節(jié)點(diǎn)為黑色setBlack(p);//父節(jié)點(diǎn)設(shè)為黑色setRed(g);//祖父節(jié)點(diǎn)設(shè)為紅色rightRotate(g);//祖父節(jié)點(diǎn)為支點(diǎn)右旋}else{//相反的操作u = g.left;

? ? ? ? ? ? ? ? if(u !=null&& isRed(u)){

? ? ? ? ? ? ? ? ? ? setBlack(p);

? ? ? ? ? ? ? ? ? ? setBlack(u);

? ? ? ? ? ? ? ? ? ? setRed(g);

? ? ? ? ? ? ? ? ? ? current = g;

? ? ? ? ? ? ? ? ? ? continue;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? if(current == p.left){

? ? ? ? ? ? ? ? ? ? rightRotate(p);

? ? ? ? ? ? ? ? ? ? Entry tmp = p;

? ? ? ? ? ? ? ? ? ? p = current;

? ? ? ? ? ? ? ? ? ? current = tmp;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? setBlack(p);

? ? ? ? ? ? ? ? setRed(g);

? ? ? ? ? ? ? ? leftRotate(g);

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? //最后將根節(jié)點(diǎn)設(shè)置為紅色? ? ? ? setBlack(root);

? ? }

　　刪除節(jié)點(diǎn)

　　在二叉樹分析一文中已經(jīng)說(shuō)過(guò)，刪除一個(gè)節(jié)點(diǎn)的時(shí)候有3中情況：

　　1、刪除節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)

　　2、刪除節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)

　　3、刪除節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)

　　首先，我們逐個(gè)來(lái)分析每種情況刪除節(jié)點(diǎn)后對(duì)整顆紅黑樹的平衡性的影響。在刪除節(jié)點(diǎn)時(shí)候紅黑樹的特性1，2，3肯定不會(huì)違背，所以只需要考慮特性4，5即可。

　　對(duì)于情況1，肯定不會(huì)違背特性4，如果刪除節(jié)點(diǎn)為紅色，那么對(duì)整顆紅黑樹的平衡性都不會(huì)影響，如果是黑色則違背了特性5，我們先將這種情況記錄下來(lái)，稍后再進(jìn)一步討論。

　　對(duì)于情況2，有可能刪除的是左子樹或右子樹，暫且不討論。如果刪除的節(jié)點(diǎn)為紅色，不影響平衡性，如果刪除的是黑色，那么肯定會(huì)和特性5有沖突，當(dāng)刪除節(jié)點(diǎn)的父節(jié)點(diǎn)為紅色，子節(jié)點(diǎn)為紅色是也和特性4有沖突。

　　對(duì)于情況3，其實(shí)最后刪除的是它的替代節(jié)點(diǎn)，根據(jù)替代節(jié)點(diǎn)的特點(diǎn)，最終其實(shí)是回到了1這種情況或者情況2。

　　總結(jié)上面的3種情況可得到一個(gè)結(jié)論，只有刪除節(jié)點(diǎn)為黑色時(shí)才會(huì)破壞紅黑樹原來(lái)的平衡，因在刪除節(jié)點(diǎn)之前紅黑樹是出于平衡狀態(tài)的，刪除之后很明顯的其兄弟節(jié)點(diǎn)分支必然比刪除節(jié)點(diǎn)的分支多了一個(gè)黑色的節(jié)點(diǎn)，因此我們只需要改變兄弟節(jié)點(diǎn)的顏色即可，我們只討論左節(jié)點(diǎn)，右節(jié)點(diǎn)對(duì)稱。

　　一、刪除節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是紅色

　　將兄弟節(jié)點(diǎn)設(shè)為黑色，父節(jié)點(diǎn)設(shè)為紅色，以父節(jié)點(diǎn)為支點(diǎn)左旋轉(zhuǎn)，然后將父節(jié)點(diǎn)的右節(jié)點(diǎn)放到兄弟節(jié)點(diǎn)上：

　　二、兄弟節(jié)點(diǎn)是黑色的，兄弟的兩個(gè)子節(jié)點(diǎn)也都是黑色的

　　兄弟節(jié)點(diǎn)設(shè)為紅色，把父節(jié)點(diǎn)設(shè)置為新的刪除節(jié)點(diǎn)：

　　三、兄弟節(jié)點(diǎn)是黑色的，且兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)是紅色，右子節(jié)點(diǎn)是黑色

　　將兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)設(shè)為黑色，兄弟節(jié)點(diǎn)設(shè)為紅色，以兄弟節(jié)點(diǎn)為支點(diǎn)右旋，把父節(jié)點(diǎn)的右節(jié)點(diǎn)設(shè)置為兄弟節(jié)點(diǎn)

四、兄弟節(jié)點(diǎn)是黑色的，且兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)是紅色，左子節(jié)點(diǎn)任意顏色

　　把兄弟節(jié)點(diǎn)的設(shè)為父節(jié)點(diǎn)的顏色，父節(jié)點(diǎn)設(shè)為黑色，父節(jié)點(diǎn)的右節(jié)點(diǎn)設(shè)為黑色，父節(jié)點(diǎn)為支點(diǎn)左旋

　　刪除的Java代碼示例：

public V remove(Object key){

? ? ? ? if(key ==null)returnnull;

? ? ? ? Entry delEntry;

? ? ? ? delEntry = getEntry(key);

? ? ? ? if(delEntry ==null)returnnull;

? ? ? ? size--;

? ? ? ? Entry p = delEntry.parent;

? ? ? ? if(delEntry.right ==null&& delEntry.left ==null){

? ? ? ? ? ? if(p ==null){

? ? ? ? ? ? ? ? root =null;

? ? ? ? ? ? }else {

? ? ? ? ? ? ? ? if(p.left == delEntry){

? ? ? ? ? ? ? ? ? ? p.left =null;

? ? ? ? ? ? ? ? }else {

? ? ? ? ? ? ? ? ? ? p.right =null;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }elseif(delEntry.right ==null){//只有左節(jié)點(diǎn)Entry lc = delEntry.left;

? ? ? ? ? ? if(p ==null) {

? ? ? ? ? ? ? ? lc.parent =null;

? ? ? ? ? ? ? ? root = lc;

? ? ? ? ? ? } else {

? ? ? ? ? ? ? ? if(delEntry == p.left){

? ? ? ? ? ? ? ? ? ? p.left = lc;

? ? ? ? ? ? ? ? }else {

? ? ? ? ? ? ? ? ? ? p.right = lc;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? lc.parent = p;

? ? ? ? ? ? }

? ? ? ? }elseif(delEntry.left ==null){//只有右節(jié)點(diǎn)Entry rc = delEntry.right;

? ? ? ? ? ? if(p ==null) {

? ? ? ? ? ? ? ? rc.parent =null;

? ? ? ? ? ? ? ? root = rc;

? ? ? ? ? ? }else {

? ? ? ? ? ? ? ? if(delEntry == p.left)

? ? ? ? ? ? ? ? ? ? p.left = rc;

? ? ? ? ? ? ? ? else? ? ? ? ? ? ? ? ? ? p.right = rc;

? ? ? ? ? ? ? ? rc.parent = p;

? ? ? ? ? ? }

? ? ? ? }else{//有兩個(gè)節(jié)點(diǎn),找到后繼節(jié)點(diǎn)，將值賦給刪除節(jié)點(diǎn)，然后將后繼節(jié)點(diǎn)刪除掉即可Entry successor = successor(delEntry);//獲取到后繼節(jié)點(diǎn)boolean color = successor.color;

? ? ? ? ? ? V old = delEntry.value;

? ? ? ? ? ? delEntry.value = successor.value;

? ? ? ? ? ? delEntry.key = successor.key;

? ? ? ? ? ? if(delEntry.right == successor){//后繼節(jié)點(diǎn)為右子節(jié)點(diǎn)，if(successor.right !=null) {//右子節(jié)點(diǎn)有右子節(jié)點(diǎn)delEntry.right = successor.right;

? ? ? ? ? ? ? ? ? ? successor.right.parent = delEntry;

? ? ? ? ? ? ? ? }else{//右子節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)delEntry.right =null;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }else {

? ? ? ? ? ? ? ? successor.parent.left =null;

? ? ? ? ? ? }

? ? ? ? ? ? if(color == BLACK)

? ? ? ? ? ? ? ? //fixUpAfterRemove(child,parent);return old;

? ? ? ? }

? ? ? ? V old = delEntry.value;

? ? ? ? if(delEntry.color == BLACK)//刪除為黑色時(shí)，需要重新平衡樹if(delEntry.right !=null)//刪除節(jié)點(diǎn)的子節(jié)點(diǎn)只有右節(jié)點(diǎn)? ? ? ? ? ? ? ? fixUpAfterRemove(delEntry.right,delEntry.parent);

? ? ? ? ? ? elseif(delEntry.left !=null)//刪除節(jié)點(diǎn)只有左節(jié)點(diǎn)? ? ? ? ? ? ? ? fixUpAfterRemove(delEntry.left,delEntry.parent);

? ? ? ? ? ? else? ? ? ? ? ? ? ? fixUpAfterRemove(null,delEntry.parent);

? ? ? ? delEntry.parent =null;

? ? ? ? delEntry.left =null;

? ? ? ? delEntry.right =null;

? ? ? ? return old;

? ? }

? ? privateEntry getEntry(Object key) {

? ? ? ? if(key ==null)returnnull;

? ? ? ? Entry delEntry =null;

? ? ? ? Entry current = root;

? ? ? ? int ret;

? ? ? ? if(comparator ==null){

? ? ? ? ? ? Comparable k = (Comparable) key;

? ? ? ? ? ? while(current !=null){

? ? ? ? ? ? ? ? ret = k.compareTo(current.key);

? ? ? ? ? ? ? ? if(ret <0)

? ? ? ? ? ? ? ? ? ? current = current.left;

? ? ? ? ? ? ? ? elseif(ret >0)

? ? ? ? ? ? ? ? ? ? current = current.right;

? ? ? ? ? ? ? ? else{

? ? ? ? ? ? ? ? ? ? delEntry = current;

? ? ? ? ? ? ? ? ? ? break;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }else {

? ? ? ? ? ? for(;current !=null;){

? ? ? ? ? ? ? ? ret = comparator.compare(current.key, (K) key);

? ? ? ? ? ? ? ? if(ret <0)

? ? ? ? ? ? ? ? ? ? current = current.left;

? ? ? ? ? ? ? ? elseif(ret >0)

? ? ? ? ? ? ? ? ? ? current = current.right;

? ? ? ? ? ? ? ? else{

? ? ? ? ? ? ? ? ? ? delEntry = current;

? ? ? ? ? ? ? ? ? ? break;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? return delEntry;

? ? }

? ? //node表示待修正的節(jié)點(diǎn)，即后繼節(jié)點(diǎn)的子節(jié)點(diǎn)（因?yàn)楹罄^節(jié)點(diǎn)被挪到刪除節(jié)點(diǎn)的位置去了）privatevoidfixUpAfterRemove(Entry node,Entry parent) {

? ? ? ? Entry other;

? ? ? ? while((node ==null|| isBlack(node)) && (node != root)) {

? ? ? ? ? ? if(parent.left == node) {//node是左子節(jié)點(diǎn)，下面else與這里的剛好相反other = parent.right;//node的兄弟節(jié)點(diǎn)if(isRed(other)) {//case1: node的兄弟節(jié)點(diǎn)other是紅色的? ? ? ? ? ? ? ? ? ? setBlack(other);

? ? ? ? ? ? ? ? ? ? setRed(parent);

? ? ? ? ? ? ? ? ? ? leftRotate(parent);

? ? ? ? ? ? ? ? ? ? other = parent.right;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? //case2: node的兄弟節(jié)點(diǎn)other是黑色的，且other的兩個(gè)子節(jié)點(diǎn)也都是黑色的if((other.left ==null|| isBlack(other.left)) &&? ? ? ? ? ? ? ? ? ? ? ? (other.right ==null|| isBlack(other.right))) {

? ? ? ? ? ? ? ? ? ? setRed(other);

? ? ? ? ? ? ? ? ? ? node = parent;

? ? ? ? ? ? ? ? ? ? parent = parentOf(node);

? ? ? ? ? ? ? ? } else {

? ? ? ? ? ? ? ? ? ? //case3: node的兄弟節(jié)點(diǎn)other是黑色的，且other的左子節(jié)點(diǎn)是紅色，右子節(jié)點(diǎn)是黑色if(other.right ==null|| isBlack(other.right)) {

? ? ? ? ? ? ? ? ? ? ? ? setBlack(other.left);

? ? ? ? ? ? ? ? ? ? ? ? setRed(other);

? ? ? ? ? ? ? ? ? ? ? ? rightRotate(other);

? ? ? ? ? ? ? ? ? ? ? ? other = parent.right;

? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? //case4: node的兄弟節(jié)點(diǎn)other是黑色的，且other的右子節(jié)點(diǎn)是紅色，左子節(jié)點(diǎn)任意顏色? ? ? ? ? ? ? ? ? ? setColor(other, colorOf(parent));

? ? ? ? ? ? ? ? ? ? setBlack(parent);

? ? ? ? ? ? ? ? ? ? setBlack(other.right);

? ? ? ? ? ? ? ? ? ? leftRotate(parent);

? ? ? ? ? ? ? ? ? ? node =this.root;

? ? ? ? ? ? ? ? ? ? break;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? } else{//與上面的對(duì)稱other = parent.left;

? ? ? ? ? ? ? ? if (isRed(other)) {

? ? ? ? ? ? ? ? ? ? // Case 1: node的兄弟other是紅色的? ? ? ? ? ? ? ? ? ? setBlack(other);

? ? ? ? ? ? ? ? ? ? setRed(parent);

? ? ? ? ? ? ? ? ? ? rightRotate(parent);

? ? ? ? ? ? ? ? ? ? other = parent.left;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? if((other.left==null|| isBlack(other.left)) &&? ? ? ? ? ? ? ? ? ? ? ? (other.right==null|| isBlack(other.right))) {

? ? ? ? ? ? ? ? ? ? // Case 2: node的兄弟other是黑色，且other的倆個(gè)子節(jié)點(diǎn)都是黑色的? ? ? ? ? ? ? ? ? ? setRed(other);

? ? ? ? ? ? ? ? ? ? node = parent;

? ? ? ? ? ? ? ? ? ? parent = parentOf(node);

? ? ? ? ? ? ? ? } else {

? ? ? ? ? ? ? ? ? ? if(other.left==null|| isBlack(other.left)) {

? ? ? ? ? ? ? ? ? ? ? ? // Case 3: node的兄弟other是黑色的，并且other的左子節(jié)點(diǎn)是紅色，右子節(jié)點(diǎn)為黑色。? ? ? ? ? ? ? ? ? ? ? ? setBlack(other.right);

? ? ? ? ? ? ? ? ? ? ? ? setRed(other);

? ? ? ? ? ? ? ? ? ? ? ? leftRotate(other);

? ? ? ? ? ? ? ? ? ? ? ? other = parent.left;

? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? // Case 4: node的兄弟other是黑色的；并且other的左子節(jié)點(diǎn)是紅色的，右子節(jié)點(diǎn)任意顏色? ? ? ? ? ? ? ? ? ? setColor(other, colorOf(parent));

? ? ? ? ? ? ? ? ? ? setBlack(parent);

? ? ? ? ? ? ? ? ? ? setBlack(other.left);

? ? ? ? ? ? ? ? ? ? rightRotate(parent);

? ? ? ? ? ? ? ? ? ? node =this.root;

? ? ? ? ? ? ? ? ? ? break;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? if(node!=null)

? ? ? ? ? ? setBlack(node);

? ? }

? ? privateEntry successor(Entry delEntry) {

? ? ? ? Entry r = delEntry.right;//assert r != null;while(r.left !=null){

? ? ? ? ? ? r = r.left;

? ? ? ? }

? ? ? ? return r;

? ? }

　　到此，紅黑樹的添加刪除操作已經(jīng)全部講完了，如果文中有什么錯(cuò)誤或不懂得地方，隨時(shí)歡迎大家指出討論。