建站
咨詢
售后
建站咨詢
新聞中心
本文轉(zhuǎn)載自微信公眾號(hào)「三太子敖丙」，作者三太子敖丙。轉(zhuǎn)載本文請(qǐng)聯(lián)系三太子敖丙公眾號(hào)。
創(chuàng)新互聯(lián)專注于中大型企業(yè)的成都網(wǎng)站制作、成都網(wǎng)站建設(shè)和網(wǎng)站改版、網(wǎng)站營(yíng)銷服務(wù)，追求商業(yè)策劃與數(shù)據(jù)分析、創(chuàng)意藝術(shù)與技術(shù)開發(fā)的融合，累計(jì)客戶超過千家，服務(wù)滿意度達(dá)97%。幫助廣大客戶順利對(duì)接上互聯(lián)網(wǎng)浪潮，準(zhǔn)確優(yōu)選出符合自己需要的互聯(lián)網(wǎng)運(yùn)用，我們將一直專注高端網(wǎng)站設(shè)計(jì)和互聯(lián)網(wǎng)程序開發(fā)，在前進(jìn)的路上，與客戶一起成長(zhǎng)！
紅黑樹是面試中一個(gè)很經(jīng)典也很有難度的知識(shí)點(diǎn)，網(wǎng)傳字節(jié)跳動(dòng)面試官最喜歡問這個(gè)問題。
很多人會(huì)覺得這個(gè)知識(shí)點(diǎn)太難，不想花太多功夫去了解，也有人會(huì)認(rèn)為這個(gè)數(shù)據(jù)結(jié)構(gòu)在日常開發(fā)中使用的很少，因此沒必要多做掌握。
在此我針對(duì)以上兩個(gè)觀點(diǎn)做出一些糾正：首先，紅黑樹這個(gè)數(shù)據(jù)結(jié)構(gòu)確實(shí)復(fù)雜，但是還沒有到完全無法理解的地步。網(wǎng)上大多博客都不能夠清晰完整的描述出紅黑樹的整個(gè)體系，對(duì)于紅黑平衡調(diào)整的細(xì)節(jié)部分也沒有很詳盡的介紹，因此給學(xué)習(xí)帶來了較大的困難。
其次，諸如Java中HashMap的底層實(shí)現(xiàn)，在JDK1.8中為了解決過度哈希沖突帶來的長(zhǎng)鏈表，會(huì)將鏈表轉(zhuǎn)為紅黑樹;Linux底層的CFS進(jìn)程調(diào)度算法中，vruntime利用紅黑樹來進(jìn)行存儲(chǔ);多路復(fù)用技術(shù)的Epoll的核心結(jié)構(gòu)也是紅黑樹+雙向鏈表。
我們不會(huì)直接去手寫一個(gè)可用的紅黑樹，但是了解紅黑樹的結(jié)構(gòu)，有助于我們?nèi)ダ斫庖恍┑讓泳唧w實(shí)現(xiàn)。與此同時(shí)，紅黑樹也是對(duì)樹結(jié)構(gòu)的一種高度綜合運(yùn)用，涉及到多叉樹，樹平衡調(diào)整，節(jié)點(diǎn)旋轉(zhuǎn)等等，這些是對(duì)數(shù)據(jù)結(jié)構(gòu)基本功的最佳歷練。
其實(shí)當(dāng)面試官提出這個(gè)問題的時(shí)候，不參照答案，他大概率也無法清晰的給出具體的定義和操作。但是他希望從這個(gè)問題出發(fā)，看到你對(duì)于一個(gè)數(shù)據(jù)結(jié)構(gòu)的理解，考察你知識(shí)面的廣度和深度。能否給出完整的定義，能否介紹自己對(duì)紅黑樹的認(rèn)識(shí)，能否通過旋轉(zhuǎn)，染色等操作在給定的場(chǎng)景下對(duì)一顆紅黑樹進(jìn)行調(diào)整使其符合定義......這些才是面試官希望從你的答案中得到的信息，問了一圈身邊大廠的面試官朋友，跟我這個(gè)說法出入不大。
讀完這篇文章，你將能夠從紅黑樹的概念模型2-3-4樹出發(fā)，理解紅黑樹五大定義背后的邏輯。你也可以深刻認(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í)。
先談平衡樹
做開發(fā)的朋友一定知道接口這個(gè)東西：定義接口，給出實(shí)現(xiàn)。一個(gè)接口可以有多種不同的實(shí)現(xiàn)，但是這些實(shí)現(xiàn)都會(huì)滿足接口中的聲明。
例如，我們定義手機(jī)是一個(gè)可用作通訊的工具，作為它的實(shí)現(xiàn)，三星，蘋果，華為推出了各式各樣的產(chǎn)品。
紅黑樹的本質(zhì)其實(shí)也是對(duì)概念模型：2-3-4樹的一種實(shí)現(xiàn)，因此我們先來關(guān)注2-3-4樹。
2-3-4樹是階數(shù)為4的B樹，B樹，全名BalanceTree，平衡樹。這種結(jié)構(gòu)主要用來做查找。
關(guān)于B樹(平衡多路查找樹)的定義，網(wǎng)上已經(jīng)有很多介紹，在此不多贅述。它最重要的特性在于平衡，這使得我們能夠在最壞情況下也保持O(LogN)的時(shí)間復(fù)雜度實(shí)現(xiàn)查找(一個(gè)不具備平衡性的查找樹可能退化成單鏈表，時(shí)間復(fù)雜度會(huì)到O(N))。
“在此需要提醒大家一下，平衡的定義是說從空鏈接到根節(jié)點(diǎn)距離相等，此處一定要用心理解。(也就是說非葉子節(jié)點(diǎn)是不會(huì)存在空鏈接的)
由于2-3-4樹是一顆階數(shù)為4的B樹，所以它會(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)可依此類推。
節(jié)點(diǎn)介紹
2-3-4樹到紅黑樹的轉(zhuǎn)化
紅黑樹是對(duì)概念模型2-3-4樹的一種實(shí)現(xiàn)，由于直接進(jìn)行不同節(jié)點(diǎn)間的轉(zhuǎn)化會(huì)造成較大的開銷，所以選擇以二叉樹為基礎(chǔ)，在二叉樹的屬性中加入一個(gè)顏色屬性來表示2-3-4樹中不同的節(jié)點(diǎn)。
2-3-4樹中的2節(jié)點(diǎn)對(duì)應(yīng)著紅黑樹中的黑色節(jié)點(diǎn)，而2-3-4樹中的非2節(jié)點(diǎn)是以紅節(jié)點(diǎn)+黑節(jié)點(diǎn)的方式存在，紅節(jié)點(diǎn)的意義是與黑色父節(jié)點(diǎn)結(jié)合，表達(dá)著2-3-4樹中的3，4節(jié)點(diǎn)。
(此處理解成紅節(jié)點(diǎn)也好，紅色鏈接也好，看個(gè)人喜好。很多書中會(huì)說是由黑色節(jié)點(diǎn)指出的紅色鏈接，鏈接指向的節(jié)點(diǎn)顏色為紅。)
我們先看2-3-4樹到紅黑樹的節(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樹到紅黑樹的轉(zhuǎn)化
本文的研究主體是2-3樹(原因會(huì)在后文給出)，并且是2-3樹中較為特殊的一種轉(zhuǎn)化--左傾紅黑樹。顧名思義，左傾紅黑樹限制了如果在樹中出現(xiàn)了紅色節(jié)點(diǎn)，那么這個(gè)節(jié)點(diǎn)必須是左兒子。
以下是它的轉(zhuǎn)化過程：
B樹到紅黑樹的轉(zhuǎn)化
光看單個(gè)節(jié)點(diǎn)的轉(zhuǎn)化可能還不夠明顯，我制作了一張紅黑樹轉(zhuǎn)2-3樹的示意圖，很清晰地描繪了它們之間的關(guān)系。
只要把左傾紅黑樹中的紅色節(jié)點(diǎn)順時(shí)針方向旋轉(zhuǎn)45°使其與黑父平行，然后再將它們看作一個(gè)整體，你就會(huì)發(fā)現(xiàn)，這不就是一顆2-3樹嗎?
B樹到紅黑樹的轉(zhuǎn)化
至此，我想大家已經(jīng)明白，紅黑樹其實(shí)就是對(duì)概念模型2-3樹(或者2-3-4樹)的一種實(shí)現(xiàn)。
算法導(dǎo)論中給出的是紅黑樹基于2-3-4樹實(shí)現(xiàn)，其中4節(jié)點(diǎn)要求平衡(即4節(jié)點(diǎn)必須用黑色父親和左右兩個(gè)紅色兒子表示，紅色兒子不能出現(xiàn)在同一邊)。
算法4中給出的紅黑樹是基于2-3樹實(shí)現(xiàn)，而且這種實(shí)現(xiàn)的紅黑樹十分特殊，它要求概念模型中的3節(jié)點(diǎn)在紅黑樹中必須用左傾的紅色節(jié)點(diǎn)來表示。這種限定能夠很大的減少紅黑樹調(diào)整過程中的復(fù)雜性，我們將在接下來的內(nèi)容中體會(huì)到這一點(diǎn)。
我將算法導(dǎo)論和算法4中的紅黑樹反復(fù)的看了幾遍，最終選擇算法4中的紅黑樹做演示主體。
- 首先，算法4中的紅黑樹基于2-3樹概念模型，不用考慮2-3-4樹中復(fù)雜的4節(jié)點(diǎn)分裂;
- 第二，算法4中的紅黑樹是左傾紅黑樹，進(jìn)一步降低了調(diào)平的難度;
- 第三，算法導(dǎo)論中對(duì)于紅黑樹刪除場(chǎng)景的闡述并不夠具體，許多關(guān)鍵環(huán)節(jié)都用“經(jīng)過一定的旋轉(zhuǎn)和變色處理”來帶過，不利于新手的學(xué)習(xí)。(我花了很長(zhǎng)時(shí)間還原具體過程)。
考慮到部分讀者有充足的精力研究以2-3-4樹為概念模型的紅黑樹，在介紹2-3樹的同時(shí)也會(huì)帶上2-3-4樹的基礎(chǔ)知識(shí)，幫助學(xué)有余力的讀者去理解算法導(dǎo)論中的紅黑樹。(所以如果沒有必要，只看2-3樹的部分就行)。
我們?cè)诹私饧t黑樹的插入刪除操作之前，需要先了解2-3樹的插入刪除操作，這樣才能理解紅黑樹中染色和旋轉(zhuǎn)背后的意義。
讓我們來看一下對(duì)于2-3樹的插入。我們的插入操作需要遵循一個(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樹中向4節(jié)點(diǎn)內(nèi)插入元素，那么會(huì)引發(fā)如下圖所示的分裂過程
2-3-4樹的插入
事實(shí)上，這正對(duì)應(yīng)了紅黑樹在插入的時(shí)候一定會(huì)把待插入節(jié)點(diǎn)涂成紅色，因?yàn)榧t色節(jié)點(diǎn)的意義是與父節(jié)點(diǎn)進(jìn)行關(guān)聯(lián)，形成概念模型2-3樹中的3節(jié)點(diǎn)或者臨時(shí)4節(jié)點(diǎn)。
而紅黑樹之所以需要在插入后進(jìn)行調(diào)整，正是因?yàn)榭赡艽嬖谥拍钅Ｐ椭械呐R時(shí)4節(jié)點(diǎn)(反應(yīng)在紅黑樹中是雙紅的情況)。
試想在2-3樹中如果待插入節(jié)點(diǎn)是個(gè)2節(jié)點(diǎn)，那么反應(yīng)在紅黑樹中，不正好對(duì)應(yīng)著黑色父節(jié)點(diǎn)嗎，在黑色父節(jié)點(diǎn)下面增加一個(gè)紅色兒子，確實(shí)不會(huì)違背紅黑樹的任何規(guī)則，這也對(duì)應(yīng)著我們向2-3樹中的2節(jié)點(diǎn)插入一個(gè)元素，只需要簡(jiǎn)單的把2節(jié)點(diǎn)變成3節(jié)點(diǎn)。
接下來讓我們來看一下對(duì)于2-3樹的刪除。對(duì)于2-3樹的刪除我們主要要考慮待刪除元素在2節(jié)點(diǎn)這種情況，因?yàn)槿绻齽h除元素在3節(jié)點(diǎn)，那么可以直接將這個(gè)元素刪除，而不會(huì)破壞2-3樹的任何性質(zhì)(刪除這個(gè)元素不會(huì)引起高度的變化)。
當(dāng)待刪除元素在2節(jié)點(diǎn)的時(shí)候，由于刪除這個(gè)元素會(huì)導(dǎo)致2節(jié)點(diǎn)失去自己唯一的元素，引發(fā)2節(jié)點(diǎn)自身的刪除，會(huì)使得樹中某條路徑的高度發(fā)生變化，樹變得不平衡。
因此我們有兩種方案去解決這個(gè)問題：
- 第一種方案，先刪除這個(gè)2節(jié)點(diǎn)，然后對(duì)樹進(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)(視具體情況而定，在后面的紅黑樹部分會(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)行過了這種操作，所以不可能是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樹的刪除
再看紅黑樹
紅黑樹的節(jié)點(diǎn)
來看它的五條定義：
1.節(jié)點(diǎn)顏色有紅色和黑色
【2-3樹到紅黑樹的轉(zhuǎn)化已經(jīng)解釋過】
2.根節(jié)點(diǎn)必為黑色
【2-3樹中如果根節(jié)點(diǎn)為2節(jié)點(diǎn)，那么它本來就對(duì)應(yīng)紅黑樹中黑節(jié)點(diǎn);如果根節(jié)點(diǎn)為3節(jié)點(diǎn)，也可以用黑色節(jié)點(diǎn)表示較大的那個(gè)元素，然后較小的元素作為左傾紅節(jié)點(diǎn)存在于紅黑樹中】
3.所有葉子節(jié)點(diǎn)都是黑色
【此處提到的葉子其實(shí)是空鏈接，因篇幅問題不便全部畫出】
####4.任意節(jié)點(diǎn)到葉子節(jié)點(diǎn)經(jīng)過的黑色節(jié)點(diǎn)數(shù)目相同
【紅黑樹中的紅節(jié)點(diǎn)是和黑色父節(jié)點(diǎn)綁定的，在2-3樹中本來就是同一層的，只有黑色節(jié)點(diǎn)才會(huì)在2-3樹中真正貢獻(xiàn)高度，由于2-3樹的任一節(jié)點(diǎn)到空鏈接距離相同，因此反應(yīng)在紅黑樹中就是黑色完美平衡】
5.不會(huì)有連續(xù)的紅色節(jié)點(diǎn)
【2-3樹中本來就規(guī)定沒有4節(jié)點(diǎn)，2-3-4樹中雖然有4節(jié)點(diǎn)，但是要求在紅黑樹中體現(xiàn)為一黑色節(jié)點(diǎn)帶兩紅色兒子，分布左右，所以也不會(huì)有連續(xù)紅節(jié)點(diǎn)】
相信在你的視角中，紅黑樹已經(jīng)不再是這五條僵硬的定義了，它背后正浮現(xiàn)著一顆2-3樹概念模型。雖然你已經(jīng)有了這樣的認(rèn)識(shí)，但是紅黑樹作為真正的實(shí)現(xiàn)模型，我們還是要回到這個(gè)實(shí)現(xiàn)本身來探究它的一系列操作。在開始前，我準(zhǔn)備了兩個(gè)基礎(chǔ)知識(shí)，希望能幫助到你。
1.作為二叉查找樹
二叉查找樹的節(jié)點(diǎn)有一個(gè)元素X和兩個(gè)指針域，左指針指向小于X的元素，右指針指向大于X的元素。
假設(shè)我們的插入序列是1~10，那么這顆樹會(huì)演變成只有右鏈接的形式，樹高會(huì)增加到10層，這個(gè)時(shí)候已經(jīng)不具備O(LogN)的查找時(shí)間復(fù)雜度，因?yàn)檫@顆樹退化成了鏈表。
因此對(duì)二叉樹進(jìn)行平衡調(diào)整是很重要的一個(gè)環(huán)節(jié)，無論是AVL還是紅黑樹，它們本質(zhì)上都是希望盡可能保證這顆二叉查找樹中的元素盡量均衡的分布在樹的兩側(cè)。
當(dāng)我們向一顆二叉查找樹中插入一個(gè)元素Y的時(shí)候，我們會(huì)一直與樹中的節(jié)點(diǎn)進(jìn)行大小比較，如果Y小于當(dāng)前元素，就往左走，如果Y大于當(dāng)前元素，就往右走，直到達(dá)到葉子節(jié)點(diǎn)，這個(gè)時(shí)候我們可以把Y插入這顆二叉查找樹了。
由于這次的插入動(dòng)作，整棵樹可能會(huì)發(fā)生一些不平衡，因此我們需要在插入后進(jìn)行一次平衡調(diào)整，使得整棵樹恢復(fù)到平衡的狀態(tài)(具體如何調(diào)整，要看樹是AVL還是紅黑樹亦或是其他的平衡樹)。
二叉查找樹的刪除是一個(gè)很有意思的問題，不同于插入的是，待刪除的元素并不能保證一定出現(xiàn)在樹中的葉子節(jié)點(diǎn)。這將帶來一個(gè)棘手的情景，即我們需要從樹的中間部分取走一個(gè)元素，而且在取走后還需要經(jīng)過調(diào)整來使得整顆樹滿足平衡的性質(zhì)。從樹的中間部分直接取走一個(gè)節(jié)點(diǎn)的場(chǎng)景實(shí)在是太多，也牽扯到了太多相關(guān)的節(jié)點(diǎn)，這種操作很難實(shí)現(xiàn)。
好在有人提出了一個(gè)觀點(diǎn)，我們對(duì)查找樹中一個(gè)節(jié)點(diǎn)的刪除，其實(shí)可以不必真的改動(dòng)這個(gè)節(jié)點(diǎn)的位置。由于查找樹的特殊性質(zhì)，將某個(gè)元素節(jié)點(diǎn)刪除后，它有兩個(gè)最佳替代者，分別是有序序列中的前驅(qū)元素和后繼元素。
我們還是以一個(gè)包含元素1~10的二叉查找樹為例，如果我們希望刪除5所在的節(jié)點(diǎn)，那么讓4或者6替代它的位置都是可行的。作為前驅(qū)元素的4，會(huì)存放在5所在節(jié)點(diǎn)的左子樹的最右側(cè);作為后繼元素的6，會(huì)存放在5所在節(jié)點(diǎn)的右子樹的最左側(cè)。
關(guān)于這個(gè)結(jié)論，大家只需稍加思索便可以明白。
現(xiàn)在我們又讓問題簡(jiǎn)化了，也就是說，刪除某個(gè)節(jié)點(diǎn)的時(shí)候，我們先找到它的前驅(qū)元素或者后繼元素(隨便選一個(gè))，將它的前驅(qū)元素直接填到待刪除的節(jié)點(diǎn)，然后再把它的前驅(qū)元素或者后繼元素刪除。
這個(gè)時(shí)候問題就轉(zhuǎn)化成了在二叉查找樹中刪除一個(gè)沒有左子樹的節(jié)點(diǎn)(或者是一個(gè)沒有右子樹的節(jié)點(diǎn))，我們只需要將這個(gè)節(jié)點(diǎn)刪除再進(jìn)行對(duì)應(yīng)的平衡調(diào)整即可(雖然還是需要調(diào)平，但是比直接在樹中層刪除一個(gè)同時(shí)具備左右兒子的節(jié)點(diǎn)要容易很多)。
注意，此處并沒有強(qiáng)調(diào)是針對(duì)紅黑樹的操作，因?yàn)榧t黑樹和AVL都是二叉查找樹，它們都適用這個(gè)方法。
介紹一下樹的旋轉(zhuǎn)為了調(diào)平一顆二叉樹，使得其左右節(jié)點(diǎn)數(shù)目分布均勻，通常會(huì)選擇旋轉(zhuǎn)的手段。你可以把一顆二叉樹某節(jié)點(diǎn)的左右子樹想象成天平上待稱量的物品，如果哪邊重了，我們就從重的那邊拿出一部分，加到輕的那邊，以此保持相對(duì)的平均。
在二叉樹中這種調(diào)整的操作就是旋轉(zhuǎn)，下面給出了兩個(gè)示例，希望大家能夠仔細(xì)探究，旋轉(zhuǎn)是二叉樹調(diào)平的精髓。
介紹一下樹的旋轉(zhuǎn)
樹的旋轉(zhuǎn)操作
理解了這些之后，再去看紅黑樹的插入刪除，就能夠理解旋轉(zhuǎn)和染色背后的意義了。我們選擇算法4中的左傾紅黑樹作演示：首先看插入
左傾紅黑樹的插入
如圖所示，對(duì)于左傾紅黑樹的插入一共有三種可能的情況。
- 第一種，待插入元素比黑父大，插在了黑父的右邊，而黑父左邊是紅色兒子。這種情況會(huì)導(dǎo)致在紅黑樹中出現(xiàn)右傾紅節(jié)點(diǎn)。
注意，這種情況對(duì)應(yīng)著2-3樹中出現(xiàn)了臨時(shí)4節(jié)點(diǎn)，我們?cè)?-3樹中的處理是將這個(gè)臨時(shí)4節(jié)點(diǎn)分裂，左右元素各自形成一個(gè)2節(jié)點(diǎn)，中間元素上升到上層跟父節(jié)點(diǎn)結(jié)合。所以，我們?cè)诩t黑樹中的動(dòng)作是，將原本紅色的左右兒子染黑(左右分裂)，將黑父染紅(等待上升結(jié)合)。
左傾紅黑樹的插入
- 第二種情況，待插入元素比紅父小，且紅父自身就是左傾。聽起來有點(diǎn)繞，看圖就會(huì)明白，其實(shí)就是說紅父和待插入元素同時(shí)靠在了左邊，形成了連續(xù)的紅節(jié)點(diǎn)。
這種情況我們需要用兩步來調(diào)整。由于我們插入的是紅色節(jié)點(diǎn)，其實(shí)不會(huì)破壞黑色完美平衡，所以要注意的是在旋轉(zhuǎn)和染色的過程種繼續(xù)保持這種完美黑色平衡。
首先對(duì)紅父的父親進(jìn)行一次右旋，這次右旋不會(huì)破壞黑色平衡，但是也沒有解決連續(xù)紅色的問題。
接下來將12所在節(jié)點(diǎn)與15所在節(jié)點(diǎn)交換顏色，這樣的目的是為了消除連續(xù)紅色，并且這個(gè)操作依舊維持了黑色平衡。現(xiàn)在我們已經(jīng)得到了情況1的場(chǎng)景，直接按情況1處理即可。
左傾紅黑樹的插入
- 第三種情況，待插入元素比紅父大，且紅父自身就是左傾。
也就是說插入的這個(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í)，可以體會(huì)到左傾紅黑樹對(duì)于左傾的限制帶來的好處，因?yàn)樵谠瓨浞霞t黑樹定義的情況下，如果父親是紅的，那么它一定左傾，同時(shí)也不用考慮可能存在的右傾兄弟(如果有，那說明原樹不滿足紅黑樹定義)。
這種限制消除了很多需要考慮的場(chǎng)景，讓插入變得更加簡(jiǎn)單。
左傾紅黑樹的刪除
左傾紅黑樹的刪除需要借鑒上文中提到的二叉查找樹通用的刪除策略，當(dāng)我們要?jiǎng)h除某個(gè)節(jié)點(diǎn)的時(shí)候選擇它的前驅(qū)節(jié)點(diǎn)或者后繼節(jié)點(diǎn)元素來替代它，轉(zhuǎn)而刪除它的前驅(qū)/后繼節(jié)點(diǎn)。
在這個(gè)例子中，我選擇用后繼節(jié)點(diǎn)來替代被刪除節(jié)點(diǎn)。
假設(shè)我們需要?jiǎng)h除的節(jié)點(diǎn)它的右子樹如圖所示，那么對(duì)該節(jié)點(diǎn)的刪除實(shí)際上轉(zhuǎn)為了對(duì)2的刪除。
我們從當(dāng)前的根節(jié)點(diǎn)出發(fā)，利于2-3樹中預(yù)合并的策略逐層對(duì)紅黑樹進(jìn)行調(diào)整。具體的做法是，每次都保證當(dāng)前的節(jié)點(diǎn)是2-3樹中的非2節(jié)點(diǎn)，如果當(dāng)前節(jié)點(diǎn)已經(jīng)是非2節(jié)點(diǎn)，那么直接跳過;如果當(dāng)前節(jié)點(diǎn)是2節(jié)點(diǎn)，那么根據(jù)兄弟節(jié)點(diǎn)的狀況來進(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)，我們可以直接將其元素刪除。
左傾紅黑樹的刪除
接下來要考慮的是修復(fù)工作，由于紅黑樹定義的限制，我們?cè)谡{(diào)整的過程中出現(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ì)來到當(dāng)前節(jié)點(diǎn)的位置，然后將右兒子與當(dāng)前節(jié)點(diǎn)交換顏色，我們就將右傾紅節(jié)點(diǎn)修復(fù)成了左傾紅節(jié)點(diǎn)，同時(shí)我們并沒有破壞黑色節(jié)點(diǎn)的平衡。
左傾紅黑樹的刪除
右傾轉(zhuǎn)左傾是一個(gè)很基本的操作，我們以35，44為例，你既可以將35作為黑節(jié)點(diǎn)，44作為右傾紅色兒子;也可以將44作為黑節(jié)點(diǎn)，35作為左傾紅兒子。事實(shí)上我們對(duì)于右傾的修復(fù)就是換了一種樹形而已。一路回溯到當(dāng)前根節(jié)點(diǎn)，直至路徑中不再包含任何的紅色右傾節(jié)點(diǎn)，至此修復(fù)工作全部完成。
總結(jié)
這篇文章的目的旨在從概念模型2-3樹出發(fā)介紹一顆紅黑樹的前世今生。希望大家能夠跳出枯燥的五條定義，更加本質(zhì)地認(rèn)識(shí)紅黑樹中的各種操作來源。
雖然本文只是介紹了相對(duì)簡(jiǎn)單的左傾紅黑樹，但是如果能夠?qū)⒆髢A紅黑樹認(rèn)識(shí)的很清楚，那么普通紅黑樹也只是多了一些情況而已。
對(duì)于還有精力閱讀算法導(dǎo)論的讀者，我給出一點(diǎn)自己的經(jīng)驗(yàn)：
插入階段與左傾紅黑樹比較相似
配圖中的部分節(jié)點(diǎn)標(biāo)識(shí)不太清楚，要反復(fù)對(duì)照原文閱讀
刪除階段，算法導(dǎo)論中將刪除黑節(jié)點(diǎn)X帶來的黑色平衡破壞解釋為，給X的子節(jié)點(diǎn)添上額外的一層黑色，讓X的子節(jié)點(diǎn)變?yōu)椤倦p重黑】或者【既黑又紅】的。
我其實(shí)不太接受這種解釋，經(jīng)過考慮，我認(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)過來。
因此，如果實(shí)在無法理解【雙重黑】，【既黑又紅】，那么直接按照“某條路徑欠黑，所以要想辦法補(bǔ)充一個(gè)黑色節(jié)點(diǎn)”這個(gè)思路來思考吧!
還是刪除階段，四個(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í)候，我們只需要滿足兄弟的右兒子是紅色，就能通過一次調(diào)整來實(shí)現(xiàn)平衡(具體請(qǐng)參照算法導(dǎo)論)。
另外提醒注意的是，一定要想好記憶的順序。算法導(dǎo)論中的刪除調(diào)平4種情況中，只有情況4是絕對(duì)終態(tài)，也就是說到達(dá)了這種狀態(tài)后只需要一次調(diào)整絕對(duì)能達(dá)到平衡。所以我們的出發(fā)點(diǎn)一定是從這種狀態(tài)開始，對(duì)于另外幾種情況，我們要想的不是怎么去達(dá)到最終平衡，而是怎么能讓它一步一步轉(zhuǎn)為情況4。這樣子你的思路就會(huì)清晰很多，記憶的壓力也會(huì)減小。如果細(xì)心的話，你可以回想一下本文是按照怎樣的順序介紹左傾紅黑樹的插入的，為什么是這樣的順序?
一個(gè)數(shù)據(jù)結(jié)構(gòu)可視化網(wǎng)站，它的紅黑樹是基于2-3-4樹的，跟算法導(dǎo)論中基本一樣(除了刪除時(shí)候?qū)η膀?qū)/后繼節(jié)點(diǎn)的選擇)，可以用它當(dāng)做檢驗(yàn)。https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
絮叨最后，如果你被問到紅黑樹，也許你可以試著反問面試官一個(gè)問題：“您應(yīng)該知道紅黑樹的五條定義，如果我構(gòu)造一顆只有黑色節(jié)點(diǎn)的紅黑樹，這樣子可行嗎?因?yàn)檫@樣子沒有破壞任何一條紅黑樹的規(guī)則?！?/p>
如果他回答可行。
繼續(xù)問：“那么請(qǐng)問紅黑樹中要紅節(jié)點(diǎn)干什么呢?紅節(jié)點(diǎn)的真實(shí)意義是什么呢?”
你們的故事就開始了，而我和你的算法故事也才剛開始。
好啦以上就是本期的全部?jī)?nèi)容了，我是敖丙，你知道的越多，你不知道的越多，我們下期見。
當(dāng)前名稱：帶你殺死面試夢(mèng)魘-紅黑樹【圖解】
瀏覽路徑：http://m.fisionsoft.com.cn/article/dpgosej.html
