[[350533]]

 本文轉(zhuǎn)載自微信公眾號(hào)「三太子敖丙」，作者三太子敖丙。轉(zhuǎn)載本文請(qǐng)聯(lián)系三太子敖丙公眾號(hào)。  

紅黑樹(shù)是面試中一個(gè)很經(jīng)典也很有難度的知識(shí)點(diǎn)，網(wǎng)傳字節(jié)跳動(dòng)面試官最喜歡問(wèn)這個(gè)問(wèn)題。

很多人會(huì)覺(jué)得這個(gè)知識(shí)點(diǎn)太難，不想花太多功夫去了解，也有人會(huì)認(rèn)為這個(gè)數(shù)據(jù)結(jié)構(gòu)在日常開(kāi)發(fā)中使用的很少，因此沒(méi)必要多做掌握。

在此我針對(duì)以上兩個(gè)觀點(diǎn)做出一些糾正：首先，紅黑樹(shù)這個(gè)數(shù)據(jù)結(jié)構(gòu)確實(shí)復(fù)雜，但是還沒(méi)有到完全無(wú)法理解的地步。網(wǎng)上大多博客都不能夠清晰完整的描述出紅黑樹(shù)的整個(gè)體系，對(duì)于紅黑平衡調(diào)整的細(xì)節(jié)部分也沒(méi)有很詳盡的介紹，因此給學(xué)習(xí)帶來(lái)了較大的困難。

其次，諸如Java中HashMap的底層實(shí)現(xiàn)，在JDK1.8中為了解決過(guò)度哈希沖突帶來(lái)的長(zhǎng)鏈表，會(huì)將鏈表轉(zhuǎn)為紅黑樹(shù);Linux底層的CFS進(jìn)程調(diào)度算法中，vruntime利用紅黑樹(shù)來(lái)進(jìn)行存儲(chǔ);多路復(fù)用技術(shù)的Epoll的核心結(jié)構(gòu)也是紅黑樹(shù)+雙向鏈表。

我們不會(huì)直接去手寫(xiě)一個(gè)可用的紅黑樹(shù)，但是了解紅黑樹(shù)的結(jié)構(gòu)，有助于我們?nèi)ダ斫庖恍┑讓泳唧w實(shí)現(xiàn)。與此同時(shí)，紅黑樹(shù)也是對(duì)樹(shù)結(jié)構(gòu)的一種高度綜合運(yùn)用，涉及到多叉樹(shù)，樹(shù)平衡調(diào)整，節(jié)點(diǎn)旋轉(zhuǎn)等等，這些是對(duì)數(shù)據(jù)結(jié)構(gòu)基本功的最佳歷練。

 

其實(shí)當(dāng)面試官提出這個(gè)問(wèn)題的時(shí)候，不參照答案，他大概率也無(wú)法清晰的給出具體的定義和操作。但是他希望從這個(gè)問(wèn)題出發(fā)，看到你對(duì)于一個(gè)數(shù)據(jù)結(jié)構(gòu)的理解，考察你知識(shí)面的廣度和深度。能否給出完整的定義，能否介紹自己對(duì)紅黑樹(shù)的認(rèn)識(shí)，能否通過(guò)旋轉(zhuǎn)，染色等操作在給定的場(chǎng)景下對(duì)一顆紅黑樹(shù)進(jìn)行調(diào)整使其符合定義......這些才是面試官希望從你的答案中得到的信息，問(wèn)了一圈身邊大廠(chǎng)的面試官朋友，跟我這個(gè)說(shuō)法出入不大。

讀完這篇文章，你將能夠從紅黑樹(shù)的概念模型2-3-4樹(shù)出發(fā)，理解紅黑樹(shù)五大定義背后的邏輯。你也可以深刻認(rèn)識(shí)到紅黑節(jié)點(diǎn)顏色背后的意義，對(duì)于插入刪除引發(fā)的動(dòng)態(tài)變化有一定的認(rèn)識(shí)，而不再是去硬性的記憶某個(gè)場(chǎng)景下的調(diào)平操作(諸如：刪除某節(jié)點(diǎn)，當(dāng)該節(jié)點(diǎn)的叔父節(jié)點(diǎn)為紅，而叔父節(jié)點(diǎn)的左右子節(jié)點(diǎn)都為黑的情況下，我們應(yīng)該......)。你能夠掌握節(jié)點(diǎn)旋轉(zhuǎn)的具體操作，理解染色的目的。

最后，如果你足夠認(rèn)真，配圖中有清晰的插入刪除全部步驟，你能夠真正的將紅黑樹(shù)變成自己的知識(shí)。

先談平衡樹(shù)

做開(kāi)發(fā)的朋友一定知道接口這個(gè)東西：定義接口，給出實(shí)現(xiàn)。一個(gè)接口可以有多種不同的實(shí)現(xiàn)，但是這些實(shí)現(xiàn)都會(huì)滿(mǎn)足接口中的聲明。

例如，我們定義手機(jī)是一個(gè)可用作通訊的工具，作為它的實(shí)現(xiàn)，三星，蘋(píng)果，華為推出了各式各樣的產(chǎn)品。

紅黑樹(shù)的本質(zhì)其實(shí)也是對(duì)概念模型：2-3-4樹(shù)的一種實(shí)現(xiàn)，因此我們先來(lái)關(guān)注2-3-4樹(shù)。

2-3-4樹(shù)是階數(shù)為4的B樹(shù)，B樹(shù)，全名BalanceTree，平衡樹(shù)。這種結(jié)構(gòu)主要用來(lái)做查找。

關(guān)于B樹(shù)(平衡多路查找樹(shù))的定義，網(wǎng)上已經(jīng)有很多介紹，在此不多贅述。它最重要的特性在于平衡，這使得我們能夠在最壞情況下也保持O(LogN)的時(shí)間復(fù)雜度實(shí)現(xiàn)查找(一個(gè)不具備平衡性的查找樹(shù)可能退化成單鏈表，時(shí)間復(fù)雜度會(huì)到O(N))。

“在此需要提醒大家一下，平衡的定義是說(shuō)從空鏈接到根節(jié)點(diǎn)距離相等，此處一定要用心理解。(也就是說(shuō)非葉子節(jié)點(diǎn)是不會(huì)存在空鏈接的)

由于2-3-4樹(shù)是一顆階數(shù)為4的B樹(shù)，所以它會(huì)存在以下節(jié)點(diǎn)：

• 2節(jié)點(diǎn)
• 3節(jié)點(diǎn)
• 4節(jié)點(diǎn)

2節(jié)點(diǎn)中存放著一個(gè)key[X]，兩個(gè)指針，分別指向小于X的子節(jié)點(diǎn)和大于X的子節(jié)點(diǎn);3節(jié)點(diǎn)中存放在兩個(gè)key[X,Y],三個(gè)指針，分別指向小于X的子節(jié)點(diǎn)，介于X~Y之間的子節(jié)點(diǎn)和大于Y的子節(jié)點(diǎn);4節(jié)點(diǎn)可依此類(lèi)推。

節(jié)點(diǎn)介紹

 

2-3-4樹(shù)到紅黑樹(shù)的轉(zhuǎn)化

紅黑樹(shù)是對(duì)概念模型2-3-4樹(shù)的一種實(shí)現(xiàn)，由于直接進(jìn)行不同節(jié)點(diǎn)間的轉(zhuǎn)化會(huì)造成較大的開(kāi)銷(xiāo)，所以選擇以二叉樹(shù)為基礎(chǔ)，在二叉樹(shù)的屬性中加入一個(gè)顏色屬性來(lái)表示2-3-4樹(shù)中不同的節(jié)點(diǎn)。

2-3-4樹(shù)中的2節(jié)點(diǎn)對(duì)應(yīng)著紅黑樹(shù)中的黑色節(jié)點(diǎn)，而2-3-4樹(shù)中的非2節(jié)點(diǎn)是以紅節(jié)點(diǎn)+黑節(jié)點(diǎn)的方式存在，紅節(jié)點(diǎn)的意義是與黑色父節(jié)點(diǎn)結(jié)合，表達(dá)著2-3-4樹(shù)中的3，4節(jié)點(diǎn)。

(此處理解成紅節(jié)點(diǎn)也好，紅色鏈接也好，看個(gè)人喜好。很多書(shū)中會(huì)說(shuō)是由黑色節(jié)點(diǎn)指出的紅色鏈接，鏈接指向的節(jié)點(diǎn)顏色為紅。)

我們先看2-3-4樹(shù)到紅黑樹(shù)的節(jié)點(diǎn)轉(zhuǎn)換。2節(jié)點(diǎn)直接轉(zhuǎn)化為黑色節(jié)點(diǎn);3節(jié)點(diǎn)這里可以有兩種表現(xiàn)形式，左傾紅節(jié)點(diǎn)或者右傾紅節(jié)點(diǎn)。而4節(jié)點(diǎn)被強(qiáng)制要求轉(zhuǎn)化為一個(gè)黑父帶著左右兩個(gè)紅色兒子。

B樹(shù)到紅黑樹(shù)的轉(zhuǎn)化

 

本文的研究主體是2-3樹(shù)(原因會(huì)在后文給出)，并且是2-3樹(shù)中較為特殊的一種轉(zhuǎn)化--左傾紅黑樹(shù)。顧名思義，左傾紅黑樹(shù)限制了如果在樹(shù)中出現(xiàn)了紅色節(jié)點(diǎn)，那么這個(gè)節(jié)點(diǎn)必須是左兒子。

以下是它的轉(zhuǎn)化過(guò)程：

B樹(shù)到紅黑樹(shù)的轉(zhuǎn)化

 

光看單個(gè)節(jié)點(diǎn)的轉(zhuǎn)化可能還不夠明顯，我制作了一張紅黑樹(shù)轉(zhuǎn)2-3樹(shù)的示意圖，很清晰地描繪了它們之間的關(guān)系。

只要把左傾紅黑樹(shù)中的紅色節(jié)點(diǎn)順時(shí)針?lè)较蛐D(zhuǎn)45°使其與黑父平行，然后再將它們看作一個(gè)整體，你就會(huì)發(fā)現(xiàn)，這不就是一顆2-3樹(shù)嗎?

B樹(shù)到紅黑樹(shù)的轉(zhuǎn)化

 

至此，我想大家已經(jīng)明白，紅黑樹(shù)其實(shí)就是對(duì)概念模型2-3樹(shù)(或者2-3-4樹(shù))的一種實(shí)現(xiàn)。

算法導(dǎo)論中給出的是紅黑樹(shù)基于2-3-4樹(shù)實(shí)現(xiàn)，其中4節(jié)點(diǎn)要求平衡(即4節(jié)點(diǎn)必須用黑色父親和左右兩個(gè)紅色兒子表示，紅色兒子不能出現(xiàn)在同一邊)。

算法4中給出的紅黑樹(shù)是基于2-3樹(shù)實(shí)現(xiàn)，而且這種實(shí)現(xiàn)的紅黑樹(shù)十分特殊，它要求概念模型中的3節(jié)點(diǎn)在紅黑樹(shù)中必須用左傾的紅色節(jié)點(diǎn)來(lái)表示。這種限定能夠很大的減少紅黑樹(shù)調(diào)整過(guò)程中的復(fù)雜性，我們將在接下來(lái)的內(nèi)容中體會(huì)到這一點(diǎn)。

我將算法導(dǎo)論和算法4中的紅黑樹(shù)反復(fù)的看了幾遍，最終選擇算法4中的紅黑樹(shù)做演示主體。

• 首先，算法4中的紅黑樹(shù)基于2-3樹(shù)概念模型，不用考慮2-3-4樹(shù)中復(fù)雜的4節(jié)點(diǎn)分裂;
• 第二，算法4中的紅黑樹(shù)是左傾紅黑樹(shù)，進(jìn)一步降低了調(diào)平的難度;
• 第三，算法導(dǎo)論中對(duì)于紅黑樹(shù)刪除場(chǎng)景的闡述并不夠具體，許多關(guān)鍵環(huán)節(jié)都用“經(jīng)過(guò)一定的旋轉(zhuǎn)和變色處理”來(lái)帶過(guò)，不利于新手的學(xué)習(xí)。(我花了很長(zhǎng)時(shí)間還原具體過(guò)程)。

考慮到部分讀者有充足的精力研究以2-3-4樹(shù)為概念模型的紅黑樹(shù)，在介紹2-3樹(shù)的同時(shí)也會(huì)帶上2-3-4樹(shù)的基礎(chǔ)知識(shí)，幫助學(xué)有余力的讀者去理解算法導(dǎo)論中的紅黑樹(shù)。(所以如果沒(méi)有必要，只看2-3樹(shù)的部分就行)。

我們?cè)诹私饧t黑樹(shù)的插入刪除操作之前，需要先了解2-3樹(shù)的插入刪除操作，這樣才能理解紅黑樹(shù)中染色和旋轉(zhuǎn)背后的意義。

讓我們來(lái)看一下對(duì)于2-3樹(shù)的插入。我們的插入操作需要遵循一個(gè)原則：先將這個(gè)元素嘗試性地放在已經(jīng)存在的節(jié)點(diǎn)中，如果要存放的節(jié)點(diǎn)是2節(jié)點(diǎn)，那么插入后會(huì)變成3節(jié)點(diǎn)，如果要存放的節(jié)點(diǎn)是3節(jié)點(diǎn)，那么插入后會(huì)變成4節(jié)點(diǎn)(臨時(shí))。然后，我們對(duì)可能生成的臨時(shí)4節(jié)點(diǎn)進(jìn)行分裂處理，使得臨時(shí)4節(jié)點(diǎn)消失。

 

 

如果需要在2-3-4樹(shù)中向4節(jié)點(diǎn)內(nèi)插入元素，那么會(huì)引發(fā)如下圖所示的分裂過(guò)程

 

2-3-4樹(shù)的插入

 

事實(shí)上，這正對(duì)應(yīng)了紅黑樹(shù)在插入的時(shí)候一定會(huì)把待插入節(jié)點(diǎn)涂成紅色，因?yàn)榧t色節(jié)點(diǎn)的意義是與父節(jié)點(diǎn)進(jìn)行關(guān)聯(lián)，形成概念模型2-3樹(shù)中的3節(jié)點(diǎn)或者臨時(shí)4節(jié)點(diǎn)。

而紅黑樹(shù)之所以需要在插入后進(jìn)行調(diào)整，正是因?yàn)榭赡艽嬖谥拍钅Ｐ椭械呐R時(shí)4節(jié)點(diǎn)(反應(yīng)在紅黑樹(shù)中是雙紅的情況)。

試想在2-3樹(shù)中如果待插入節(jié)點(diǎn)是個(gè)2節(jié)點(diǎn)，那么反應(yīng)在紅黑樹(shù)中，不正好對(duì)應(yīng)著黑色父節(jié)點(diǎn)嗎，在黑色父節(jié)點(diǎn)下面增加一個(gè)紅色兒子，確實(shí)不會(huì)違背紅黑樹(shù)的任何規(guī)則，這也對(duì)應(yīng)著我們向2-3樹(shù)中的2節(jié)點(diǎn)插入一個(gè)元素，只需要簡(jiǎn)單的把2節(jié)點(diǎn)變成3節(jié)點(diǎn)。

接下來(lái)讓我們來(lái)看一下對(duì)于2-3樹(shù)的刪除。對(duì)于2-3樹(shù)的刪除我們主要要考慮待刪除元素在2節(jié)點(diǎn)這種情況，因?yàn)槿绻齽h除元素在3節(jié)點(diǎn)，那么可以直接將這個(gè)元素刪除，而不會(huì)破壞2-3樹(shù)的任何性質(zhì)(刪除這個(gè)元素不會(huì)引起高度的變化)。

當(dāng)待刪除元素在2節(jié)點(diǎn)的時(shí)候，由于刪除這個(gè)元素會(huì)導(dǎo)致2節(jié)點(diǎn)失去自己唯一的元素，引發(fā)2節(jié)點(diǎn)自身的刪除，會(huì)使得樹(shù)中某條路徑的高度發(fā)生變化，樹(shù)變得不平衡。

因此我們有兩種方案去解決這個(gè)問(wèn)題：

• 第一種方案，先刪除這個(gè)2節(jié)點(diǎn)，然后對(duì)樹(shù)進(jìn)行平衡調(diào)整。
• 第二種方案，我們想辦法讓這個(gè)被刪除的元素不可能出現(xiàn)在2節(jié)點(diǎn)中。

本文選擇第二種方案，我們?cè)谒阉鞯竭@個(gè)節(jié)點(diǎn)的路徑中，不斷地判斷當(dāng)前節(jié)點(diǎn)是否為2節(jié)點(diǎn)，如果是，就從它的兄弟節(jié)點(diǎn)或者它的父節(jié)點(diǎn)借一個(gè)元素，使得當(dāng)前節(jié)點(diǎn)由2節(jié)點(diǎn)成為一個(gè)3節(jié)點(diǎn)或者一個(gè)臨時(shí)4節(jié)點(diǎn)(視具體情況而定，在后面的紅黑樹(shù)部分會(huì)詳細(xì)介紹)。

這種操作會(huì)產(chǎn)生一種結(jié)果：除非當(dāng)前節(jié)點(diǎn)是根節(jié)點(diǎn)，否則當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)一定是一個(gè)非2節(jié)點(diǎn)(因?yàn)樗阉鞯穆窂绞亲陨隙?，父?jié)點(diǎn)已經(jīng)進(jìn)行過(guò)了這種操作，所以不可能是2節(jié)點(diǎn))，那么我們可以保證到達(dá)葉子節(jié)點(diǎn)的時(shí)候，也能順利的從父節(jié)點(diǎn)或者兄弟節(jié)點(diǎn)處借到元素，使得自己成為非2節(jié)點(diǎn)。從而能夠直接刪除某個(gè)元素(現(xiàn)在這個(gè)元素不在2節(jié)點(diǎn)中了)。

 

 

2-3樹(shù)的刪除

 

 

再看紅黑樹(shù)

紅黑樹(shù)的節(jié)點(diǎn)

 

來(lái)看它的五條定義：

1.節(jié)點(diǎn)顏色有紅色和黑色

【2-3樹(shù)到紅黑樹(shù)的轉(zhuǎn)化已經(jīng)解釋過(guò)】

2.根節(jié)點(diǎn)必為黑色

【2-3樹(shù)中如果根節(jié)點(diǎn)為2節(jié)點(diǎn)，那么它本來(lái)就對(duì)應(yīng)紅黑樹(shù)中黑節(jié)點(diǎn);如果根節(jié)點(diǎn)為3節(jié)點(diǎn)，也可以用黑色節(jié)點(diǎn)表示較大的那個(gè)元素，然后較小的元素作為左傾紅節(jié)點(diǎn)存在于紅黑樹(shù)中】

3.所有葉子節(jié)點(diǎn)都是黑色

【此處提到的葉子其實(shí)是空鏈接，因篇幅問(wèn)題不便全部畫(huà)出】

####4.任意節(jié)點(diǎn)到葉子節(jié)點(diǎn)經(jīng)過(guò)的黑色節(jié)點(diǎn)數(shù)目相同

【紅黑樹(shù)中的紅節(jié)點(diǎn)是和黑色父節(jié)點(diǎn)綁定的，在2-3樹(shù)中本來(lái)就是同一層的，只有黑色節(jié)點(diǎn)才會(huì)在2-3樹(shù)中真正貢獻(xiàn)高度，由于2-3樹(shù)的任一節(jié)點(diǎn)到空鏈接距離相同，因此反應(yīng)在紅黑樹(shù)中就是黑色完美平衡】

5.不會(huì)有連續(xù)的紅色節(jié)點(diǎn)

【2-3樹(shù)中本來(lái)就規(guī)定沒(méi)有4節(jié)點(diǎn)，2-3-4樹(shù)中雖然有4節(jié)點(diǎn)，但是要求在紅黑樹(shù)中體現(xiàn)為一黑色節(jié)點(diǎn)帶兩紅色兒子，分布左右，所以也不會(huì)有連續(xù)紅節(jié)點(diǎn)】

相信在你的視角中，紅黑樹(shù)已經(jīng)不再是這五條僵硬的定義了，它背后正浮現(xiàn)著一顆2-3樹(shù)概念模型。雖然你已經(jīng)有了這樣的認(rèn)識(shí)，但是紅黑樹(shù)作為真正的實(shí)現(xiàn)模型，我們還是要回到這個(gè)實(shí)現(xiàn)本身來(lái)探究它的一系列操作。在開(kāi)始前，我準(zhǔn)備了兩個(gè)基礎(chǔ)知識(shí)，希望能幫助到你。

1.作為二叉查找樹(shù)

二叉查找樹(shù)的節(jié)點(diǎn)有一個(gè)元素X和兩個(gè)指針域，左指針指向小于X的元素，右指針指向大于X的元素。

假設(shè)我們的插入序列是1~10，那么這顆樹(shù)會(huì)演變成只有右鏈接的形式，樹(shù)高會(huì)增加到10層，這個(gè)時(shí)候已經(jīng)不具備O(LogN)的查找時(shí)間復(fù)雜度，因?yàn)檫@顆樹(shù)退化成了鏈表。

因此對(duì)二叉樹(shù)進(jìn)行平衡調(diào)整是很重要的一個(gè)環(huán)節(jié)，無(wú)論是AVL還是紅黑樹(shù)，它們本質(zhì)上都是希望盡可能保證這顆二叉查找樹(shù)中的元素盡量均衡的分布在樹(shù)的兩側(cè)。

當(dāng)我們向一顆二叉查找樹(shù)中插入一個(gè)元素Y的時(shí)候，我們會(huì)一直與樹(shù)中的節(jié)點(diǎn)進(jìn)行大小比較，如果Y小于當(dāng)前元素，就往左走，如果Y大于當(dāng)前元素，就往右走，直到達(dá)到葉子節(jié)點(diǎn)，這個(gè)時(shí)候我們可以把Y插入這顆二叉查找樹(shù)了。

由于這次的插入動(dòng)作，整棵樹(shù)可能會(huì)發(fā)生一些不平衡，因此我們需要在插入后進(jìn)行一次平衡調(diào)整，使得整棵樹(shù)恢復(fù)到平衡的狀態(tài)(具體如何調(diào)整，要看樹(shù)是AVL還是紅黑樹(shù)亦或是其他的平衡樹(shù))。

二叉查找樹(shù)的刪除是一個(gè)很有意思的問(wèn)題，不同于插入的是，待刪除的元素并不能保證一定出現(xiàn)在樹(shù)中的葉子節(jié)點(diǎn)。這將帶來(lái)一個(gè)棘手的情景，即我們需要從樹(shù)的中間部分取走一個(gè)元素，而且在取走后還需要經(jīng)過(guò)調(diào)整來(lái)使得整顆樹(shù)滿(mǎn)足平衡的性質(zhì)。從樹(shù)的中間部分直接取走一個(gè)節(jié)點(diǎn)的場(chǎng)景實(shí)在是太多，也牽扯到了太多相關(guān)的節(jié)點(diǎn)，這種操作很難實(shí)現(xiàn)。

好在有人提出了一個(gè)觀點(diǎn)，我們對(duì)查找樹(shù)中一個(gè)節(jié)點(diǎn)的刪除，其實(shí)可以不必真的改動(dòng)這個(gè)節(jié)點(diǎn)的位置。由于查找樹(shù)的特殊性質(zhì)，將某個(gè)元素節(jié)點(diǎn)刪除后，它有兩個(gè)最佳替代者，分別是有序序列中的前驅(qū)元素和后繼元素。

我們還是以一個(gè)包含元素1~10的二叉查找樹(shù)為例，如果我們希望刪除5所在的節(jié)點(diǎn)，那么讓4或者6替代它的位置都是可行的。作為前驅(qū)元素的4，會(huì)存放在5所在節(jié)點(diǎn)的左子樹(shù)的最右側(cè);作為后繼元素的6，會(huì)存放在5所在節(jié)點(diǎn)的右子樹(shù)的最左側(cè)。

關(guān)于這個(gè)結(jié)論，大家只需稍加思索便可以明白。

現(xiàn)在我們又讓問(wèn)題簡(jiǎn)化了，也就是說(shuō)，刪除某個(gè)節(jié)點(diǎn)的時(shí)候，我們先找到它的前驅(qū)元素或者后繼元素(隨便選一個(gè))，將它的前驅(qū)元素直接填到待刪除的節(jié)點(diǎn)，然后再把它的前驅(qū)元素或者后繼元素刪除。

這個(gè)時(shí)候問(wèn)題就轉(zhuǎn)化成了在二叉查找樹(shù)中刪除一個(gè)沒(méi)有左子樹(shù)的節(jié)點(diǎn)(或者是一個(gè)沒(méi)有右子樹(shù)的節(jié)點(diǎn))，我們只需要將這個(gè)節(jié)點(diǎn)刪除再進(jìn)行對(duì)應(yīng)的平衡調(diào)整即可(雖然還是需要調(diào)平，但是比直接在樹(shù)中層刪除一個(gè)同時(shí)具備左右兒子的節(jié)點(diǎn)要容易很多)。

注意，此處并沒(méi)有強(qiáng)調(diào)是針對(duì)紅黑樹(shù)的操作，因?yàn)榧t黑樹(shù)和AVL都是二叉查找樹(shù)，它們都適用這個(gè)方法。

介紹一下樹(shù)的旋轉(zhuǎn)為了調(diào)平一顆二叉樹(shù)，使得其左右節(jié)點(diǎn)數(shù)目分布均勻，通常會(huì)選擇旋轉(zhuǎn)的手段。你可以把一顆二叉樹(shù)某節(jié)點(diǎn)的左右子樹(shù)想象成天平上待稱(chēng)量的物品，如果哪邊重了，我們就從重的那邊拿出一部分，加到輕的那邊，以此保持相對(duì)的平均。

在二叉樹(shù)中這種調(diào)整的操作就是旋轉(zhuǎn)，下面給出了兩個(gè)示例，希望大家能夠仔細(xì)探究，旋轉(zhuǎn)是二叉樹(shù)調(diào)平的精髓。

介紹一下樹(shù)的旋轉(zhuǎn)

樹(shù)的旋轉(zhuǎn)操作

 

理解了這些之后，再去看紅黑樹(shù)的插入刪除，就能夠理解旋轉(zhuǎn)和染色背后的意義了。我們選擇算法4中的左傾紅黑樹(shù)作演示：首先看插入

左傾紅黑樹(shù)的插入

 

如圖所示，對(duì)于左傾紅黑樹(shù)的插入一共有三種可能的情況。

• 第一種，待插入元素比黑父大，插在了黑父的右邊，而黑父左邊是紅色兒子。這種情況會(huì)導(dǎo)致在紅黑樹(shù)中出現(xiàn)右傾紅節(jié)點(diǎn)。

注意，這種情況對(duì)應(yīng)著2-3樹(shù)中出現(xiàn)了臨時(shí)4節(jié)點(diǎn)，我們?cè)?-3樹(shù)中的處理是將這個(gè)臨時(shí)4節(jié)點(diǎn)分裂，左右元素各自形成一個(gè)2節(jié)點(diǎn)，中間元素上升到上層跟父節(jié)點(diǎn)結(jié)合。所以，我們?cè)诩t黑樹(shù)中的動(dòng)作是，將原本紅色的左右兒子染黑(左右分裂)，將黑父染紅(等待上升結(jié)合)。

 

 

左傾紅黑樹(shù)的插入

 

 

• 第二種情況，待插入元素比紅父小，且紅父自身就是左傾。聽(tīng)起來(lái)有點(diǎn)繞，看圖就會(huì)明白，其實(shí)就是說(shuō)紅父和待插入元素同時(shí)靠在了左邊，形成了連續(xù)的紅節(jié)點(diǎn)。

這種情況我們需要用兩步來(lái)調(diào)整。由于我們插入的是紅色節(jié)點(diǎn)，其實(shí)不會(huì)破壞黑色完美平衡，所以要注意的是在旋轉(zhuǎn)和染色的過(guò)程種繼續(xù)保持這種完美黑色平衡。

首先對(duì)紅父的父親進(jìn)行一次右旋，這次右旋不會(huì)破壞黑色平衡，但是也沒(méi)有解決連續(xù)紅色的問(wèn)題。

接下來(lái)將12所在節(jié)點(diǎn)與15所在節(jié)點(diǎn)交換顏色，這樣的目的是為了消除連續(xù)紅色，并且這個(gè)操作依舊維持了黑色平衡?，F(xiàn)在我們已經(jīng)得到了情況1的場(chǎng)景，直接按情況1處理即可。

左傾紅黑樹(shù)的插入

 

• 第三種情況，待插入元素比紅父大，且紅父自身就是左傾。

也就是說(shuō)插入的這個(gè)節(jié)點(diǎn)形成了一個(gè)右傾的紅色節(jié)點(diǎn)，對(duì)右傾的處理很簡(jiǎn)單，將紅父進(jìn)行一次左旋，就能使得右傾紅節(jié)點(diǎn)變?yōu)樽髢A，現(xiàn)在出現(xiàn)了連續(xù)的左傾紅節(jié)點(diǎn)，直接按情況2處理即可。

左傾紅黑樹(shù)的插入

 

在插入時(shí)，可以體會(huì)到左傾紅黑樹(shù)對(duì)于左傾的限制帶來(lái)的好處，因?yàn)樵谠瓨?shù)符合紅黑樹(shù)定義的情況下，如果父親是紅的，那么它一定左傾，同時(shí)也不用考慮可能存在的右傾兄弟(如果有，那說(shuō)明原樹(shù)不滿(mǎn)足紅黑樹(shù)定義)。

這種限制消除了很多需要考慮的場(chǎng)景，讓插入變得更加簡(jiǎn)單。

左傾紅黑樹(shù)的刪除

左傾紅黑樹(shù)的刪除需要借鑒上文中提到的二叉查找樹(shù)通用的刪除策略，當(dāng)我們要?jiǎng)h除某個(gè)節(jié)點(diǎn)的時(shí)候選擇它的前驅(qū)節(jié)點(diǎn)或者后繼節(jié)點(diǎn)元素來(lái)替代它，轉(zhuǎn)而刪除它的前驅(qū)/后繼節(jié)點(diǎn)。

在這個(gè)例子中，我選擇用后繼節(jié)點(diǎn)來(lái)替代被刪除節(jié)點(diǎn)。

假設(shè)我們需要?jiǎng)h除的節(jié)點(diǎn)它的右子樹(shù)如圖所示，那么對(duì)該節(jié)點(diǎn)的刪除實(shí)際上轉(zhuǎn)為了對(duì)2的刪除。

我們從當(dāng)前的根節(jié)點(diǎn)出發(fā)，利于2-3樹(shù)中預(yù)合并的策略逐層對(duì)紅黑樹(shù)進(jìn)行調(diào)整。具體的做法是，每次都保證當(dāng)前的節(jié)點(diǎn)是2-3樹(shù)中的非2節(jié)點(diǎn)，如果當(dāng)前節(jié)點(diǎn)已經(jīng)是非2節(jié)點(diǎn)，那么直接跳過(guò);如果當(dāng)前節(jié)點(diǎn)是2節(jié)點(diǎn)，那么根據(jù)兄弟節(jié)點(diǎn)的狀況來(lái)進(jìn)行調(diào)整：

如果兄弟是2節(jié)點(diǎn)，那么從父節(jié)點(diǎn)借一個(gè)元素給當(dāng)前節(jié)點(diǎn)，然后與兄弟節(jié)點(diǎn)一起形成一個(gè)臨時(shí)4節(jié)點(diǎn)。

如果兄弟是非2節(jié)點(diǎn)，那么兄弟上升一個(gè)元素到父節(jié)點(diǎn)，同時(shí)父節(jié)點(diǎn)下降一個(gè)元素到當(dāng)前節(jié)點(diǎn)，使得當(dāng)前節(jié)點(diǎn)成為一個(gè)3節(jié)點(diǎn)。

這樣的策略能夠保證最后走到待刪除節(jié)點(diǎn)的時(shí)候，它一定是一個(gè)非2節(jié)點(diǎn)，我們可以直接將其元素刪除。

左傾紅黑樹(shù)的刪除

 

接下來(lái)要考慮的是修復(fù)工作，由于紅黑樹(shù)定義的限制，我們?cè)谡{(diào)整的過(guò)程中出現(xiàn)了一些本不該存在的紅色右傾節(jié)點(diǎn)(因?yàn)樯闪烁拍钅Ｐ椭械呐R時(shí)4節(jié)點(diǎn))，于是我們順著搜索的方向向上回溯，如果遇到當(dāng)前節(jié)點(diǎn)具備右傾的紅色兒子，那么對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行一次左旋，這時(shí)原本的右兒子會(huì)來(lái)到當(dāng)前節(jié)點(diǎn)的位置，然后將右兒子與當(dāng)前節(jié)點(diǎn)交換顏色，我們就將右傾紅節(jié)點(diǎn)修復(fù)成了左傾紅節(jié)點(diǎn)，同時(shí)我們并沒(méi)有破壞黑色節(jié)點(diǎn)的平衡。

左傾紅黑樹(shù)的刪除

 

右傾轉(zhuǎn)左傾是一個(gè)很基本的操作，我們以35，44為例，你既可以將35作為黑節(jié)點(diǎn)，44作為右傾紅色兒子;也可以將44作為黑節(jié)點(diǎn)，35作為左傾紅兒子。事實(shí)上我們對(duì)于右傾的修復(fù)就是換了一種樹(shù)形而已。一路回溯到當(dāng)前根節(jié)點(diǎn)，直至路徑中不再包含任何的紅色右傾節(jié)點(diǎn)，至此修復(fù)工作全部完成。

總結(jié)

這篇文章的目的旨在從概念模型2-3樹(shù)出發(fā)介紹一顆紅黑樹(shù)的前世今生。希望大家能夠跳出枯燥的五條定義，更加本質(zhì)地認(rèn)識(shí)紅黑樹(shù)中的各種操作來(lái)源。

雖然本文只是介紹了相對(duì)簡(jiǎn)單的左傾紅黑樹(shù)，但是如果能夠?qū)⒆髢A紅黑樹(shù)認(rèn)識(shí)的很清楚，那么普通紅黑樹(shù)也只是多了一些情況而已。

對(duì)于還有精力閱讀算法導(dǎo)論的讀者，我給出一點(diǎn)自己的經(jīng)驗(yàn)：

插入階段與左傾紅黑樹(shù)比較相似

配圖中的部分節(jié)點(diǎn)標(biāo)識(shí)不太清楚，要反復(fù)對(duì)照原文閱讀

刪除階段，算法導(dǎo)論中將刪除黑節(jié)點(diǎn)X帶來(lái)的黑色平衡破壞解釋為，給X的子節(jié)點(diǎn)添上額外的一層黑色，讓X的子節(jié)點(diǎn)變?yōu)椤倦p重黑】或者【既黑又紅】的。

我其實(shí)不太接受這種解釋?zhuān)?jīng)過(guò)考慮，我認(rèn)為其實(shí)這個(gè)表達(dá)可以更直接一點(diǎn)：既然刪除了某個(gè)黑色節(jié)點(diǎn)，那么必然會(huì)破壞以這個(gè)黑色節(jié)點(diǎn)為路徑上的黑色平衡，表現(xiàn)為路徑中缺少一個(gè)黑。

如果你仔細(xì)研究算法導(dǎo)論中的四個(gè)刪除場(chǎng)景，會(huì)發(fā)現(xiàn)它們?cè)谧龅氖虑槠鋵?shí)都是從兄弟節(jié)點(diǎn)的路徑想辦法移動(dòng)一個(gè)黑色節(jié)點(diǎn)過(guò)來(lái)。

因此，如果實(shí)在無(wú)法理解【雙重黑】，【既黑又紅】，那么直接按照“某條路徑欠黑，所以要想辦法補(bǔ)充一個(gè)黑色節(jié)點(diǎn)”這個(gè)思路來(lái)思考吧!

還是刪除階段，四個(gè)刪除場(chǎng)景該如何記憶?我們假設(shè)刪除的是某個(gè)左傾節(jié)點(diǎn)，其實(shí)決定場(chǎng)景變化的就是三個(gè)因素：這個(gè)節(jié)點(diǎn)的兄弟顏色;兄弟的左右兒子的顏色;這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)的顏色。這樣子粗略估計(jì)有2x2x2x2共16種情況。實(shí)際上會(huì)少很多，我們從兄弟的顏色入手。請(qǐng)注意如果兄弟是紅色，那么當(dāng)前節(jié)點(diǎn)的父親和兄弟的兒子其實(shí)都是黑色。而當(dāng)兄弟是黑色的時(shí)候，我們只需要滿(mǎn)足兄弟的右兒子是紅色，就能通過(guò)一次調(diào)整來(lái)實(shí)現(xiàn)平衡(具體請(qǐng)參照算法導(dǎo)論)。

另外提醒注意的是，一定要想好記憶的順序。算法導(dǎo)論中的刪除調(diào)平4種情況中，只有情況4是絕對(duì)終態(tài)，也就是說(shuō)到達(dá)了這種狀態(tài)后只需要一次調(diào)整絕對(duì)能達(dá)到平衡。所以我們的出發(fā)點(diǎn)一定是從這種狀態(tài)開(kāi)始，對(duì)于另外幾種情況，我們要想的不是怎么去達(dá)到最終平衡，而是怎么能讓它一步一步轉(zhuǎn)為情況4。這樣子你的思路就會(huì)清晰很多，記憶的壓力也會(huì)減小。如果細(xì)心的話(huà)，你可以回想一下本文是按照怎樣的順序介紹左傾紅黑樹(shù)的插入的，為什么是這樣的順序?

一個(gè)數(shù)據(jù)結(jié)構(gòu)可視化網(wǎng)站，它的紅黑樹(shù)是基于2-3-4樹(shù)的，跟算法導(dǎo)論中基本一樣(除了刪除時(shí)候?qū)η膀?qū)/后繼節(jié)點(diǎn)的選擇)，可以用它當(dāng)做檢驗(yàn)。https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

絮叨最后，如果你被問(wèn)到紅黑樹(shù)，也許你可以試著反問(wèn)面試官一個(gè)問(wèn)題：“您應(yīng)該知道紅黑樹(shù)的五條定義，如果我構(gòu)造一顆只有黑色節(jié)點(diǎn)的紅黑樹(shù)，這樣子可行嗎?因?yàn)檫@樣子沒(méi)有破壞任何一條紅黑樹(shù)的規(guī)則。”

如果他回答可行。

繼續(xù)問(wèn)：“那么請(qǐng)問(wèn)紅黑樹(shù)中要紅節(jié)點(diǎn)干什么呢?紅節(jié)點(diǎn)的真實(shí)意義是什么呢?”

你們的故事就開(kāi)始了，而我和你的算法故事也才剛開(kāi)始。

好啦以上就是本期的全部?jī)?nèi)容了，我是敖丙，你知道的越多，你不知道的越多，我們下期見(jiàn)。