紅黑樹(shù)是一種相對(duì)平衡的二叉樹(shù)，它可以在O(log n)時(shí)間內(nèi)做出查找，和二分查找的效率低相似的撼唾。它的用途也非常的廣泛，就目前Java中HashMap哥蔚、TreeMap中都有涉及到紅黑樹(shù)到運(yùn)用倒谷，在移動(dòng)端Android方面，Android的底層Binder架構(gòu)中也有運(yùn)用到紅黑樹(shù)來(lái)存儲(chǔ)binder實(shí)體和引用糙箍。從理論以及運(yùn)用場(chǎng)景可見(jiàn)這種樹(shù)數(shù)據(jù)結(jié)構(gòu)的效率之高寺渗。
性質(zhì)
這里引用Wikipedia中的定義窒典。
紅黑樹(shù)是每個(gè)節(jié)點(diǎn)都帶有顏色屬性的二叉查找樹(shù)涮阔，顏色為紅色或黑色厢汹。
在二叉查找樹(shù)強(qiáng)制一般要求以外课舍，對(duì)于任何有效的紅黑樹(shù)我們?cè)黾恿巳缦碌念~外要求：
1.節(jié)點(diǎn)是紅色或黑色塌西。
2.根是黑色。
3.所有葉子都是黑色（葉子是NIL節(jié)點(diǎn)）筝尾。
4.每個(gè)紅色節(jié)點(diǎn)必須有兩個(gè)黑色的子節(jié)點(diǎn)捡需。（從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)。）
5.從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡(jiǎn)單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)筹淫。
注：如果不明白什么是“二叉查找樹(shù)”的可以去百度谷歌一下站辉，還是很簡(jiǎn)單的這里就不贅述了。
首先看著條條框框的約束條件很多其實(shí)重要的只有第4條和第5條损姜，也是這兩條屬性使得紅黑樹(shù)能有一個(gè)相對(duì)平衡的樹(shù)形結(jié)構(gòu)饰剥。這里上兩個(gè)紅黑樹(shù)的示例圖：
如上面兩張圖，他們都屬于紅黑樹(shù)摧阅。
第一張例圖汰蓉，從根節(jié)點(diǎn)到所有葉子結(jié)點(diǎn)的黑色節(jié)點(diǎn)數(shù)（包括葉子節(jié)點(diǎn)）都是3，并且從任一節(jié)點(diǎn)到葉子節(jié)點(diǎn)到黑色節(jié)點(diǎn)數(shù)目都相同棒卷。樹(shù)中也沒(méi)有出現(xiàn)過(guò)連續(xù)的兩個(gè)紅色節(jié)點(diǎn)顾孽。滿足紅黑樹(shù)的所有性質(zhì)祝钢。
第二張例圖比較極端，所有節(jié)點(diǎn)都是黑色的但也沒(méi)有違反紅黑樹(shù)的性質(zhì)若厚，從根節(jié)點(diǎn)到所有葉子結(jié)點(diǎn)的黑色結(jié)點(diǎn)數(shù)都是4拦英，并且沒(méi)有出現(xiàn)連續(xù)的兩個(gè)紅色節(jié)點(diǎn)相連接（因?yàn)楦揪蜎](méi)有紅色的節(jié)點(diǎn)）。也滿足紅黑樹(shù)的所有性質(zhì)测秸。
2-3-4樹(shù)的引入
對(duì)紅黑樹(shù)有初步了解以后這里再來(lái)看看2-3-4樹(shù)疤估。為什么突然要引入2-3-4樹(shù)？因?yàn)榧t黑樹(shù)其實(shí)就是2-3-4樹(shù)的一種體現(xiàn)霎冯。這里引入2-3-4樹(shù)更多的是為了后面對(duì)紅黑樹(shù)做插入刪除時(shí)的對(duì)比說(shuō)明從而更好的理解紅黑樹(shù)的設(shè)計(jì)思想做裙。如果不理解紅黑樹(shù)的設(shè)計(jì)思想，后面對(duì)紅黑樹(shù)的一系列操作變化都會(huì)成為公式形式的記憶肃晚，過(guò)一段時(shí)間就容易忘記锚贱。
2-3-4樹(shù)的定義
首先先簡(jiǎn)單的說(shuō)明一下2-3-4樹(shù)。2-3-4樹(shù)是一種特殊的多叉查找樹(shù)关串，它的每一個(gè)節(jié)點(diǎn)中可能包含一個(gè)兩個(gè)或者三個(gè)數(shù)據(jù)拧廊。2-3-4樹(shù)不論是在插入還是在刪除時(shí)都能達(dá)到一種實(shí)時(shí)平衡的效果。下面給出2-3-4樹(shù)中可能出現(xiàn)的節(jié)點(diǎn)類(lèi)型：
- 包含一個(gè)數(shù)據(jù)的節(jié)點(diǎn)稱為2node
- 包含兩個(gè)數(shù)據(jù)的節(jié)點(diǎn)稱為3node
- 包含三個(gè)數(shù)據(jù)的節(jié)點(diǎn)稱為4node
另外2-3-4樹(shù)任一節(jié)點(diǎn)到每個(gè)葉子的所有路徑包含的節(jié)點(diǎn)數(shù)都相同（深度相同）晋修。
這里給出一個(gè)2-3-4樹(shù)的示例圖吧碾，里面包含了2-3-4樹(shù)中出現(xiàn)的所有節(jié)點(diǎn)形式。
2-3-4樹(shù)的插入
2-3-4樹(shù)的插入可以簡(jiǎn)單的理解成一種“加法進(jìn)位”墓卦。例如當(dāng)你按照普通二叉樹(shù)的插入規(guī)則插入節(jié)點(diǎn)倦春，最后定位到需要插入到一個(gè)指定的節(jié)點(diǎn)。普通二叉查找樹(shù)可能是直接在節(jié)點(diǎn)下方添加一個(gè)子節(jié)點(diǎn)落剪，而2-3-4樹(shù)當(dāng)中則會(huì)以一種“合并”的方式并入到當(dāng)前節(jié)點(diǎn)當(dāng)中睁本。正因?yàn)檫@種“合并”操作使得2-3-4樹(shù)在插入刪除時(shí)保持實(shí)時(shí)平衡成為可能，因?yàn)槊看尾迦?-3-4樹(shù)的節(jié)點(diǎn)都會(huì)有一次判斷的機(jī)會(huì)（可能時(shí)并入也可能是分裂（進(jìn)位））忠怖，有了這一次操作就可以將暫時(shí)會(huì)導(dǎo)致破壞樹(shù)平衡的新添加的節(jié)點(diǎn)“緩存”起來(lái)呢堰，當(dāng)“緩存”節(jié)點(diǎn)到達(dá)一定的數(shù)量時(shí)就會(huì)分裂提升一級(jí)樹(shù)的高度。這就是2-3-4樹(shù)插入時(shí)能夠達(dá)到實(shí)時(shí)平衡的核心思想凡泣。
下面結(jié)合圖例來(lái)分析2-3-4樹(shù)插入的具體邏輯（注：圖例均選為234樹(shù)的子樹(shù)來(lái)做分析來(lái)減少?gòu)?fù)雜度）枉疼。首先當(dāng)定位到插入的節(jié)點(diǎn)時(shí)一個(gè)2node（節(jié)點(diǎn)中只有一個(gè)數(shù)據(jù)并且擁有兩個(gè)子節(jié)點(diǎn)）時(shí)，插入的數(shù)據(jù)會(huì)被“并入到”2node節(jié)點(diǎn)當(dāng)中鞋拟，然后形成一個(gè)3node節(jié)點(diǎn)骂维。如下圖：
當(dāng)被插入的是3node節(jié)點(diǎn)時(shí)也是一樣的，新數(shù)據(jù)會(huì)被“并入”到3node節(jié)點(diǎn)中形成4node節(jié)點(diǎn)贺纲。如下圖：
當(dāng)插入的是4node節(jié)點(diǎn)時(shí)就需要用到上面提到的“進(jìn)位”操作了航闺。“進(jìn)位”的意思就和我們做加法運(yùn)算時(shí)一樣哮笆，當(dāng)個(gè)位數(shù)據(jù)相加滿十了這時(shí)候就要進(jìn)位到十分位来颤。2-3-4樹(shù)也是一樣的道理汰扭，當(dāng)4node節(jié)點(diǎn)再“并入”節(jié)點(diǎn)時(shí)就會(huì)發(fā)生“進(jìn)位”，分裂出一個(gè)節(jié)點(diǎn)然后插入到父節(jié)點(diǎn)當(dāng)中福铅。稍有不同的地方就是2-3-4樹(shù)當(dāng)中為了保證節(jié)點(diǎn)的位置是采取先分裂“進(jìn)位”再插入的操作萝毛，具體怎么操作可以看下圖：
當(dāng)然有一種情況是進(jìn)位以后父節(jié)點(diǎn)也已經(jīng)是4node了，這樣就會(huì)再次進(jìn)行一次進(jìn)位滑黔，操作和之前是一樣的笆包。這里可以簡(jiǎn)單的把當(dāng)前發(fā)生進(jìn)位（被分裂出來(lái)）的節(jié)點(diǎn)當(dāng)作是一個(gè)新加入的節(jié)點(diǎn)加入到父節(jié)點(diǎn)中，父節(jié)點(diǎn)（即將發(fā)生進(jìn)位）分裂出來(lái)的節(jié)點(diǎn)也當(dāng)作新加入的節(jié)點(diǎn)加入到祖父節(jié)點(diǎn)當(dāng)中就可以了略荡。簡(jiǎn)單的說(shuō)進(jìn)位可以理解成分裂和插入（至于怎么插入繼續(xù)套用上面的邏輯）庵佣，其實(shí)就是一種遞歸，這里就不再上圖描述了汛兜。
2-3-4樹(shù)的刪除
2-3-4樹(shù)的插入可以理解為“進(jìn)位”巴粪，那刪除就可以理解為“借位”，就比如說(shuō)當(dāng)17減8時(shí)各位數(shù)“減不動(dòng)”了粥谬，這個(gè)時(shí)候就需要向十分位去“借一位”2-3-4樹(shù)的刪除也是這個(gè)道理肛根，當(dāng)節(jié)點(diǎn)自己能。
這里3node漏策、4node的刪除就不多做分析派哲，和添加時(shí)一樣，直接拿掉需要?jiǎng)h除的數(shù)據(jù)就可以了掺喻。
這里主要分析一下2node刪除時(shí)的操作邏輯芭届。
首先第一種情況是向兄弟節(jié)點(diǎn)“借位”。有兄弟節(jié)點(diǎn)有多余的數(shù)據(jù)先借過(guò)來(lái)保證樹(shù)結(jié)構(gòu)不變感耙，不然這邊刪除一個(gè)節(jié)點(diǎn)不就多了一個(gè)缺口了褂乍，因此這里需要先找兄弟節(jié)點(diǎn)借。怎么樣的兄弟節(jié)點(diǎn)才能算有多余節(jié)點(diǎn)的兄弟節(jié)點(diǎn)呢抑月？就是一個(gè)節(jié)點(diǎn)內(nèi)有多個(gè)數(shù)據(jù)的也就是3node或者4node树叽；借過(guò)來(lái)以后就可以順利的刪除需要?jiǎng)h除的節(jié)點(diǎn)而不留“缺口”了舆蝴。這里簡(jiǎn)單的說(shuō)就是合并重分配最后移除谦絮。具體操作如下圖：
下面分析另外一種情況就是當(dāng)兄弟節(jié)點(diǎn)沒(méi)有可以借用的數(shù)據(jù)了，這個(gè)時(shí)候就需要找父親節(jié)點(diǎn)去借了洁仗。借完以后父親節(jié)點(diǎn)自然就從原來(lái)的3node降為2node了层皱，就如同個(gè)位不夠問(wèn)十分位借，借完以后十分位減一赠潦。具體操作如下圖：
上面討論的是能夠向父親節(jié)點(diǎn)借到數(shù)據(jù)的情況叫胖，那如果借不到那就會(huì)向父親節(jié)點(diǎn)的兄弟節(jié)點(diǎn)（叔叔節(jié)點(diǎn)）借，這個(gè)時(shí)候你可以簡(jiǎn)單的理解成當(dāng)前父親節(jié)點(diǎn)需要?jiǎng)h除她奥，然后回到剛剛第一種情況來(lái)操作——兄弟能借借兄弟節(jié)點(diǎn)的瓮增，借不到就問(wèn)父節(jié)點(diǎn)借怎棱。這里也是一種遞歸思想，具體流程圖我就不放了绷跑，有興趣可以自己動(dòng)手畫(huà)畫(huà)就很清晰了拳恋。
最后可能存在一種極端情況就是遞歸到根節(jié)點(diǎn)仍然借不到數(shù)據(jù)砸捏，這個(gè)時(shí)候就需要將根節(jié)點(diǎn)和兩個(gè)子節(jié)點(diǎn)合并成為一個(gè)4node梆暖，然后繼續(xù)做刪除借位操作。具體操作如下圖：
這里只分析了兩層，其實(shí)多層的情況也是一樣的。
刪除操作相比添加操作稍微有一些復(fù)雜俺陋，這里做一個(gè)小結(jié)：刪除的核心思想其實(shí)就是和減法運(yùn)算是一樣的，當(dāng)個(gè)位不夠用時(shí)向十位借缴挖，十位也不夠用的時(shí)候就向百位借，就這樣循環(huán)遞歸。只不過(guò)2-3-4樹(shù)中的刪除操作在借位時(shí)多加上一步檢查兄弟節(jié)點(diǎn)是否有可借用的數(shù)據(jù)這一步瘫析，本質(zhì)上是一樣的咸包。
紅黑樹(shù)和2-3-4樹(shù)之間的聯(lián)系
紅黑樹(shù)通過(guò)添加顏色這一屬性讓二叉樹(shù)擁有了2-3-4樹(shù)的結(jié)構(gòu)特性，紅色節(jié)點(diǎn)向上連接的線可以看作是“紅線”，而由“紅線”相連的多個(gè)節(jié)點(diǎn)即為一個(gè)2-3-4樹(shù)中的“多node”。因此紅黑樹(shù)也將擁有2-3-4樹(shù)的“緩存”能力來(lái)保證實(shí)時(shí)的平衡注竿。
紅黑樹(shù)轉(zhuǎn)化為2-3-4樹(shù)
紅黑樹(shù)轉(zhuǎn)化為2-3-4樹(shù)的規(guī)則就是通過(guò)顏色。
- 紅色節(jié)點(diǎn)向上的連接線為紅線
- 通過(guò)紅線連接起來(lái)的節(jié)點(diǎn)為n-node（n可以是2或者3）
這么形容可能有一點(diǎn)抽象，這里我就把上圖紅黑樹(shù)示例中一個(gè)圖為例子將它轉(zhuǎn)化為2-3-4樹(shù)：
（這里圖拉長(zhǎng)就很小了，所以放在兩行展示清楚一點(diǎn)。這里面總共包含了三步轉(zhuǎn)換）
好了到了這里紅黑樹(shù)和2-3-4樹(shù)之間的聯(lián)系已經(jīng)很明顯了吧侥祭。
總結(jié)一下：紅黑樹(shù)經(jīng)過(guò)轉(zhuǎn)換可以看作是一個(gè)2-3-4樹(shù)，而這個(gè)轉(zhuǎn)換的關(guān)鍵就是找到“紅線”欢伏。從2-3-4樹(shù)的角度看，2-3-4樹(shù)因?yàn)橛兄?jié)點(diǎn)“緩存”的能力因此可以在插入刪除節(jié)點(diǎn)時(shí)保持樹(shù)的平衡。而紅黑樹(shù)作為2-3-4樹(shù)的另一種展現(xiàn)形式自然也擁有著插入刪除節(jié)點(diǎn)時(shí)對(duì)樹(shù)進(jìn)行調(diào)整至平衡的方法抱究。
上面花了大半篇幅介紹2-3-4樹(shù)其實(shí)主要還是為了說(shuō)明紅黑樹(shù)在添加刪除操作時(shí)和2-3-4樹(shù)之間的聯(lián)系勋磕，剩下的紅黑樹(shù)的添加刪除操作的理解我就放在后面一篇文章去分析了苦银。
