一. 算法之變，結(jié)構(gòu)為宗
計算機在很多情況下被應(yīng)用于檢索數(shù)據(jù)望众，比如航空和鐵路運輸業(yè)的航班信息和列車時刻表的查詢万栅，都要求快速地找到用戶所需要的信息佑钾。所以，對于存儲大量信息的計算機來說烦粒，能“大量存”固然好休溶，但同時還必須能“快速取”才行。又比如扰她，我們在使用C++或者Java這樣的編程語言時兽掰，都會用到標(biāo)準(zhǔn)模版類庫，因為它們簡潔高效徒役，能提供動態(tài)增長的各類數(shù)據(jù)結(jié)構(gòu)孽尽，極大地提高了開發(fā)效率，同時又保證了健壯性忧勿。那么杉女，再深入一點看這個問題，究竟是什么“神秘的力量”狐蜕，在持續(xù)地彰顯這些卓越的“行為”呢宠纯？
答案是：“結(jié)構(gòu)模式影響行為”。
“當(dāng)置身于同一個系統(tǒng)時层释，其中的事物無論有多大差別婆瓜，都傾向于產(chǎn)生相似的行為結(jié)果」备幔”
所以你看廉白，在這些高效卓越的檢索能力背后，一定存在著一個隱藏在事物表面以下的“結(jié)構(gòu)”乖寒，正是因為這個內(nèi)部結(jié)構(gòu)的存在影響著外部行為的表現(xiàn)猴蹂，不同的結(jié)構(gòu)產(chǎn)生不同的影響力，當(dāng)然也就有好壞之分楣嘁。
“萬變不離其宗”磅轻，很多時候我們在學(xué)習(xí)和積累的過程中，特別是遇到很多很“復(fù)雜”的問題時逐虚，總是有著一種深深的挫敗感聋溜，這種巨大的挫敗感，來自于我們無法把握瞬息萬變的外在行為叭爱。變化的永遠(yuǎn)是外部的行為撮躁，不變的永遠(yuǎn)是內(nèi)部影響這些行為的結(jié)構(gòu)。因此买雾，我們必須拋開讓人眼花繚亂的外部行為把曼，去洞察事物的內(nèi)部結(jié)構(gòu)杨帽，去把握這個“宗”，這往往有著意想不到的收獲嗤军。
為了提高搜索效率注盈，人們想到了用二叉搜索樹（Binary Search Tree）這樣的非線性數(shù)據(jù)結(jié)構(gòu)來存儲數(shù)據(jù)，每次檢索數(shù)據(jù)時根據(jù)關(guān)鍵字的大小選擇是往左子樹走還是往右子樹走型雳，這樣每次都少比較了一半的數(shù)據(jù)当凡，這樣就比線性搜索效率高了山害。但是纠俭，采用“樹”的數(shù)據(jù)結(jié)構(gòu)，就產(chǎn)生了這樣一種行為影響：檢索的過程是跟著樹的路徑往下走的浪慌，因此樹的高度會對效率產(chǎn)生影響冤荆，如果恰巧某個搜索路徑比較“深”，那么查找就比較費時間了权纤，因此不能保證在所有情況下都有很好的效率钓简，打個比方，如果將事先已排好序的序列作為輸入建立一棵二叉搜索樹汹想，那么得到的結(jié)構(gòu)可能就變成了圖1所示這個樣子：
如果在這樣的BST上搜索數(shù)據(jù)外邓，其效率就變成了O(n)，就變得很壞古掏。那么自然就有了一種想法：能不能在BST的結(jié)構(gòu)上進(jìn)行某種“改進(jìn)”损话，讓它的根結(jié)點到樹中任意葉結(jié)點的路徑都差不多一樣長呢？如果能做到這樣的優(yōu)化結(jié)構(gòu)槽唾，那么其所表現(xiàn)出來的行為（也就是搜索效率）必然會得到改善和提高丧枪。2-3-4樹正是在這樣的背景下提出的。
二. 平衡之美：2-3-4樹
2-3-4樹有完美的平衡性能——根結(jié)點到任意葉子結(jié)點的路徑長度相等庞萍∨》常“2-3-4樹”名稱的來歷是因為這棵樹包含了三種結(jié)點：2-node、3-node和4-node钝计。
- 2-node：有1個關(guān)鍵字恋博，2個子結(jié)點；
- 3-node：有2個關(guān)鍵字私恬，3個子結(jié)點债沮；
- 4-node：有3個關(guān)鍵字，4個子結(jié)點践付。
如圖2-1秦士，2-node的左孩子關(guān)鍵字小于W，右孩子關(guān)鍵字大于W永高；圖2-2中孩子結(jié)點從左到右隧土，分別是小于C提针，介于C和E之間以及大于E的；圖2-3中的4-node類似曹傀。
2.1 2-3-4樹的查找操作
先看查找操作辐脖，查找的過程就是比對關(guān)鍵字大小，然后沿著某一路徑向下搜索皆愉，直到找到對應(yīng)結(jié)點嗜价，或者當(dāng)找不到時返回“空”，如圖2-4所示幕庐。
2.2 2-3-4樹的插入操作
現(xiàn)在來看看插入操作：首先仍然是按照關(guān)鍵字大小沿著樹的路徑向下久锥，當(dāng)?shù)竭_(dá)2-node或者3-node時，直接“擴充”這個結(jié)點——2-node擴充成3-node异剥，3-node擴充成4-node瑟由，如圖2-5，2-6冤寿，2-7歹苦，2-8所示。
但是督怜，如果插入的位置落在一個4-node內(nèi)殴瘦，就出現(xiàn)問題了，因為我們既不能把4-node再擴充成5-node号杠，也不能把新加入的結(jié)點直接掛在這個4-node下蚪腋，因為這樣就破壞了2-3-4樹完美的平衡性質(zhì)——根到任意葉結(jié)點的路徑相同，如圖2-9所示究流。
那么遇到這種情況怎么辦呢？我們的解決辦法是采取分解（split）策略——將4-node的3個關(guān)鍵字中間那個“向上提”芬探，把它合并到這個4-node的父結(jié)點中神得，這個4-node被分解為兩個2-node，如圖2-10所示偷仿。
然后，我們再將關(guān)鍵字為H的結(jié)點插入酝静，即得到了圖2-11所示的樣子节榜，注意，此時2-3-4樹的完美性質(zhì)仍然保持别智。
但是新的問題又產(chǎn)生了喔宗苍！仔細(xì)想想，如果圖2-12這種兩個4-node連接在一起的情況發(fā)生了該怎么辦。
有兩種策略解決這個問題——分別稱為Top-down和Bottom-up讳窟。
Bottom-up策略是让歼，如果分解4-node時發(fā)現(xiàn)它的父結(jié)點仍然是4-node，就繼續(xù)分解丽啡，如果有必要的話谋右，這個過程一直持續(xù)往上走，直到到達(dá)根結(jié)點為止补箍，它是“自底向上”的分解策略改执。
Top-down策略是，在執(zhí)行插入操作時坑雅，沿樹往下走的路徑上辈挂，只要發(fā)現(xiàn)4-node，就對其進(jìn)行分解霞丧，并在底部插入新結(jié)點呢岗，它是“自頂向下”的策略。
這里我們采用Top-down策略蛹尝，也就是說，在沿著樹向下的過程中悉尾，只要發(fā)現(xiàn)4-node就將其分解突那，因此我們就保證了當(dāng)前結(jié)點一定不是4-node，這樣就保證了圖8這種情況不會出現(xiàn)构眯，并且我們最后能落在2-node和3-node中愕难，如圖2-13所示。
這樣的分解操作只涉及當(dāng)前結(jié)點和其父結(jié)點惫霸，因此是局部的操作猫缭，不會將調(diào)整結(jié)點的影響擴散到其他地方，這里的這個“分解”的概念很重要壹店，一定要認(rèn)真體會和理解猜丹，這牽涉到后面對紅黑樹很多調(diào)整操作的理解，其實紅黑樹的各種調(diào)整操作其本質(zhì)都來源于2-3-4樹硅卢。
好了射窒，寫到這里，如果你真正理解了“分解”的概念以及為什么要分解将塑，那么我們就來看一個具體的例子脉顿，如圖2-14，2-15所示点寥，輸入序列為“ASERCDINBX”,建立一棵2-3-4樹的過程艾疟，注意在插入R，N，B和X這四個關(guān)鍵字時都發(fā)生了4-node的分解蔽莱，其中前三個關(guān)鍵字是因為所插入的結(jié)點落在4-node中误褪，必須分解；最后一個關(guān)鍵字是因為在沿著樹根向下的過程中遇到4-node了碾褂，對其進(jìn)行分解（還記得Top-down策略嗎）兽间。
2.3 完美平衡的2-3-4樹
一棵稍微復(fù)雜一些的2-3-4樹如圖2-16所示，這種完美的平衡感正塌，保證了根到任一葉結(jié)點的路徑不會比其他路徑長得太多嘀略，也就保證了搜索和插入操作能夠在對數(shù)時間內(nèi)完成，最壞情況下（全是2-node）乓诽，其漸進(jìn)時間復(fù)雜度為lgN帜羊，最好情況下（全是4-node），其漸進(jìn)時間復(fù)雜度為log4(N)=1/2lgN鸠天，10到20次操作就能完成對100讼育，0000個結(jié)點的搜索和插入操作。這就是“優(yōu)美”的結(jié)構(gòu)所產(chǎn)生的卓越能力稠集。
但是奶段，不要高興得太早了，凡事有得必有失剥纷，2-3-4樹的性能雖然接近完美痹籍，但是實現(xiàn)起來卻很困難，原因很簡單——要實現(xiàn)這三種結(jié)點晦鞋，還要實現(xiàn)三種結(jié)點之間的相互轉(zhuǎn)換相當(dāng)困難蹲缠。實際上，2-3-4樹的理論意義要強于實際意義悠垛，因為還有一種著名的數(shù)據(jù)結(jié)構(gòu)也是從2-3-4樹衍生出來的线定，那就是在數(shù)據(jù)庫領(lǐng)域使用非常多的“B樹”，那么确买，面對這樣一種完美的數(shù)據(jù)結(jié)構(gòu)斤讥，我們是不是束手無策了呢？也不見得拇惋，下面周偎，就輪到紅黑樹登場了。
三. 紅黑樹的崛起
從某種意義上說撑帖，紅黑樹是2-3-4樹的一種“精神表達(dá)”蓉坎，其實這也不奇怪，只有神才能創(chuàng)造出完美無瑕的事物胡嘿，作為人類蛉艾，要將完美的東西變成現(xiàn)實，必須根據(jù)實際情況稍作修改和犧牲。不先弄懂2-3-4樹勿侯，是很難理解紅黑樹的各種操作的拓瞪，但是如果理解了2-3-4樹，你就能明白助琐，紛繁復(fù)雜的紅黑樹旋轉(zhuǎn)和顏色翻轉(zhuǎn)的操作其實就是為了恢復(fù)因插入或刪除結(jié)點而造成的2-3-4樹性質(zhì)的破壞祭埂，所以，在我們進(jìn)入具體的紅黑樹討論之前兵钮，如果你對2-3-4樹還有什么不了解的地方蛆橡，請不要急躁毫炉，再回過頭去好好看看前面的敘述骨望；如果你準(zhǔn)備好了，那么我們開始走進(jìn)紅黑樹吧搁凸。
3.1 紅黑樹的基本性質(zhì)
《算法導(dǎo)論》一書敘述了紅黑樹的經(jīng)典五條性質(zhì)：
“一棵二叉查找樹如果滿足下面的紅黑性質(zhì)葱轩，則為一棵紅黑樹：
- 每個結(jié)點是紅的睦焕，或是黑的；
- 根結(jié)點是黑的靴拱；
- 每個葉結(jié)點（NIL）是黑的垃喊；
- 如果一個結(jié)點是紅的，則它的兩個兒子都是黑的缭嫡；
- 對每個結(jié)點缔御，從該結(jié)點到其子孫結(jié)點的所有路徑上包含相同數(shù)目的黑結(jié)點。”
其實妇蛀，如果自己總結(jié)一下，紅黑樹的性質(zhì)大概可以歸納成以下4條：
- 要么紅笤成，要么黑评架；
- 一頭一尾都是黑；
- 有紅必有黑炕泳；
- 任意路徑上黑結(jié)點個數(shù)穩(wěn)定纵诞。
你也許會認(rèn)為，這就是紅黑樹的本質(zhì)了培遵，的確《算法導(dǎo)論》一書對紅黑樹所有操作的敘述浙芙，其實就是在保持上面紅黑樹的五條性質(zhì)，但是這本書卻沒有回答兩個問題：
- 為什么要對結(jié)點進(jìn)行染色籽腕？
- 為什么染色后的二叉查找樹的效率就提高了嗡呼？
3.2 紅黑樹的本質(zhì)
不搞懂2-3-4樹，你永遠(yuǎn)無從知曉這個問題的答案』屎模現(xiàn)在南窗，讓我來告訴你什么是紅黑樹的本質(zhì)。
紅黑樹的真正本質(zhì)是要將2-3-4樹“表達(dá)”成二叉搜索樹，2-3-4樹有三類不同的結(jié)點万伤，二叉搜索樹只有一類結(jié)點——2-node窒悔，因此主要的問題，就是考慮怎么把3-node和4-node“表達(dá)”成2-node敌买，而“紅邊”的引入简珠，使這個問題的解決成為可能。事實上虹钮，在一棵紅黑樹中聋庵，結(jié)點是無所謂紅色還是黑色的，被染色的不是結(jié)點芜抒，而是連接結(jié)點的邊珍策！，讀過《算法導(dǎo)論》的同學(xué)都知道宅倒，書上對紅黑樹的描述都是說對結(jié)點染色攘宙，但是真正的紅黑樹其實是對邊區(qū)分紅色和黑色，因為我們在實現(xiàn)具體的數(shù)據(jù)結(jié)構(gòu)時拐迁，主要是實現(xiàn)結(jié)點的數(shù)據(jù)域蹭劈，而邊的關(guān)系是通過指針來描述的，因此就把邊的顏色值放到結(jié)點的域中线召。
- 當(dāng)我們說一個結(jié)點是紅色時铺韧，實際上是指連接它的邊是紅色；
- 當(dāng)我們說一個結(jié)點是黑色時缓淹，實際上是指連接它的邊是黑色哈打。
3.3 紅黑樹與2-3-4樹的基本對應(yīng)關(guān)系
好了，前面的鋪墊有了讯壶，我們回到正題——紅黑樹是怎么把2-3-4樹中的3-node和4-node表達(dá)成2-node的料仗？答案是：通過“紅邊”。也就是說伏蚊，紅邊是“內(nèi)部邊”立轧，黑邊是“外部邊”，紅黑樹中的黑邊與2-3-4樹中的邊一一對應(yīng)躏吊；而紅黑樹中的紅邊在2-3-4樹中看不見——因為紅邊是3-node和4-node的內(nèi)部邊氛改。這個概念很重要，后面還要再次提到它比伏，所以請你把她記在心里胜卤。引入紅邊后，3-node和4-node就被表達(dá)成如圖3-1凳怨，3-2這樣的BST結(jié)構(gòu)瑰艘。
于是是鬼，通過紅邊和黑邊的幫助，我們就在紅黑樹和2-3-4樹之間建立了一個對應(yīng)關(guān)系（請注意紫新，只是對應(yīng)關(guān)系均蜜，我沒有說是“一一對應(yīng)”關(guān)系，其實如果細(xì)心觀察的話芒率，這個從圖3-1中你就可以看出來了囤耳，這會引出后面一個問題的討論）。一棵2-3-4樹在經(jīng)過紅黑邊的詮釋過后偶芍，就成了圖3-3中的這個樣子充择。
（*注：我覺得這張圖是錯的，右子樹應(yīng)該是G在上面匪蟀，F(xiàn)在左下椎麦，J在右下才對，下圖也是同樣的問題材彪，不過將就用吧观挎，心里有數(shù)就好了。）
這并不是唯一的表達(dá)方式段化，事實上嘁捷，同一棵2-3-4樹還有以下三種表達(dá)，如圖3-4所示显熏。
這可就麻煩了啊雄嚣，2-3-4樹和紅黑樹居然沒有一一對應(yīng)！那得考慮多少種不同的等價情況啊喘蟆，有的情況完全是左右對稱的——這也是《算法導(dǎo)論》一書讓人費解的原因缓升，因為大量的代碼都用來處理各種情況了，所以讀起來讓人甚是費解和疑惑蕴轨。但是仔細(xì)觀察仔沿，這四種不同表達(dá)的關(guān)鍵因素在哪？就是紅邊尺棋！紅邊可以左斜（Left-Leaning），又可以右斜（Right-Leaning）绵跷，所以導(dǎo)致4種情況的組合（根據(jù)概率論的乘法原理）膘螟，所以，為了消除這些不必要的復(fù)雜情況碾局，我們只研究其中一種：左旋紅黑樹荆残。
四. 左旋紅黑樹（LLRB）
于是左斜紅黑樹（Left-Leaning Red Black Tree）登場了。左斜紅黑樹中净当，所有的3-node其內(nèi)部的紅邊都是向左傾斜的内斯，這就是LLRB名稱的由來蕴潦，如圖4-1所示。
這樣我們不僅保證了完美的黑邊平衡（因為它本質(zhì)上是2-3-4樹）俘闯，同時也保證了2-3-4樹與其紅黑表示的一一對應(yīng)關(guān)系潭苞，如圖4-2所示。
呃真朗，讀到這里大家肯定會有個疑問此疹，2-3-4樹看起來是挺漂亮的，但是咋一看紅黑樹里的紅邊怎么這么扎眼罢谏簟蝗碎？2-3-4樹的紅黑表示似乎讓樹“變高”了，那么同學(xué)們肯定會問：紅黑樹還能保持2-3-4樹的對數(shù)時間效率么旗扑？
4.1 搜索效率的數(shù)學(xué)證明
讓我們用一點點數(shù)學(xué)分析來回答這個問題吧蹦骑。
引理：一棵有n個內(nèi)結(jié)點的紅黑樹的高度至多為2lg(n+1)。
這個定理由《算法導(dǎo)論》一書引出 臀防，看起來特別的抽象眠菇，不好理解，不過沒關(guān)系清钥，下面就由我?guī)ьI(lǐng)各位來體驗一把書上的證明琼锋，我會把書上一些寫的不清不楚、一筆帶過的東西重新詮釋一下祟昭，這樣這個定理就不難理解啦缕坎！
那么要證明這個定理呢，我們需要另外一個工具篡悟，描述如下：
“對以x為根的子樹谜叹，它所包含的內(nèi)部結(jié)點數(shù)至少為2^[bh(x)]-1（2的bh(x)次方然后再減一）“嵩幔”這里bh(x)被定義為結(jié)點x的黑高度荷腊，就是說，從結(jié)點x（不包括它本身）到它任一個葉結(jié)點的路徑上所有黑色結(jié)點的個數(shù)急凰。
這里我們用數(shù)學(xué)歸納法來證明這個工具女仰。
- 基本步：若x高度為0，那么它就是一葉子結(jié)點抡锈，它確實至少包含2^0-1=0個內(nèi)部結(jié)點疾忍，基本步證明完畢；
- 歸納步：假設(shè)x為紅黑樹的某一內(nèi)部結(jié)點床三，且它高度h>0一罩，那么它的黑高度就是bh(x)，但是它的兩個孩子結(jié)點呢撇簿？這個就根據(jù)它們的顏色來判斷了：
如果x有一個紅色的孩子y聂渊，那么y的黑高度bh(y)=bh(x)差购，看看上面對黑高度的定義你就明白了——既然它是紅色的，那么它的黑高度就應(yīng)該和它父親的黑高度是一樣的汉嗽；
如果x有一個黑色的孩子z欲逃，那么z的黑高度bh(z)=bh(x)-1，這個怎么解釋呢诊胞，因為它自己就是個黑結(jié)點暖夭，那么在計算它的黑高度時，必須把它自己排除在外（還是根據(jù)定義）撵孤，所以它是bh(x)-1迈着。
現(xiàn)在關(guān)鍵的來了：x的孩子結(jié)點所構(gòu)成的子樹的高度肯定小于x這顆子樹，那么對于這兩個孩子邪码，不管它們顏色如何裕菠，一定滿足歸納假設(shè)的，所以闭专，對x來說奴潘，它所包含的內(nèi)部結(jié)點個數(shù)“至少”為兩個孩子結(jié)點所包含的內(nèi)部結(jié)點數(shù)，再加上它自己影钉，于是就為2[bh(x)-1]-1+2[bh(x)-1]-1+1=2^[bh(x)]-1画髓，歸納證明完畢。好了平委，工具拿到手上了奈虾。
現(xiàn)在該干什么呢？對廉赔！現(xiàn)在該完成對原引理的證明啦肉微，不過在此之前，我們先來回顧一下紅黑樹的五個性質(zhì)蜡塌。
- 每個結(jié)點或者是紅的碉纳，或者是黑的；
- 根結(jié)點是黑的馏艾；
- 每個葉結(jié)點（NIL）是黑的劳曹；
- 如果一個結(jié)點是紅的，則它的兩個兒子都是黑的琅摩；
- 對每個結(jié)點厚者，從該結(jié)點到其子孫結(jié)點的所有路徑上包含相同數(shù)目的黑結(jié)點。
相信不斷地重復(fù)能讓人記得更牢迫吐，從特性4）我們知道，如果有一個紅結(jié)點存在账忘，那么它的兩個子結(jié)點一定是黑的志膀，最極端的情況下熙宇，該路徑上所有的結(jié)點就被紅、黑兩種結(jié)點給平分了溉浙，所以烫止，我們可以說，對于任意一棵紅黑樹戳稽，從它根結(jié)點到任一葉結(jié)點的路徑上黑結(jié)點的個數(shù)至少占到了一半馆蠕，不知這個問題我解釋清楚沒有，因為這是往下理解的關(guān)鍵惊奇。
如果一棵紅黑樹的高為h互躬，那么在這個高度上（不包括根結(jié)點本身）至少有1/2h的黑結(jié)點，再結(jié)合上面對“黑高度”的定義颂郎，我們說吼渡，紅黑樹根結(jié)點的黑高度至少是1/2h，好了乓序，現(xiàn)在拿出上面那個工具寺酪，設(shè)n為該紅黑樹所包含的內(nèi)部結(jié)點數(shù)，我們得出如下結(jié)論：
n>=2^(1/2h)-1
我們把它整理整理替劈，就得到了h<=2lg(n+1)寄雀，就是我們要證明的結(jié)論：紅黑樹的高度最多也就是2lg(n+1)。
現(xiàn)在明白為啥紅黑樹的效率還是很高了吧陨献，因為這些操作在一棵高度為h的二叉查找樹上運行時間為O(h)盒犹，而包含n個結(jié)點的紅黑樹是高度為O(lgn)的查找樹，所以相關(guān)的操作還是能在對數(shù)時間內(nèi)完成湿故，這下我們就可以放心了阿趁。
4.2 必須要避免的兩種情況
刻意地讓紅邊向左傾斜，就要考慮新結(jié)點插入后的邊的調(diào)整問題坛猪，因為可能會產(chǎn)生兩種不允許的情況出現(xiàn)脖阵。稍后將會看到，每次插入的新結(jié)點都是用紅邊去連接它的（就是說插入的默認(rèn)都是紅結(jié)點墅茉，然后再根據(jù)情況進(jìn)行調(diào)整）命黔，那么如果插入的結(jié)點恰好作為其父結(jié)點的右子結(jié)點的話，樹中就有右斜的紅邊了就斤，這是第一種不允許的情況悍募，如圖4-3所示。
第二種不允許的情況是洋机，如果插入的新結(jié)點坠宴，其父結(jié)點也是紅邊連接的，那么在一條路徑上就出現(xiàn)了兩個連續(xù)的紅邊绷旗，這叫“two reds in a row”喜鼓，這也是不允許的（回憶一下《算法導(dǎo)論》一書經(jīng)典的紅黑定義——紅結(jié)點的孩子必定是黑結(jié)點）副砍，四種不允許的情況如圖4-4所示。
好了庄岖，這里總結(jié)一下豁翎，我們的LLRB是一棵特殊的紅黑樹結(jié)構(gòu)，它不允許下面兩種情況出現(xiàn)：
- 右斜的紅邊隅忿；
- 兩個連續(xù)的紅邊出現(xiàn)在一條路徑上心剥。
注意喔！標(biāo)準(zhǔn)的紅黑樹是允許情況1出現(xiàn)的背桐，因為這里實現(xiàn)的是LLRB优烧，是紅邊向左傾斜的，所以這種情況也不允許了——這可以簡化很多對稱結(jié)構(gòu)的討論牢撼！好了匙隔，理論準(zhǔn)備足夠充分之后，我們下面要展開對具體編程實現(xiàn)的討論熏版，在具體的編程語言實現(xiàn)中結(jié)合代碼來分析紅黑樹的各種旋轉(zhuǎn)和調(diào)整操作纷责，在此之前，仍然希望你先看懂上面的討論撼短，如果你準(zhǔn)備好了再膳，那么我們繼續(xù)深入到代碼層吧！
五. LLRB的Go語言實現(xiàn)
5.1 數(shù)據(jù)結(jié)構(gòu)
我們先來看看紅黑樹的數(shù)據(jù)結(jié)構(gòu)曲横，這里設(shè)計的紅黑樹的結(jié)點由6個域組成：鍵喂柒、值、顏色（紅或者黑）禾嫉、父結(jié)點灾杰，左子結(jié)點和右子結(jié)點，即一個六元組<key, value, color, parent, left, right>熙参。其中為了提高程序的通用性艳吠，我們把關(guān)鍵字和對應(yīng)值的類型分別定義為KeyType和ValType，并將顏色值（RED和BLACK）和布爾值（TRUE和FALSE）定義成常量孽椰。然后我們使用一個head指針作為整個紅黑樹的頭部昭娩，head指針的右子結(jié)點指向紅黑樹的樹根。
type rbnode struct {
key, value interface{}
red bool
left, right *rbnode
}
type RBTree struct {
root *rbnode
length int
less func(a, b interface{}) bool
}
5.2 debug方法論
只要跟編程打交道黍匾，就絕對少不了debug栏渺，不論你考慮得再怎么仔細(xì)，bug總是存在的锐涯，不過呢磕诊，我們總是有方法來盡量減少bug的出現(xiàn)，盡量提高程序的健壯性，下面就來介紹一下我debug的三件法寶吧秀仲。
5.2.1 防御性編程（Defensive Programming）
工程師最有力的武器融痛，永遠(yuǎn)是自己的大腦。不要急著編寫代碼神僵，寫之前一定要仔細(xì)地考慮好，借用莫扎特那句名言：
“Everything has been composed, just not yet written down.”
思想應(yīng)該是先在大腦中構(gòu)思充分并反復(fù)推敲之后覆劈，再考慮它在現(xiàn)實世界的成形保礼。至少考慮好三件事，首先我這個函數(shù)要實現(xiàn)什么功能责语？如果你發(fā)現(xiàn)你的函數(shù)完成了兩個或以上的功能炮障，那還是重構(gòu)一下好一些，最好一個函數(shù)只做好一件事坤候，這符合UNIX的設(shè)計哲學(xué)胁赢；其次，這個函數(shù)的執(zhí)行需要滿足什么先決條件（precondition）白筹？是不是一定要保證在某些指針變量不為空的前提下執(zhí)行智末？注意喔，在執(zhí)行具體操作之前檢查先決條件就是防御性編程的精髓徒河！否則如果不滿足條件就執(zhí)行系馆，最后可能會得到一些莫名奇妙的結(jié)果，到時候再調(diào)試顽照，你找都找不到問題出在哪兒由蘑，所以，考慮清楚先決條件不僅減少了很多不必要的麻煩代兵，同時也為后來的單元測試提供便利：認(rèn)真檢查先決條件就是了尼酿；最后，就是后置條件（postcondition）——你這個函數(shù)執(zhí)行了什么改變植影？函數(shù)執(zhí)行后得到什么結(jié)果裳擎？把這三個因素都考慮清楚了，能極大地提高代碼的健壯性何乎，一般呢句惯，我會將函數(shù)的一個簡短的描述以及先決條件和后置條件寫成注釋放在函數(shù)的開頭。
func function(/* parameter list*/) {
/*
* DESC: function described here
* PRE: function's preconditions
* POST: function's postconditions
*/
// CODE...
}
5.2.2 測試驅(qū)動開發(fā)（Test-Driven Development）
此方法來源于敏捷思想支救，具體地說抢野，就是先寫測試，然后用測試來驅(qū)動開發(fā)各墨。在構(gòu)思好模塊的功能后指孤，我們可以先將測試代碼寫出來，然后我們剩下的工作就是圍繞測試代碼來展開：編寫正確的代碼，使得測試通過恃轩。Bob大叔在他的大作《敏捷軟件開發(fā)——原則结洼、模式與實踐》一書中談到了TDD的好處有如下幾點：
程序中的每一項功能都有測試來驗證它的操作的正確性；
迫使我們站在調(diào)用者的觀察角度叉跛，關(guān)注功能的同時也關(guān)注了接口松忍；
迫使自己把程序設(shè)計為可測試的，可測試性使得程序與其他部分解耦合筷厘；
測試代碼是一種無價的文檔形式鸣峭。
因此，往后對紅黑樹的討論就采取TDD的方法酥艳，先寫測試摊溶，再寫代碼，每完成一個功能就運行測試代碼看看結(jié)果充石，直到能夠正常結(jié)束并得到正確的結(jié)果為止莫换，然后再編寫新的測試和新的功能并與以前的測試代碼一起運行，這個過程一直持續(xù)到整個開發(fā)結(jié)束骤铃，這樣保證了新添加的功能不會影響到以前編寫的代碼拉岁，。
5.2.3 gdb調(diào)試器
這個是每一個Linux程序員必知必會的強大工具了劲厌，使用它膛薛，可以反匯編、單步執(zhí)行补鼻、設(shè)置斷點哄啄、設(shè)置觀察點.
5.2.4 創(chuàng)建紅黑樹、新建結(jié)點和判斷結(jié)點顏色
對于創(chuàng)建紅黑樹的操作风范，我們希望該樹在創(chuàng)建時是一棵“空樹”咨跌。然后我們就著手編寫NewRBTree()的代碼吧，如下所示硼婿。
func NewRBTree(less func(a, b interface{}) bool) *RBTree {
return &RBTree{
less: less,
}
}
然后是判斷結(jié)點顏色和創(chuàng)建紅黑樹結(jié)點的操作锌半。要注意當(dāng)相應(yīng)結(jié)點為nil時，返回FALSE寇漫，這個nil結(jié)點代表葉子結(jié)點刊殉。本文中所畫的紅黑樹都是內(nèi)結(jié)點，即含有鍵值對的結(jié)點州胳，而真正的葉結(jié)點是空結(jié)點记焊，不含鍵值對∷ㄗ玻回憶一下遍膜，按照紅黑樹的定義葉子結(jié)點必須是黑結(jié)點（性質(zhì)3）碗硬，故返回false。
func isRed(node *rbnode) bool {
return node != nil && node.red
}
func newRBNode(k, v interface{}) *rbnode {
return &rbnode{
key: k,
value: v,
}
}
5.2.5 左旋瓢颅、右旋和顏色翻轉(zhuǎn)
對紅黑樹的相關(guān)操作（如插入恩尾，刪除）本質(zhì)上都是基于對二叉查找樹的操作，但是挽懦，在紅黑樹的上下文中翰意，相關(guān)操作有可能會破壞紅黑性質(zhì)，因此信柿，必須對被破壞的性質(zhì)進(jìn)行“修復(fù)”猎物，而左旋（left-rotating）、右旋（right-rotating）和顏色翻轉(zhuǎn)（color flip）就是對紅黑樹進(jìn)行修復(fù)的操作角塑。但是修復(fù)并不是毫無章法的，對于不同的情況要采取不同的修復(fù)策略淘讥，相應(yīng)情況和對應(yīng)修復(fù)策略如圖4-5所示圃伶。
理解為什么要旋轉(zhuǎn)調(diào)整的關(guān)鍵，在于將2-3-4樹與其相應(yīng)的紅黑表示聯(lián)系起來看蒲列。這里以插入操作為例（刪除操作類似）窒朋，圖25中紅圈所示情況為我們有一個新插入的結(jié)點插入到了2-node的右孩子處，此時在對應(yīng)的紅黑表示中紅邊被右旋语淘，于是我們就用左旋操作來恢復(fù)LLRB“紅邊左斜（left-leaning）”的性質(zhì)甫窟；當(dāng)插入的結(jié)點作為3-node的最左孩子時莫杈，對應(yīng)的紅黑表示如圖中藍(lán)圈所示，此時我們只要將其右旋即可欺劳；而當(dāng)新插入結(jié)點作為3-node的中間孩子插入時，此時對應(yīng)的紅黑表示如圖中黃圈所示铅鲤，這時我們先執(zhí)行一個左旋操作轉(zhuǎn)換成藍(lán)圈所示情況划提，然后再執(zhí)行一個右旋即可。那么為什么要執(zhí)行顏色翻轉(zhuǎn)呢邢享？回憶一下鹏往，上面我們在討論2-3-4樹的時候，談到了4-node的分解骇塘，而顏色翻轉(zhuǎn)的操作伊履，就是為4-node準(zhǔn)備的。理解的關(guān)鍵款违，還是要把2-3-4樹和它對應(yīng)的紅黑表示聯(lián)系起來唐瀑，如圖4-6所示。
顏色翻轉(zhuǎn)之后奠货，圖4-6中原本由M介褥、E和Q共同組成的4-node就被拆分了，E和Q分別形成一個2-node，而M結(jié)點由于被紅邊連接而“融入”到了上面的結(jié)點中——如果M的父結(jié)點是2-node柔滔，則此時該父結(jié)點變成3-node溢陪，這一共有2種情況；如果M的父結(jié)點是3-node睛廊，那么此時該父結(jié)點變成4-node形真，這一共有3種情況，如圖4-7超全、圖4-8所示咆霜。
好了，理論到此為止嘶朱，下面開始貼代碼蛾坯，注意，旋轉(zhuǎn)操作只旋轉(zhuǎn)紅邊疏遏。
func rotateLeft(node *rbnode) *rbnode {
rightChild := node.right
node.right = rightChild.left
rightChild.left = node
rightChild.red = node.red
node.red = true
return rightChild
}
func rotateRight(node *rbnode) *rbnode {
leftChild := node.left
node.left = leftChild.right
leftChild.right = node
leftChild.red = node.red
node.red = true
return leftChild
}
func colorFlip(node *rbnode) *rbnode {
node.red = !node.red
if node.left != nil {
node.left.red = !node.left.red
}
if node.right != nil {
node.right.red = !node.right.red
}
return node
}
六. 紅黑樹的插入操作
有了上述的三個輔助函數(shù)脉课，我們現(xiàn)在可以來討論一下紅黑樹的插入操作，紅黑樹的插入算法可以分成兩個基本部分：一是以二叉查找樹為基礎(chǔ)的結(jié)點遞歸插入操作财异，這里對已經(jīng)存在的關(guān)鍵字更新其相應(yīng)的值倘零，而對于原來樹中沒有的關(guān)鍵字新建紅結(jié)點進(jìn)行插入；二是對樹進(jìn)行“修復(fù)”操作戳寸。
6.1 插入操作的分情況討論
為了方便理解呈驶，還是把插入操作分解成以下六種情況吧：
情況1：若新插入的紅黑結(jié)點關(guān)鍵字并不存在于原來的紅黑樹中，那么將該結(jié)點插入到樹的底部（否則更新對應(yīng)關(guān)鍵的值）疫鹊，如圖6-1所示袖瞻；
情況2：在沿樹根向下遞歸的過程中若發(fā)現(xiàn)當(dāng)前結(jié)點是4-node订晌，則分解它虏辫，判斷當(dāng)前結(jié)點是否為4-node，就是看它的左子和右子結(jié)點是不是都是紅色锈拨，如圖6-2所示砌庄；
情況3：若新插入結(jié)點的關(guān)鍵字小于當(dāng)前結(jié)點關(guān)鍵字，則插入其左子樹中（遞歸）奕枢；
情況4：若新插入結(jié)點的關(guān)鍵字大于當(dāng)前結(jié)點關(guān)鍵字娄昆，則插入其右子樹中（遞歸）；
情況5：遇到向右傾斜的紅邊缝彬，將其向左旋轉(zhuǎn)萌焰，如圖6-3所示；
情況6：遇到兩條紅邊在一條路徑上谷浅，對其進(jìn)行平衡扒俯，如圖6-4所示奶卓；
這六種情況是按順序安排的——即我們的插入算法即按照情況1到情況6的先后順序來執(zhí)行代碼的。
6.2 紅黑狀態(tài)修復(fù)
情況2撼玄、情況5和情況6都是對插入新結(jié)點后紅黑樹性質(zhì)的修復(fù)夺姑，考慮到后面的刪除操作也需要進(jìn)行相應(yīng)的修復(fù)操作，這里就使用了一個小技巧掌猛，我們把2盏浙，5和6三種情況稍微調(diào)整一下順序，并重構(gòu)到一個函數(shù)中荔茬，統(tǒng)稱為“fixUp”废膘。
func fixUp(node *rbnode) *rbnode {
if isRed(node.right) {
node = rotateLeft(node)
}
if isRed(node.left) && isRed(node.left.left) {
node = rotateRight(node)
}
if isRed(node.left) && isRed(node.right) {
node = colorFlip(node)
}
return node
}
注意，這里有一個非常重要的細(xì)節(jié)上的不同就產(chǎn)生了慕蔚。本來丐黄，如果我們按照先前介紹的順序執(zhí)行情況1到情況6，那么我們就是在自頂向下地邊插入新結(jié)點邊修復(fù)紅黑樹性質(zhì)孔飒，而當(dāng)我們將修復(fù)的操作重構(gòu)成fixUp()函數(shù)并在插入操作完成后執(zhí)行孵稽，就變成了自底向上地“事后修復(fù)”紅黑性質(zhì)了！非但如此十偶，我們還引入了兩個細(xì)微但是至關(guān)重要的不同點，仔細(xì)觀察上面的代碼园细，你會發(fā)現(xiàn)兩個問題——首先是對4-node的拆分操作被放到了兩個旋轉(zhuǎn)調(diào)整操作的后面惦积，這樣一來，我們的LLRB就不再是對2-3-4樹的表示了猛频，而是對2-3樹的表示狮崩！因為沿路徑向上的4-node全部被提前分解，不存在4-node了鹿寻！這是只看代碼不容易察覺的差別睦柴；然后就是多了個語句判斷該結(jié)點的父結(jié)點是不是head，若是的話就將其染黑毡熏，這是因為在我們沿路徑向上不斷修復(fù)紅黑性質(zhì)的時候根結(jié)點有可能被染紅坦敌，而為了防止這種情況的發(fā)生，我們在修復(fù)的最后都會強制染黑根結(jié)點痢法。好了狱窘，前面鋪墊了這么多分析，就是怕大家不好理解财搁，看到這里蘸炸，插入算法也該隆重登場了，其實只有很簡單的幾行尖奔，只要結(jié)構(gòu)組織得好搭儒，編寫的代碼就能體現(xiàn)出簡潔的美穷当，如圖40所示。
func (r *RBTree) insert(node *rbnode, k, v interface{}) (*rbnode, bool) {
ok := false
if node == nil {
return &rbnode{key: k, value: v, red: true}, true
}
if r.less(k, node.key) {
node.left, ok = insert(node.left, k, v)
} else if r.less(node.key, k) {
node.right, ok = insert(node.right, k, v)
} else {
node.value = v
ok = true
}
return fixUp(node), ok
}
相信我不用再做過多解釋淹禾，大家也能看懂它在做什么了馁菜，無非是一個二叉插入操作，然后返回一個修復(fù)過的結(jié)點稀拐。如果插入操作弄懂了火邓，下面我們就要進(jìn)入，更加復(fù)雜的——刪除操作啦德撬！
七. 紅黑樹的刪除操作
從這里開始铲咨，我們就正式介紹LLRB的刪除操作，刪除操作比插入操作要復(fù)雜一些蜓洪，但也不是完全沒有規(guī)律可循纤勒，我們甚至還可以從插入操作中獲得一些啟示，因此隆檀，對刪除操作的介紹分為兩個部分：首先進(jìn)行一下熱身摇天，先給出刪除最大元素和刪除最小元素的實現(xiàn)，然后再正式討論刪除任意元素的操作恐仑。不過在展開介紹之前泉坐，先讓我們提綱挈領(lǐng)地討論一下紅黑樹的刪除操作，介紹一些基本的裳仆，起關(guān)鍵作用的思想腕让，這樣能夠增進(jìn)對后面所討論內(nèi)容的理解∑缯澹回想一下剛才的插入操作纯丸，我們在插入新結(jié)點的時候最害怕什么？最害怕紅黑樹性質(zhì)的破壞静袖，和碰到4-node觉鼻，對吧？紅黑樹性質(zhì)被破壞了队橙，我們就要采用相應(yīng)措施修復(fù)坠陈，遇到4-node的時候，新結(jié)點根本插不進(jìn)去——因為4-node已經(jīng)“滿”了捐康，沒有空間插入新結(jié)點了——這也是我們不遺余力地分解4-node的原因（還記得“顏色翻轉(zhuǎn)”嗎）畅姊。
刪除操作只不過是插入操作的“反操作”，一個增加結(jié)點吹由，一個減少結(jié)點若未，因此插入操作中肯定有東西值得刪除操作借鑒，因為相互矛盾的事物往往又是相互聯(lián)系的倾鲫。首先很明顯的一點是粗合，刪除操作也可能會破壞紅黑性質(zhì)萍嬉，特別是你刪到黑結(jié)點的時候，所以刪除之后還是要修復(fù)的隙疚，這也是為什么會有fixUp()函數(shù)的原因壤追。其次，如果說當(dāng)執(zhí)行插入操作時供屉，我們害怕遇到4-node行冰，那么對稱地看，在刪除操作時伶丐，我們最怕遇到的是2-node悼做，因為對于3-node和4-node，刪除操作只是分別將它們變成2-node和3-node哗魂，如圖7-1所示肛走。
但是針對2-node刪除操作則把這個結(jié)點給刪沒了，更嚴(yán)重的是录别，刪除2-node就相當(dāng)于刪除紅黑樹中的黑結(jié)點朽色，這就會破壞紅黑樹的性質(zhì)5）。所以组题，刪除操作成功的關(guān)鍵就是看我們是否善于轉(zhuǎn)化——當(dāng)我們遇到2-node時葫男，將其轉(zhuǎn)化成3-node或4-node？這本質(zhì)上是一種數(shù)學(xué)思維（即將未解決的問題轉(zhuǎn)化成已經(jīng)解決的問題）崔列。怎么轉(zhuǎn)化腾誉？答案是要么進(jìn)行“合并”，要么就“借”峻呕。當(dāng)遇到2-node時：
- 如果2-node的兄弟結(jié)點是2-node，那么我們就把這兩個2-node合并成4-node趣效，如圖7-2所示瘦癌；
- 如果2-node的兄弟結(jié)點是3-node或者4-node，那么我們就向它們“借”一個結(jié)點過來將這個2-node轉(zhuǎn)化為3-node跷敬，如圖7-3所示讯私。
這里要提一點，我們要感謝偉大的LLRB西傀，正是因為它向左傾斜紅結(jié)點的表示方法讓我們省去了很多對稱情況的討論斤寇，保持了代碼的簡潔高效，易于理解拥褂。
7.1 刪除最大關(guān)鍵字
好了娘锁，言歸正傳，讓我們用遞歸的思想來思考刪除紅黑樹最大關(guān)鍵字結(jié)點的過程饺鹃，由于二叉查找樹本身的性質(zhì)莫秆，要刪除一棵紅黑樹的最大關(guān)鍵字結(jié)點间雀，就是刪除它的右子樹的最大關(guān)鍵字結(jié)點，然后這個過程又可以看成刪除右子樹的右子樹的最大關(guān)鍵字結(jié)點……就這么一直遞歸下去镊屎，直到我們走到那個其右子樹為“空”的結(jié)點惹挟，就是我們要刪除的結(jié)點了》觳担可是剛才說了连锯，如果刪除了黑結(jié)點是會破壞紅黑性質(zhì)的，且要刪除的結(jié)點右子樹為空用狱，并不代表左子樹就為空运怖，刪除結(jié)點的同時還要考慮其左結(jié)點的連接問題，怎么辦呢齿拂？
這里我們采用一個小技巧——把紅邊往右搬驳规，即當(dāng)我們在沿右子樹不斷遞歸向下的過程中,遇到向左傾斜的紅邊（這是肯定會遇到的）就把它往右搬，并且當(dāng)遇到2-node時署海，就按照上面所說的吗购，或采用合并策略，或采用借取策略來將2-node轉(zhuǎn)化成3-node或4-node砸狞，這樣最終能保證最后被刪除的結(jié)點是紅結(jié)點捻勉，并位于整棵樹的底端。具體說來刀森，處理兩種情況：遇到向左傾斜的紅邊踱启，就將其旋轉(zhuǎn)成向右傾斜（保證較大元素被“推”到右子樹去），如圖7-4所示研底。
若發(fā)現(xiàn)當(dāng)前結(jié)點h的右子結(jié)點和右子結(jié)點的左子結(jié)點都是黑結(jié)點（注意埠偿，這說明當(dāng)前結(jié)點的右子結(jié)點是2-node），那么：
- 那么榜晦，當(dāng)h的左子結(jié)點的左子結(jié)點是黑結(jié)點時（這說明h的左子結(jié)點是2-node）冠蒋，就采取合并策略，如圖7-5所示乾胶；
- 否則抖剿，當(dāng)h的左子結(jié)點的左子結(jié)點是紅結(jié)點時（這說明h的左子結(jié)點一定不是2-node），就采取借取策略识窿，如圖7-6所示斩郎。
這里的情況2是有點復(fù)雜，不好理解喻频，但是我反復(fù)強調(diào)缩宜，理解紅黑樹的關(guān)鍵不在紅黑樹本身，而在2-3-4樹甥温，因此脓恕，你把這兩種情況和圖4-2膜宋，圖4-3對2-3-4樹較為抽象的討論進(jìn)行對比，就能理解為什么會這樣做了炼幔。好了秋茫，下面我們來看代碼。
func moveRedRight(node *rbnode) *rbnode {
node = colorFlip(node)
if node.left != nil && isRed(node.left.left) {
node = rotateRight(node)
node = colorFlip(node)
}
return node
}
如果看懂了上面的分析乃秀，理解這里的代碼應(yīng)該不是問題肛著，由此看來，某些“看上去簡單”的代碼跺讯，其背后的原理不一定也簡單枢贿，所以，真正發(fā)自內(nèi)心地掌握原理才是理解和解決問題的關(guān)鍵刀脏。刪除紅黑樹中最大結(jié)點的代碼如下所示局荚。
func deleteMax(node *rbnode) *rbnode {
if isRed(node.left) {
node = rotateRight(node)
}
if node.right == nil {
return nil
}
if !isRed(node.right) && !isRed(node.right.left) {
node = moveRedRight(node)
}
node.right = deleteMax(node.right)
return fixUp(node)
}
有基本知識的讀者應(yīng)該馬上就能發(fā)現(xiàn)，這是一個遞歸調(diào)用的函數(shù)愈污，遞歸終結(jié)的條件就是當(dāng)目標(biāo)結(jié)點h的right指針指向的右子樹為“空”耀态，此時h就是包含最大關(guān)鍵字的結(jié)點，故使用deleteNode（）函數(shù)刪除之暂雹；否則在沿樹的右子樹不斷向下遞歸的過程中首装，若發(fā)現(xiàn)h結(jié)點左子樹是紅色，就右旋杭跪；發(fā)現(xiàn)h的右孩子是黑結(jié)點仙逻，就調(diào)用moveRedRight()進(jìn)行處理，最后返回修復(fù)過的紅黑樹（注意涧尿，修復(fù)操作也是自底向上遞歸進(jìn)行的）系奉。圖7-7和圖7-8給出兩個刪除最大關(guān)鍵字結(jié)點的示例。
7.2 刪除最小關(guān)鍵字
弄明白了刪除最大關(guān)鍵字結(jié)點的操作姑廉，那么刪除最小關(guān)鍵字結(jié)點的操作其實也很好理解——對稱地理解就可以了缺亮，根據(jù)BST的性質(zhì)，最小關(guān)鍵字結(jié)點一定存在于左子樹中庄蹋，我們要刪除最小關(guān)鍵字結(jié)點，只要沿左子樹一路遞歸向下即可迷雪。由于這里討論的是LLRB限书，所以紅邊本來就是向左傾斜的，所以如果跟上面刪除最大關(guān)鍵字結(jié)點要考慮的那兩種情況對比的話章咧，情況1就不用考慮了倦西，而情況2需要對稱地考慮如下。若發(fā)現(xiàn)當(dāng)前結(jié)點h的左子結(jié)點和該左子結(jié)點的左子結(jié)點都是黑結(jié)點（注意赁严，這說明當(dāng)前結(jié)點的左子結(jié)點是2-node）扰柠，那么：
- 若h的右孩子的左孩子是黑結(jié)點粉铐，那么采取“合并”策略，如圖7-9所示卤档。
- 否則蝙泼，若h的右孩子的左孩子是紅結(jié)點，那么采取“借取”策略劝枣，只不過這里是從右邊往左邊“借”紅結(jié)點汤踏，跟上面的情況恰好相反，如圖7-10所示舔腾。
下面我們先來看關(guān)鍵的moveRedLeft()函數(shù)。
func moveRedLeft(node *rbnode) *rbnode {
node = colorFlip(node)
if isRed(node.right.left) {
node.right = rotateRight(node.right)
node = rotateLeft(node)
node = colorFlip(node)
}
return node
}
不多做解釋了稳诚，直接看刪除最小結(jié)點的代碼哗脖，如圖54所示。
func deleteMin(node *rbnode) *rbnode {
if node.left == nil {
return nil
}
if !isRed(node.left) && !isRed(node.left.left) {
node = moveRedLeft(node)
}
node.left = deleteMin(node.left)
return fixUp(node)
}
圖7-11給出一個刪除操作的示例扳还。
以上就是兩個刪除特殊元素的操作才避，算是一個熱身運動，因為我們下面要開始分析真正的刪除操作了——即刪除任意元素的操作普办，在此之前一定要弄清楚上面兩個特殊過程工扎，因為下面的分析將會在上面兩個特殊情況的基礎(chǔ)上完成——本來就該這樣嘛，因為從特殊到一般衔蹲，是科學(xué)研究的基本方法肢娘。
7.3 一般刪除操作
如果說刪除最大關(guān)鍵字結(jié)點的操作是向右搬運紅邊，刪除最小關(guān)鍵字的操作是向左搬運紅邊舆驶，那么刪除任意結(jié)點的操作橱健，可以被稱為“混合搬運”——在查找被刪除結(jié)點的過程中沿樹向下遞歸，若是向左走沙廉，就把紅邊向左搬運拘荡，若是向右走，則把紅邊向右搬運撬陵，在刪除的時候考慮兩種情況：
- 被刪除的結(jié)點沒有子結(jié)點——直接刪除珊皿；
- 被刪除的結(jié)點有子結(jié)點——用該結(jié)點的直接后繼覆蓋它，然后刪除它的后繼元素（這里跟二叉查找樹的操作相同）
func (r *RBTree) delete(node *rbnode, k interface{}) (*rbnode, bool) {
ok := false
if r.less(k, node.key) {
if root.left != nil {
if !isRed(node.left) && !isRed(node.left.left) {
node = moveRedLeft(node)
}
node.left, ok = delete(node.left, k)
}
} else {
if isRed(node.left) {
node = rotateRight(node)
}
if !r.less(k, node.key) && !r.less(node.key, k) && node.right == nil {
return nil, true
}
if node.right != nil {
if !isRed(node.right) && !isRed(node.right.left) {
node = moveRedRight(node)
}
if !r.less(k, node.key) && !r.less(node.key, k) {
smallest = min(node.right)
node.key = smallest.key
node.value = smallest.value
node.right = deleteMin(node.right)
ok = true
} else {
node.right, ok = r.delete(node.right, k)
}
}
}
return fixUp(node), ok
}
func min(node *rbnode) *rbnode {
for node.left != nil {
node = node.left
}
return node
}
我們來分析一下這個過程：這個函數(shù)在一開始執(zhí)行時傳遞給h指針的是紅黑樹的樹根巨税，因此刪除操作是從樹根開始的蟋定。一開始先將h的關(guān)鍵字與key進(jìn)行對比：1）若發(fā)現(xiàn)當(dāng)前結(jié)點關(guān)鍵字大于key，說明目標(biāo)結(jié)點在其左子樹上草添，于是根據(jù)情況先將紅邊向左搬運驶兜，然后調(diào)用h->left = delete(h->left, key)向左遞歸這個過程；2）否則，若當(dāng)前結(jié)點關(guān)鍵字不大于key抄淑，那么就是小于或等于key了屠凶，這就意味著下一步要么向右子樹遞歸這個刪除過程（如果小于），要么就地刪除這個結(jié)點（如果等于）肆资，所以矗愧，若h結(jié)點左子結(jié)點是紅色，就先將其往右傾斜（以防萬一）迅耘，然后檢查它是不是有子結(jié)點贱枣，如果沒有，直接刪除并返回空颤专，否則纽哥，將紅邊往右搬，最后根據(jù)情況2）刪除它（此時被刪除的結(jié)點有子結(jié)點）栖秕，并在函數(shù)的最后返回修復(fù)過的結(jié)點春塌。這里提醒一點，也許你會有疑問簇捍，為啥判斷該結(jié)點是否有子結(jié)點只判斷了右子結(jié)點而不考慮左子結(jié)點只壳？（if((key == h->key) && (h->right == NULL))），這是因為左子結(jié)點已經(jīng)被我們向右旋轉(zhuǎn)了暑塑，所以不用考慮吼句，這里一定要想明白。
八. 知行合一
好了事格，紅黑樹的基本操作惕艳，到這里算是討論完了，這篇文章花了很大的篇幅驹愚，從2-3-4樹的完美平衡性開始介紹远搪，再到后來的紅黑樹的各種性質(zhì)和操作的分解討論，一點一點向你展示了紅黑樹的前因后果逢捺，為什么它有這么高的效率谁鳍。這里，要感謝Princeton的Sedgewick教授劫瞳，本文的所有截圖均來自于Sedgewick先生的PPT和《C算法》一書倘潜，在此對您表示最為誠摯的敬意！其實人的思維是無限的志于，想象力也是無限的涮因，但是思維世界中近乎完美的事物在現(xiàn)實世界中是不容易構(gòu)建的，它需要我們做出某種“改造”恨憎，才能很好地和現(xiàn)實情況結(jié)合起來蕊退。我覺得紅黑樹對我最大的啟發(fā)就是——一個真正的理想主義者應(yīng)該是面對現(xiàn)實的，我們既不該沉淪在自己的幻想中逃避現(xiàn)實憔恳；也不該讓外部世界成為奴役心靈的囚籠瓤荔。就像陽明先生說的，“知行合一”钥组。
