首先，在閱讀文章之前，我希望讀者對(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í)歡迎大家指出討論绽昏。
