寫在前面
當(dāng)在10億數(shù)據(jù)中只需要進(jìn)行10幾次比較就能查找到目標(biāo)時(shí)，不禁感嘆編程之魅力！人類之偉大呀纲熏！ —— 學(xué)紅黑樹有感。
終于锄俄，在學(xué)習(xí)了幾天的紅黑樹相關(guān)的知識(shí)后局劲，我想把我所學(xué)所想和所感分享給大家。紅黑樹是一種比較難的數(shù)據(jù)結(jié)構(gòu)奶赠，要完全搞懂非常耗時(shí)耗力鱼填，紅黑樹怎么自平衡？什么時(shí)候需要左旋或右旋毅戈？插入和刪除破壞了樹的平衡后怎么處理苹丸？等等一連串的問題在學(xué)習(xí)前困擾著我。如果你在學(xué)習(xí)過程中也會(huì)存在我的疑問苇经，那么本文對(duì)你會(huì)有幫助赘理，本文幫助你全面、徹底地理解紅黑樹扇单！
本文將通過圖文的方式講解紅黑樹的知識(shí)點(diǎn)商模，并且不會(huì)涉及到任何代碼，相信我令花，在懂得紅黑樹實(shí)現(xiàn)原理前，看代碼會(huì)一頭霧水的凉倚，當(dāng)原理懂了兼都，代碼也就按部就班寫而已，沒任何難度稽寒。
閱讀本文你需具備知識(shí)點(diǎn)：
- 二叉查找樹
- 完美平衡二叉樹
事不宜遲扮碧，讓我們進(jìn)入正題吧。
正文
紅黑樹也是二叉查找樹杏糙，我們知道慎王，二叉查找樹這一數(shù)據(jù)結(jié)構(gòu)并不難，而紅黑樹之所以難是難在它是自平衡的二叉查找樹宏侍，在進(jìn)行插入和刪除等可能會(huì)破壞樹的平衡的操作時(shí)赖淤，需要重新自處理達(dá)到平衡狀態(tài)。現(xiàn)在在腦海想下怎么實(shí)現(xiàn)谅河？是不是太多情景需要考慮了咱旱？嘖嘖确丢，先別急，通過本文的學(xué)習(xí)后吐限，你會(huì)覺得鲜侥，其實(shí)也不過如此而已。好吧诸典，我們先來看下紅黑樹的定義和一些基本性質(zhì)描函。
紅黑樹定義和性質(zhì)
紅黑樹是一種含有紅黑結(jié)點(diǎn)并能自平衡的二叉查找樹。它必須滿足下面性質(zhì)：
- 性質(zhì)1：每個(gè)節(jié)點(diǎn)要么是黑色狐粱，要么是紅色舀寓。
- 性質(zhì)2：根節(jié)點(diǎn)是黑色。
- 性質(zhì)3：每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色脑奠。
- 性質(zhì)4：每個(gè)紅色結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)一定都是黑色基公。
- 性質(zhì)5：任意一結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)的路徑都包含數(shù)量相同的黑結(jié)點(diǎn)。
從性質(zhì)5又可以推出：
- 性質(zhì)5.1：如果一個(gè)結(jié)點(diǎn)存在黑子結(jié)點(diǎn)宋欺，那么該結(jié)點(diǎn)肯定有兩個(gè)子結(jié)點(diǎn)
圖1就是一顆簡(jiǎn)單的紅黑樹轰豆。其中Nil為葉子結(jié)點(diǎn)，并且它是黑色的齿诞。(值得提醒注意的是酸休，在Java中，葉子結(jié)點(diǎn)是為null的結(jié)點(diǎn)祷杈。)
紅黑樹并不是一個(gè)完美平衡二叉查找樹斑司，從圖1可以看到，根結(jié)點(diǎn)P的左子樹顯然比右子樹高但汞，但左子樹和右子樹的黑結(jié)點(diǎn)的層數(shù)是相等的宿刮，也即任意一個(gè)結(jié)點(diǎn)到到每個(gè)葉子結(jié)點(diǎn)的路徑都包含數(shù)量相同的黑結(jié)點(diǎn)(性質(zhì)5)。所以我們叫紅黑樹這種平衡為黑色完美平衡私蕾。
介紹到此僵缺，為了后面講解不至于混淆，我們還需要來約定下紅黑樹一些結(jié)點(diǎn)的叫法踩叭，如圖2所示磕潮。
我們把正在處理(遍歷)的結(jié)點(diǎn)叫做當(dāng)前結(jié)點(diǎn)，如圖2中的D容贝，它的父親叫做父結(jié)點(diǎn)自脯，它的父親的另外一個(gè)子結(jié)點(diǎn)叫做兄弟結(jié)點(diǎn)，父親的父親叫做祖父結(jié)點(diǎn)斤富。
前面講到紅黑樹能自平衡膏潮，它靠的是什么？三種操作：左旋满力、右旋和變色戏罢。
- 左旋：以某個(gè)結(jié)點(diǎn)作為支點(diǎn)(旋轉(zhuǎn)結(jié)點(diǎn))屋谭，其右子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)，右子結(jié)點(diǎn)的左子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的右子結(jié)點(diǎn)龟糕，左子結(jié)點(diǎn)保持不變桐磁。如圖3。
- 右旋：以某個(gè)結(jié)點(diǎn)作為支點(diǎn)(旋轉(zhuǎn)結(jié)點(diǎn))讲岁，其左子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)我擂，左子結(jié)點(diǎn)的右子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的左子結(jié)點(diǎn)，右子結(jié)點(diǎn)保持不變缓艳。如圖4校摩。
- 變色：結(jié)點(diǎn)的顏色由紅變黑或由黑變紅。
上面所說的旋轉(zhuǎn)結(jié)點(diǎn)也即旋轉(zhuǎn)的支點(diǎn)阶淘，圖4和圖5中的P結(jié)點(diǎn)衙吩。
我們先忽略顏色，可以看到旋轉(zhuǎn)操作不會(huì)影響旋轉(zhuǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)溪窒，父結(jié)點(diǎn)以上的結(jié)構(gòu)還是保持不變的坤塞。
左旋只影響旋轉(zhuǎn)結(jié)點(diǎn)和其右子樹的結(jié)構(gòu)，把右子樹的結(jié)點(diǎn)往左子樹挪了澈蚌。
右旋只影響旋轉(zhuǎn)結(jié)點(diǎn)和其左子樹的結(jié)構(gòu)摹芙，把左子樹的結(jié)點(diǎn)往右子樹挪了。
所以旋轉(zhuǎn)操作是局部的宛瞄。另外可以看出旋轉(zhuǎn)能保持紅黑樹平衡的一些端詳了：當(dāng)一邊子樹的結(jié)點(diǎn)少了浮禾，那么向另外一邊子樹“借”一些結(jié)點(diǎn)；當(dāng)一邊子樹的結(jié)點(diǎn)多了份汗，那么向另外一邊子樹“租”一些結(jié)點(diǎn)盈电。
但要保持紅黑樹的性質(zhì)，結(jié)點(diǎn)不能亂挪杯活，還得靠變色了匆帚。怎么變？具體情景又不同變法轩猩，后面會(huì)具體講到卷扮，現(xiàn)在只需要記住紅黑樹總是通過旋轉(zhuǎn)和變色達(dá)到自平衡荡澎。
balabala了這么多均践，相信你對(duì)紅黑樹有一定印象了，那么現(xiàn)在來考考你：
思考題1：黑結(jié)點(diǎn)可以同時(shí)包含一個(gè)紅子結(jié)點(diǎn)和一個(gè)黑子結(jié)點(diǎn)嗎摩幔？ (答案見文末)
接下來先講解紅黑樹的查找熱熱身彤委。
紅黑樹查找
因?yàn)榧t黑樹是一顆二叉平衡樹，并且查找不會(huì)破壞樹的平衡或衡，所以查找跟二叉平衡樹的查找無異：
- 從根結(jié)點(diǎn)開始查找焦影，把根結(jié)點(diǎn)設(shè)置為當(dāng)前結(jié)點(diǎn)车遂；
- 若當(dāng)前結(jié)點(diǎn)為空，返回null斯辰；
- 若當(dāng)前結(jié)點(diǎn)不為空舶担，用當(dāng)前結(jié)點(diǎn)的key跟查找key作比較；
- 若當(dāng)前結(jié)點(diǎn)key等于查找key彬呻，那么該key就是查找目標(biāo)衣陶，返回當(dāng)前結(jié)點(diǎn)；
- 若當(dāng)前結(jié)點(diǎn)key大于查找key闸氮，把當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)設(shè)置為當(dāng)前結(jié)點(diǎn)剪况，重復(fù)步驟2；
- 若當(dāng)前結(jié)點(diǎn)key小于查找key蒲跨，把當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)設(shè)置為當(dāng)前結(jié)點(diǎn)译断，重復(fù)步驟2；
如圖5所示或悲。
非常簡(jiǎn)單孙咪，但簡(jiǎn)單不代表它效率不好。正由于紅黑樹總保持黑色完美平衡隆箩，所以它的查找最壞時(shí)間復(fù)雜度為O(2lgN)该贾，也即整顆樹剛好紅黑相隔的時(shí)候。能有這么好的查找效率得益于紅黑樹自平衡的特性捌臊，而這背后的付出杨蛋，紅黑樹的插入操作功不可沒～
紅黑樹插入
插入操作包括兩部分工作：一查找插入的位置；二插入后自平衡理澎。查找插入的父結(jié)點(diǎn)很簡(jiǎn)單逞力，跟查找操作區(qū)別不大：
- 從根結(jié)點(diǎn)開始查找；
- 若根結(jié)點(diǎn)為空糠爬，那么插入結(jié)點(diǎn)作為根結(jié)點(diǎn)寇荧，結(jié)束。
- 若根結(jié)點(diǎn)不為空执隧，那么把根結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)揩抡；
- 若當(dāng)前結(jié)點(diǎn)為null，返回當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)镀琉，結(jié)束峦嗤。
- 若當(dāng)前結(jié)點(diǎn)key等于查找key，那么該key所在結(jié)點(diǎn)就是插入結(jié)點(diǎn)屋摔，更新結(jié)點(diǎn)的值烁设，結(jié)束。
- 若當(dāng)前結(jié)點(diǎn)key大于查找key钓试，把當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)設(shè)置為當(dāng)前結(jié)點(diǎn)装黑，重復(fù)步驟4副瀑；
- 若當(dāng)前結(jié)點(diǎn)key小于查找key，把當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)設(shè)置為當(dāng)前結(jié)點(diǎn)恋谭，重復(fù)步驟4糠睡；
如圖6所示。
ok疚颊，插入位置已經(jīng)找到铜幽，把插入結(jié)點(diǎn)放到正確的位置就可以啦，但插入結(jié)點(diǎn)是應(yīng)該是什么顏色呢串稀？答案是紅色除抛。理由很簡(jiǎn)單，紅色在父結(jié)點(diǎn)（如果存在）為黑色結(jié)點(diǎn)時(shí)母截，紅黑樹的黑色平衡沒被破壞到忽，不需要做自平衡操作。但如果插入結(jié)點(diǎn)是黑色清寇，那么插入位置所在的子樹黑色結(jié)點(diǎn)總是多1喘漏，必須做自平衡。
所有插入情景如圖7所示华烟。
嗯翩迈，插入情景很多呢，8種插入情景盔夜！但情景1负饲、2和3的處理很簡(jiǎn)單，而情景4.2和情景4.3只是方向反轉(zhuǎn)而已喂链，懂得了一種情景就能推出另外一種情景返十，所以總體來看，并不復(fù)雜椭微，后續(xù)我們將一個(gè)一個(gè)情景來看洞坑，把它徹底搞懂。
另外蝇率，根據(jù)二叉樹的性質(zhì)迟杂，除了情景2，所有插入操作都是在葉子結(jié)點(diǎn)進(jìn)行的本慕。這點(diǎn)應(yīng)該不難理解排拷，因?yàn)椴檎也迦胛恢脮r(shí)，我們就是在找子結(jié)點(diǎn)為空的父結(jié)點(diǎn)的间狂。
在開始每個(gè)情景的講解前攻泼，我們還是先來約定下火架，如圖8所示鉴象。
圖8的字母并不代表結(jié)點(diǎn)Key的大小忙菠。I表示插入結(jié)點(diǎn)，P表示插入結(jié)點(diǎn)的父結(jié)點(diǎn)纺弊，S表示插入結(jié)點(diǎn)的叔叔結(jié)點(diǎn)牛欢，PP表示插入結(jié)點(diǎn)的祖父結(jié)點(diǎn)。
好了淆游，下面讓我們一個(gè)一個(gè)來分析每個(gè)插入的情景以其處理傍睹。
插入情景1：紅黑樹為空樹
最簡(jiǎn)單的一種情景，直接把插入結(jié)點(diǎn)作為根結(jié)點(diǎn)就行犹菱，但注意拾稳，根據(jù)紅黑樹性質(zhì)2：根節(jié)點(diǎn)是黑色。還需要把插入結(jié)點(diǎn)設(shè)為黑色腊脱。
處理：把插入結(jié)點(diǎn)作為根結(jié)點(diǎn)访得，并把結(jié)點(diǎn)設(shè)置為黑色。
插入情景2：插入結(jié)點(diǎn)的Key已存在
插入結(jié)點(diǎn)的Key已存在陕凹，既然紅黑樹總保持平衡悍抑，在插入前紅黑樹已經(jīng)是平衡的，那么把插入結(jié)點(diǎn)設(shè)置為將要替代結(jié)點(diǎn)的顏色杜耙，再把結(jié)點(diǎn)的值更新就完成插入搜骡。
處理：
- 把I設(shè)為當(dāng)前結(jié)點(diǎn)的顏色
- 更新當(dāng)前結(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í)佑女，并不會(huì)影響紅黑樹的平衡记靡，直接插入即可，無需做自平衡团驱。
處理：直接插入簸呈。
插入情景4：插入結(jié)點(diǎn)的父結(jié)點(diǎn)為紅結(jié)點(diǎn)
再次回想下紅黑樹的性質(zhì)2：根結(jié)點(diǎn)是黑色。如果插入的父結(jié)點(diǎn)為紅結(jié)點(diǎn)店茶，那么該父結(jié)點(diǎn)不可能為根結(jié)點(diǎn)蜕便，所以插入結(jié)點(diǎn)總是存在祖父結(jié)點(diǎn)。這點(diǎn)很重要贩幻，因?yàn)楹罄m(xù)的旋轉(zhuǎn)操作肯定需要祖父結(jié)點(diǎn)的參與轿腺。
情景4又分為很多子情景，下面將進(jìn)入重點(diǎn)部分丛楚，各位看官請(qǐng)留神了族壳。
插入情景4.1：叔叔結(jié)點(diǎn)存在并且為紅結(jié)點(diǎn)
從紅黑樹性質(zhì)4可以，祖父結(jié)點(diǎn)肯定為黑結(jié)點(diǎn)趣些，因?yàn)椴豢梢酝瑫r(shí)存在兩個(gè)相連的紅結(jié)點(diǎn)仿荆。那么此時(shí)該插入子樹的紅黑層數(shù)的情況是：黑紅紅。顯然最簡(jiǎn)單的處理方式是把其改為：紅黑紅。如圖9和圖10所示拢操。
處理：
- 將P和S設(shè)置為黑色
- 將PP設(shè)置為紅色
- 把PP設(shè)置為當(dāng)前插入結(jié)點(diǎn)
可以看到锦亦，我們把PP結(jié)點(diǎn)設(shè)為紅色了，如果PP的父結(jié)點(diǎn)是黑色令境，那么無需再做任何處理杠园；但如果PP的父結(jié)點(diǎn)是紅色，根據(jù)性質(zhì)4舔庶，此時(shí)紅黑樹已不平衡了抛蚁，所以還需要把PP當(dāng)作新的插入結(jié)點(diǎn)，繼續(xù)做插入操作自平衡處理惕橙，直到平衡為止瞧甩。
試想下PP剛好為根結(jié)點(diǎn)時(shí)，那么根據(jù)性質(zhì)2弥鹦，我們必須把PP重新設(shè)為黑色亲配，那么樹的紅黑結(jié)構(gòu)變?yōu)椋汉诤诩t。換句話說惶凝，從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑中吼虎，黑色結(jié)點(diǎn)增加了。這也是唯一一種會(huì)增加紅黑樹黑色結(jié)點(diǎn)層數(shù)的插入情景苍鲜。
我們還可以總結(jié)出另外一個(gè)經(jīng)驗(yàn)：紅黑樹的生長(zhǎng)是自底向上的思灰。這點(diǎn)不同于普通的二叉查找樹，普通的二叉查找樹的生長(zhǎng)是自頂向下的混滔。
插入情景4.2：叔叔結(jié)點(diǎn)不存在或?yàn)楹诮Y(jié)點(diǎn)洒疚，并且插入結(jié)點(diǎn)的父親結(jié)點(diǎn)是祖父結(jié)點(diǎn)的左子結(jié)點(diǎn)
單純從插入前來看，也即不算情景4.1自底向上處理時(shí)的情況坯屿，叔叔結(jié)點(diǎn)非紅即為葉子結(jié)點(diǎn)(Nil)油湖。因?yàn)槿绻迨褰Y(jié)點(diǎn)為黑結(jié)點(diǎn)，而父結(jié)點(diǎn)為紅結(jié)點(diǎn)领跛，那么叔叔結(jié)點(diǎn)所在的子樹的黑色結(jié)點(diǎn)就比父結(jié)點(diǎn)所在子樹的多了乏德，這不滿足紅黑樹的性質(zhì)5。后續(xù)情景同樣如此吠昭，不再多做說明了喊括。
前文說了，需要旋轉(zhuǎn)操作時(shí)矢棚，肯定一邊子樹的結(jié)點(diǎn)多了或少了郑什，需要租或借給另一邊。插入顯然是多的情況蒲肋，那么把多的結(jié)點(diǎn)租給另一邊子樹就可以了蘑拯。
插入情景4.2.1：插入結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子結(jié)點(diǎn)
處理：
- 將P設(shè)為黑色
- 將PP設(shè)為紅色
- 對(duì)PP進(jìn)行右旋
由圖11可得钝满，左邊兩個(gè)紅結(jié)點(diǎn)，右邊不存在申窘，那么一邊一個(gè)剛剛好弯蚜，并且因?yàn)闉榧t色，肯定不會(huì)破壞樹的平衡偶洋。
咦，可以把PP設(shè)為紅色距糖，I和P設(shè)為黑色嗎玄窝？答案是可以！看過《算法：第4版》的同學(xué)可能知道悍引，書中講解的就是把PP設(shè)為紅色恩脂，I和P設(shè)為黑色。但把PP設(shè)為紅色趣斤，顯然又會(huì)出現(xiàn)情景4.1的情況俩块，需要自底向上處理，做多了無謂的操作浓领，既然能自己消化就不要麻煩祖輩們啦～
插入情景4.2.2：插入結(jié)點(diǎn)是其父結(jié)點(diǎn)的右子結(jié)點(diǎn)
這種情景顯然可以轉(zhuǎn)換為情景4.2.1玉凯，如圖12所示，不做過多說明了联贩。
處理：
- 對(duì)P進(jìn)行左旋
- 把P設(shè)置為插入結(jié)點(diǎn)漫仆，得到情景4.2.1
- 進(jìn)行情景4.2.1的處理
插入情景4.3：叔叔結(jié)點(diǎn)不存在或?yàn)楹诮Y(jié)點(diǎn)，并且插入結(jié)點(diǎn)的父親結(jié)點(diǎn)是祖父結(jié)點(diǎn)的右子結(jié)點(diǎn)
該情景對(duì)應(yīng)情景4.2泪幌，只是方向反轉(zhuǎn)盲厌，不做過多說明了，直接看圖祸泪。
插入情景4.3.1：插入結(jié)點(diǎn)是其父結(jié)點(diǎn)的右子結(jié)點(diǎn)
處理：
- 將P設(shè)為黑色
- 將PP設(shè)為紅色
- 對(duì)PP進(jìn)行左旋
插入情景4.3.2：插入結(jié)點(diǎn)是其父結(jié)點(diǎn)的右子結(jié)點(diǎn)
處理：
- 對(duì)P進(jìn)行右旋
- 把P設(shè)置為插入結(jié)點(diǎn)吗浩，得到情景4.3.1
- 進(jìn)行情景4.3.1的處理
好了，講完插入的所有情景了没隘《螅可能又同學(xué)會(huì)想：上面的情景舉例的都是第一次插入而不包含自底向上處理的情況，那么上面所說的情景都適合自底向上的情況嗎右蒲？答案是肯定的微王。理由很簡(jiǎn)單，但每棵子樹都能自平衡品嚣，那么整棵樹最終總是平衡的炕倘。好吧，在出個(gè)習(xí)題翰撑，請(qǐng)大家拿出筆和紙畫下試試（請(qǐng)務(wù)必動(dòng)手畫下罩旋，加深印象）：
習(xí)題1：請(qǐng)畫出圖15的插入自平衡處理過程啊央。（答案見文末）
紅黑樹刪除
紅黑樹插入已經(jīng)夠復(fù)雜了，但刪除更復(fù)雜涨醋，也是紅黑樹最復(fù)雜的操作了瓜饥。但穩(wěn)住，勝利的曙光就在前面了浴骂！
紅黑樹的刪除操作也包括兩部分工作：一查找目標(biāo)結(jié)點(diǎn)乓土；而刪除后自平衡。查找目標(biāo)結(jié)點(diǎn)顯然可以復(fù)用查找操作溯警，當(dāng)不存在目標(biāo)結(jié)點(diǎn)時(shí)趣苏，忽略本次操作；當(dāng)存在目標(biāo)結(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)找替代結(jié)點(diǎn)有3種情情景：
- 情景1：若刪除結(jié)點(diǎn)無子結(jié)點(diǎn)伊诵，直接刪除
- 情景2：若刪除結(jié)點(diǎn)只有一個(gè)子結(jié)點(diǎn)单绑，用子結(jié)點(diǎn)替換刪除結(jié)點(diǎn)
- 情景3：若刪除結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，用后繼結(jié)點(diǎn)（大于刪除結(jié)點(diǎn)的最小結(jié)點(diǎn)）替換刪除結(jié)點(diǎn)
補(bǔ)充說明下曹宴，情景3的后繼結(jié)點(diǎn)是大于刪除結(jié)點(diǎn)的最小結(jié)點(diǎn)询张，也是刪除結(jié)點(diǎn)的右子樹種最左結(jié)點(diǎn)。那么可以拿前繼結(jié)點(diǎn)（刪除結(jié)點(diǎn)的左子樹最左結(jié)點(diǎn)）替代嗎浙炼？可以的份氧。但習(xí)慣上大多都是拿后繼結(jié)點(diǎn)來替代，后文的講解也是用后繼結(jié)點(diǎn)來替代弯屈。另外告訴大家一種找前繼和后繼結(jié)點(diǎn)的直觀的方法（不知為何沒人提過蜗帜，大家都知道？）：把二叉樹所有結(jié)點(diǎn)投射在X軸上资厉，所有結(jié)點(diǎn)都是從左到右排好序的厅缺，所有目標(biāo)結(jié)點(diǎn)的前后結(jié)點(diǎn)就是對(duì)應(yīng)前繼和后繼結(jié)點(diǎn)。如圖16所示宴偿。
接下來湘捎，講一個(gè)重要的思路：刪除結(jié)點(diǎn)被替代后，在不考慮結(jié)點(diǎn)的鍵值的情況下窄刘，對(duì)于樹來說窥妇，可以認(rèn)為刪除的是替代結(jié)點(diǎn)！話很蒼白娩践，我們看圖17活翩。在不看鍵值對(duì)的情況下烹骨，圖17的紅黑樹最終結(jié)果是刪除了Q所在位置的結(jié)點(diǎn)！這種思路非常重要材泄，大大簡(jiǎn)化了后文講解紅黑樹刪除的情景沮焕！
基于此，上面所說的3種二叉樹的刪除情景可以相互轉(zhuǎn)換并且最終都是轉(zhuǎn)換為情景1拉宗！
- 情景2：刪除結(jié)點(diǎn)用其唯一的子結(jié)點(diǎn)替換峦树，子結(jié)點(diǎn)替換為刪除結(jié)點(diǎn)后，可以認(rèn)為刪除的是子結(jié)點(diǎn)旦事，若子結(jié)點(diǎn)又有兩個(gè)子結(jié)點(diǎn)笔时，那么相當(dāng)于轉(zhuǎn)換為情景3垮兑，一直自頂向下轉(zhuǎn)換十绑，總是能轉(zhuǎn)換為情景1呼奢。（對(duì)于紅黑樹來說化戳，根據(jù)性質(zhì)5.1单料，只存在一個(gè)子結(jié)點(diǎn)的結(jié)點(diǎn)肯定在樹末了）
- 情景3：刪除結(jié)點(diǎn)用后繼結(jié)點(diǎn)（肯定不存在左結(jié)點(diǎn)），如果后繼結(jié)點(diǎn)有右子結(jié)點(diǎn)点楼，那么相當(dāng)于轉(zhuǎn)換為情景2扫尖，否則轉(zhuǎn)為為情景1。
二叉樹刪除結(jié)點(diǎn)情景關(guān)系圖如圖18所示掠廓。
綜上所述换怖，刪除操作刪除的結(jié)點(diǎn)可以看作刪除替代結(jié)點(diǎn)，而替代結(jié)點(diǎn)最后總是在樹末蟀瞧。有了這結(jié)論沉颂，我們討論的刪除紅黑樹的情景就少了很多，因?yàn)槲覀冎豢紤]刪除樹末結(jié)點(diǎn)的情景了悦污。
同樣的铸屉，我們也是先來總體看下刪除操作的所有情景，如圖19所示切端。
哈哈彻坛，是的，即使簡(jiǎn)化了還是有9種情景踏枣！但跟插入操作一樣昌屉，存在左右對(duì)稱的情景，只是方向變了茵瀑，沒有本質(zhì)區(qū)別间驮。同樣的，我們還是來約定下马昨，如圖20所示蜻牢。
圖20的字母并不代表結(jié)點(diǎn)Key的大小烤咧。R表示替代結(jié)點(diǎn)，P表示替代結(jié)點(diǎn)的父結(jié)點(diǎn)抢呆，S表示替代結(jié)點(diǎn)的兄弟結(jié)點(diǎn)煮嫌，SL表示兄弟結(jié)點(diǎn)的左子結(jié)點(diǎn)，SR表示兄弟結(jié)點(diǎn)的右子結(jié)點(diǎn)抱虐〔ⅲ灰色結(jié)點(diǎn)表示它可以是紅色也可以是黑色。
值得特別提醒的是恳邀，R是即將被替換到刪除結(jié)點(diǎn)的位置的替代結(jié)點(diǎn)懦冰，在刪除前，它還在原來所在位置參與樹的子平衡谣沸，平衡后再替換到刪除結(jié)點(diǎn)的位置刷钢，才算刪除完成。
萬事具備乳附，我們進(jìn)入最后的也是最難的講解内地。
刪除情景1：替換結(jié)點(diǎn)是紅色結(jié)點(diǎn)
我們把替換結(jié)點(diǎn)換到了刪除結(jié)點(diǎn)的位置時(shí)，由于替換結(jié)點(diǎn)時(shí)紅色赋除，刪除也了不會(huì)影響紅黑樹的平衡阱缓，只要把替換結(jié)點(diǎn)的顏色設(shè)為刪除的結(jié)點(diǎn)的顏色即可重新平衡。
處理：顏色變?yōu)閯h除結(jié)點(diǎn)的顏色
刪除情景2：替換結(jié)點(diǎn)是黑結(jié)點(diǎn)
當(dāng)替換結(jié)點(diǎn)是黑色時(shí)举农，我們就不得不進(jìn)行自平衡處理了荆针。我們必須還得考慮替換結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子結(jié)點(diǎn)還是右子結(jié)點(diǎn)，來做不同的旋轉(zhuǎn)操作颁糟，使樹重新平衡航背。
刪除情景2.1：替換結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子結(jié)點(diǎn)
刪除情景2.1.1：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)是紅結(jié)點(diǎn)
若兄弟結(jié)點(diǎn)是紅結(jié)點(diǎn)，那么根據(jù)性質(zhì)4棱貌，兄弟結(jié)點(diǎn)的父結(jié)點(diǎn)和子結(jié)點(diǎn)肯定為黑色玖媚，不會(huì)有其他子情景，我們按圖21處理键畴，得到刪除情景2.1.2.3（后續(xù)講解最盅，這里先記住，此時(shí)R仍然是替代結(jié)點(diǎn)起惕，它的新的兄弟結(jié)點(diǎn)SL和兄弟結(jié)點(diǎn)的子結(jié)點(diǎn)都是黑色）涡贱。
處理：
- 將S設(shè)為黑色
- 將P設(shè)為紅色
- 對(duì)P進(jìn)行左旋，得到情景2.1.2.3
- 進(jìn)行情景2.1.2.3的處理
刪除情景2.1.2：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)是黑結(jié)點(diǎn)
當(dāng)兄弟結(jié)點(diǎn)為黑時(shí)惹想，其父結(jié)點(diǎn)和子結(jié)點(diǎn)的具體顏色也無法確定（如果也不考慮自底向上的情況问词，子結(jié)點(diǎn)非紅即為葉子結(jié)點(diǎn)Nil，Nil結(jié)點(diǎn)為黑結(jié)點(diǎn)）嘀粱，此時(shí)又得考慮多種子情景激挪。
刪除情景2.1.2.1：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)的右子結(jié)點(diǎn)是紅結(jié)點(diǎn)辰狡，左子結(jié)點(diǎn)任意顏色
即將刪除的左子樹的一個(gè)黑色結(jié)點(diǎn)，顯然左子樹的黑色結(jié)點(diǎn)少1了垄分，然而右子樹又又紅色結(jié)點(diǎn)宛篇，那么我們直接向右子樹“借”個(gè)紅結(jié)點(diǎn)來補(bǔ)充黑結(jié)點(diǎn)就好啦，此時(shí)肯定需要用旋轉(zhuǎn)處理了薄湿。如圖22所示叫倍。
處理：
- 將S的顏色設(shè)為P的顏色
- 將P設(shè)為黑色
- 將SR設(shè)為黑色
- 對(duì)P進(jìn)行左旋
平衡后的圖怎么不滿足紅黑樹的性質(zhì)？前文提醒過豺瘤，R是即將替換的吆倦，它還參與樹的自平衡，平衡后再替換到刪除結(jié)點(diǎn)的位置坐求，所以R最終可以看作是刪除的蚕泽。另外圖2.1.2.1是考慮到第一次替換和自底向上處理的情況，如果只考慮第一次替換的情況桥嗤，根據(jù)紅黑樹性質(zhì)须妻，SL肯定是紅色或?yàn)镹il，所以最終結(jié)果樹是平衡的砸逊。如果是自底向上處理的情況璧南，同樣掌逛，每棵子樹都保持平衡狀態(tài)师逸，最終整棵樹肯定是平衡的。后續(xù)的情景同理豆混，不做過多說明了篓像。
刪除情景2.1.2.2：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)的右子結(jié)點(diǎn)為黑結(jié)點(diǎn)，左子結(jié)點(diǎn)為紅結(jié)點(diǎn)
兄弟結(jié)點(diǎn)所在的子樹有紅結(jié)點(diǎn)皿伺，我們總是可以向兄弟子樹借個(gè)紅結(jié)點(diǎn)過來员辩，顯然該情景可以轉(zhuǎn)換為情景2.1.2.1。圖如23所示鸵鸥。
處理：
- 將S設(shè)為紅色
- 將SL設(shè)為黑色
- 對(duì)S進(jìn)行右旋奠滑，得到情景2.1.2.1
- 進(jìn)行情景2.1.2.1的處理
刪除情景2.1.2.3：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)的子結(jié)點(diǎn)都為黑結(jié)點(diǎn)
好了，此次兄弟子樹都沒紅結(jié)點(diǎn)“借”了妒穴，兄弟幫忙不了宋税，找父母唄，這種情景我們把兄弟結(jié)點(diǎn)設(shè)為紅色讼油，再把父結(jié)點(diǎn)當(dāng)作替代結(jié)點(diǎn)杰赛，自底向上處理，去找父結(jié)點(diǎn)的兄弟結(jié)點(diǎn)去“借”矮台。但為什么需要把兄弟結(jié)點(diǎn)設(shè)為紅色呢乏屯？顯然是為了在P所在的子樹中保證平衡（R即將刪除根时，少了一個(gè)黑色結(jié)點(diǎn)，子樹也需要少一個(gè)）辰晕，后續(xù)的平衡工作交給父輩們考慮了蛤迎，還是那句，當(dāng)每棵子樹都保持平衡時(shí)含友，最終整棵總是平衡的忘苛。
處理：
- 將S設(shè)為紅色
- 把P作為新的替換結(jié)點(diǎn)
- 重新進(jìn)行刪除結(jié)點(diǎn)情景處理
刪除情景2.2：替換結(jié)點(diǎn)是其父結(jié)點(diǎn)的右子結(jié)點(diǎn)
好啦，右邊的操作也是方向相反唱较，不做過多說明了扎唾，相信理解了刪除情景2.1后，肯定可以理解2.2南缓。
刪除情景2.2.1：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)是紅結(jié)點(diǎn)
處理：
- 將S設(shè)為黑色
- 將P設(shè)為紅色
- 對(duì)P進(jìn)行右旋胸遇，得到情景2.2.2.3
- 進(jìn)行情景2.2.2.3的處理
刪除情景2.2.2：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)是黑結(jié)點(diǎn)
刪除情景2.2.2.1：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)的左子結(jié)點(diǎn)是紅結(jié)點(diǎn)，右子結(jié)點(diǎn)任意顏色
處理：
- 將S的顏色設(shè)為P的顏色
- 將P設(shè)為黑色
- 將SL設(shè)為黑色
- 對(duì)P進(jìn)行右旋
刪除情景2.2.2.2：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)的左子結(jié)點(diǎn)為黑結(jié)點(diǎn)汉形，右子結(jié)點(diǎn)為紅結(jié)點(diǎn)
處理：
- 將S設(shè)為紅色
- 將SR設(shè)為黑色
- 對(duì)S進(jìn)行左旋纸镊，得到情景2.2.2.1
- 進(jìn)行情景2.2.2.1的處理
刪除情景2.2.2.3：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)的子結(jié)點(diǎn)都為黑結(jié)點(diǎn)
處理：
- 將S設(shè)為紅色
- 把P作為新的替換結(jié)點(diǎn)
- 重新進(jìn)行刪除結(jié)點(diǎn)情景處理
綜上，紅黑樹刪除后自平衡的處理可以總結(jié)為：
- 自己能搞定的自消化（情景1）
- 自己不能搞定的叫兄弟幫忙（除了情景1概疆、情景2.1.2.3和情景2.2.2.3）
- 兄弟都幫忙不了的逗威，通過父母，找遠(yuǎn)方親戚（情景2.1.2.3和情景2.2.2.3）
哈哈岔冀，是不是跟現(xiàn)實(shí)中很像凯旭，當(dāng)我們有困難時(shí)，首先先自己解決使套，自己無力了總兄弟姐妹幫忙罐呼，如果連兄弟姐妹都幫不上，再去找遠(yuǎn)方的親戚了侦高。這里記憶應(yīng)該會(huì)好記點(diǎn)～
最后再做個(gè)習(xí)題加深理解（請(qǐng)不熟悉的同學(xué)務(wù)必動(dòng)手畫下）：
***習(xí)題2：請(qǐng)畫出圖29的刪除自平衡處理過程嫉柴。
寫在后面
耗時(shí)良久，終于寫完了～自己加深了紅黑樹的理解的同時(shí)奉呛，也希望能幫助大家计螺。如果你之前沒學(xué)習(xí)過紅黑樹，看完這篇文章后可能還存在很多疑問瞧壮，如果有疑問可以在評(píng)論區(qū)寫出來登馒，我會(huì)盡自己所能解答。另外給大家推薦一個(gè)支持紅黑樹在線生成的網(wǎng)站馁痴，來做各種情景梳理很有幫助：在線生成紅黑樹谊娇。（刪除操作那個(gè)把替代結(jié)點(diǎn)看作刪除結(jié)點(diǎn)思路就是我自己在用這個(gè)網(wǎng)站時(shí)自己頓悟的，我覺得這樣講解更容易理解。）
少了代碼是不是覺得有點(diǎn)空虛济欢？哈哈赠堵，后續(xù)我會(huì)寫關(guān)于Java和HashMap和TreeMap的文章，里面都有紅黑樹相關(guān)的知識(shí)法褥。相信看了這篇文章后茫叭，再去看Java和HashMap和TreeMap的源碼絕對(duì)沒難度！
最后來看下思考題和習(xí)題的答案吧半等。
思考題和習(xí)題答案
思考題1：黑結(jié)點(diǎn)可以同時(shí)包含一個(gè)紅子結(jié)點(diǎn)和一個(gè)黑子結(jié)點(diǎn)嗎揍愁？
答：可以。如下圖的F結(jié)點(diǎn)：
習(xí)題1：請(qǐng)畫出圖15的插入自平衡處理過程杀饵。
答：
習(xí)題2：請(qǐng)畫出圖29的刪除自平衡處理過程莽囤。
答：
