作為一種數(shù)據(jù)結(jié)構(gòu)，紅黑樹可謂不算樸素，因為各種宣傳讓它過于神秘，網(wǎng)上搜羅了一大堆的關(guān)于紅黑樹的文章，不外乎千篇一律，介紹概念，分析性能，貼上代碼，然后給上罪惡的一句話，它最壞情況怎么怎么地...

我們想，一棵二叉樹怎么就是最壞情況，那就是它退化為一個鏈表，這樣查找就成了遍歷。問題是，平衡二叉樹怎么會退回鏈表！它是怎么保持平衡的？能不能簡單地闡述？當然可以！一般的講述紅黑樹的資料都是直接給出黑節(jié)點相同，紅節(jié)點不連續(xù)等來作為一個足夠硬但是又不是太硬的約束來保證樹的平衡，但事實上，它還有更加簡單的理解方式。

1.查找-在高度不在寬度

對于查找而言，如果一棵二叉樹的高度是N，那么最多可以在N步內(nèi)完成查找，這個不用解釋，解釋這個有點喧賓奪主了。這就是說，樹的高度要盡可能矮?？紤]到查找的平均情況，葉子節(jié)點到根節(jié)點的距離不能差別太大。

2.二叉樹的不平衡根源

一棵樹在查找看來變得不平衡是因為子樹的高度相差很大。

二叉樹為什么會這么容易變得不平衡，很簡單，因為它只有二叉，左右均有50%的概率，那么插入N個節(jié)點全部都是左節(jié)點或者右節(jié)點的概率就是50%的N次方，如果是8叉樹，那么這個概率就是12.5%的N次方，哪個概率大，自己算。

3.多叉樹-寬度換高度

在第1節(jié)以及第2節(jié)，我們已經(jīng)知道，樹的寬度越大，高度越小，這樣查詢起來越快，Cisco路由器里不是有256叉乃至1024叉樹嗎？但是這樣真的很好嗎？對于稀疏節(jié)點，這樣會嚴重消耗內(nèi)存。

如果我們考慮CPU的MMU系統(tǒng)，就會知道，二級頁表和三級頁表的區(qū)別就在于對付稀疏地址空間的效果不同。

4.權(quán)衡-2，3樹

我們發(fā)現(xiàn)，道生一，一生二，二叉樹是一個完美的開始，但是我們發(fā)現(xiàn)它特別容易傾斜，傾斜的時候別觸摸。我們也不能一下子就上256叉樹，即使那樣在海量節(jié)點情況下也抗不住，因此這種盲目寬度換高度的方案沒有可擴展性。我們需要找出一種動態(tài)的機制，讓一棵樹動態(tài)調(diào)整保持平衡。

為了更加容易找出這個機制，讓它更加容易現(xiàn)形，暫時不斷增加樹的寬度，如果增加到3叉樹還找不到方案，就增加到4叉樹...我們說的N叉樹并不是說一個節(jié)點一定有N個子節(jié)點，而是說它最多有N個子節(jié)點。

迄今為止，以前都是我自己形而上的觀點，幾年前我的想法就到此為止，原因在于那段時間特別郁悶，就想找出些技術(shù)上的形而上思想，可是突然自己變好了，就沒有繼續(xù)下去。幸運的是，我現(xiàn)在發(fā)現(xiàn)確實有這么一個方案，而紅黑樹就是從3叉樹回退過去的。

讓我高興的是，我的思路并沒有跑偏。

5.2-3樹的平衡變換

如果是二叉樹，那么你插入一個節(jié)點，你只有最多1次機會保持子樹的高度不變，如果是一個三叉樹，那么就有2次機會。現(xiàn)在開始，我們?yōu)槎鏄涮砹艘徊妫兂闪巳鏄洹?/p>

二叉樹的時候，一個節(jié)點有兩個分支，三叉樹的時候，有三個分支。一個點可以將區(qū)間分為兩個部分區(qū)域，要想將一個區(qū)間分為三個部分區(qū)域，就需要兩個點，因此三叉的情形下，節(jié)點存儲的是兩個點而不是一個，如下圖所示：

現(xiàn)在考慮插入一個新節(jié)點，這個2-3樹怎么保持平衡。非常簡單，我們知道，插入的位置一定是葉子，假設(shè)當前的樹是平衡的，現(xiàn)在分兩種情況：

1).插入的新葉子節(jié)點的父節(jié)點是一個二叉節(jié)點

這種情況最簡單，二叉節(jié)點變?nèi)婀?jié)點即可，如下圖所示：

2).插入的新葉子節(jié)點的父節(jié)點是一個三叉節(jié)點

這種情況比較復(fù)雜。樹總是要長高的，保持平衡的方式就是同時長高，而這是不可能的，插入一個節(jié)點只能讓該節(jié)點所在的子樹長高。然而，如果能將這個信息上升到根部，在根部長高，就實現(xiàn)了“同時長高”！
還是循著上面的那個思路，我們繼續(xù)增加樹叉的數(shù)量，我們把它增加到4！新節(jié)點的插入如下圖所示：

很遺憾，沒有完成任務(wù)，但是最終我們提出了兩個問題，只要解決了這兩個問題，所有問題就解決了。

解決這兩個問題，無疑都要牽扯到節(jié)點P的父節(jié)點以及再往上的節(jié)點，有兩種可能：

可能性1：P的父節(jié)點PP是一個二叉節(jié)點
這個太爽，我們直接把P以及它的子樹全部提到PP節(jié)點即可，類似B插入的情景，如下圖所示：

問題2解決。

可能性2：P的父節(jié)點PP是一個三叉節(jié)點
這就有點不好辦了，不過有最后一擊！不管怎樣先把P節(jié)點以及其子節(jié)點全部上提到PP，保持最底部的平衡性，這樣就可以遞歸解決了，此時我們又一次遇到了往一個三叉節(jié)點里面插入子節(jié)點的問題了，為了不增加樹高，唯一的方式就是膨脹成一個四叉節(jié)點-寬度換高度。如下圖所示：

最后，我們發(fā)現(xiàn)，在遞歸的過程中，要么碰到了P..P是個二叉節(jié)點，此時按照問題2的解決方式將當前節(jié)點的值直接提到P...P中，其子樹降低一個高度，抵消增加的高度，平衡保持，遞歸結(jié)束，要么遞歸到了根節(jié)點，此時只需要一個分裂操作即可完美結(jié)束！

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【749907784】整理了一些個人覺得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書、實戰(zhàn)項目及代碼)? ??

6.演進到紅黑樹

很顯然，通過上面的描述，我們似乎找到了一個使樹保持平衡的方案，而且是相當完美的平衡！核心就是寬度和高度之間的博弈。我們總是可以用一個寬度抵消一層高度，整個過程就是一次或者多次的一加一減，最終的結(jié)果還是0！
然而，這也不再是二叉樹了，有的節(jié)點變成了三叉，并且保存了兩個值，該兩個值將區(qū)間分割成了三部分，是為三叉！因此在使用上就不如二叉樹方便，比較操作復(fù)雜化了。事實上，將三叉節(jié)點處理成二叉節(jié)點，這棵樹就成了紅黑樹！怎么處理呢？很簡單！如下圖所示：

看到了吧，紅色節(jié)點就是從2-3樹中分出來的，為了維持一棵二叉樹而不是2-3樹，必須將三叉節(jié)點變成二叉節(jié)點，這是一個寬度換高度得回退，即高度換寬度，當然代價就是不再完美平衡。

按照以上的這個變換，你自己試試看，可以變出兩個連續(xù)的紅節(jié)點嗎？NO！還在糾結(jié)紅黑樹的性質(zhì)概念嗎？看了它的演進，你會發(fā)現(xiàn)，很多紅黑樹的復(fù)雜概念和讓人沒有頭緒的性能都是自然而然的。下面我們來看一下它的最壞情況是什么。

還是以2-3樹分析，如果在一棵2-3樹中，最左邊路徑上的節(jié)點全部是三叉節(jié)點，而最右邊路徑上的節(jié)點都是二叉節(jié)點，那么把它變換成二叉紅黑樹之后，就會發(fā)現(xiàn)最左邊的路徑上是紅黑間隔的節(jié)點，而最右邊的路徑上全部是黑節(jié)點，它們的高度差接近2倍。出現(xiàn)這樣的情況是令人悲哀的，但是也是極低概率的。

紅黑樹的所有包括旋轉(zhuǎn)等操作，都可以映射到2-3樹中，而我們對2-3樹以及高度和寬度之間的博弈已經(jīng)足夠理解了。請再次去理解紅黑樹吧，再看看它的性質(zhì)和概念，together with左旋和右旋，是不是有一種新的體會呢？

原文作者：極客重生