點擊上方“C語言與CPP編程”，選擇“關注/置頂/星標公眾號”
干貨福利，第一時間送達！
最近有小伙伴說沒有收到當天的文章推送，這是因為微信改了推送機制，有一部分小伙伴刷不到當天的文章，一些比較實用的知識和信息，錯過了就是錯過了，建議大家加個星標??，就能第一時間收到推送。
小伙伴們大家好，我是飛宇。
今天分享一些干的不能再干的干貨-紅黑樹，作為一種數據結構，紅黑樹可謂不算樸素，因為各種宣傳讓它過于神秘，網上搜羅了一大堆的關于紅黑樹的文章，不外乎千篇一律，介紹概念，分析性能，貼上代碼，然后給上罪惡的一句話，它最壞情況怎么怎么地...
我們想，一棵二叉樹怎么就是最壞情況，那就是它退化為一個鏈表，這樣查找就成了遍歷。問題是，平衡二叉樹怎么會退回鏈表！它是怎么保持平衡的？能不能簡單地闡述？當然可以！一般的講述紅黑樹的資料都是直接給出黑節點相同，紅節點不連續等來作為一個足夠硬但是又不是太硬的約束來保證樹的平衡，但事實上，它還有更加簡單的理解方式。
對于查找而言，如果一棵二叉樹的高度是N，那么最多可以在N步內完成查找，這個不用解釋，解釋這個有點喧賓奪主了。這就是說，樹的高度要盡可能矮。考慮到查找的平均情況，葉子節點到根節點的距離不能差別太大。
一棵樹在查找看來變得不平衡是因為子樹的高度相差很大。
二叉樹為什么會這么容易變得不平衡，很簡單，因為它只有二叉，左右均有50%的概率，那么插入N個節點全部都是左節點或者右節點的概率就是50%的N次方，如果是8叉樹，那么這個概率就是12.5%的N次方，哪個概率大，自己算。
在第1節以及第2節，我們已經知道，樹的寬度越大，高度越小，這樣查詢起來越快，Cisco路由器里不是有256叉乃至1024叉樹嗎？但是這樣真的很好嗎？對于稀疏節點，這樣會嚴重消耗內存。
如果我們考慮CPU的MMU系統，就會知道，二級頁表和三級頁表的區別就在于對付稀疏地址空間的效果不同。
我們發現，道生一，一生二，二叉樹是一個完美的開始，但是我們發現它特別容易傾斜，傾斜的時候別觸摸。我們也不能一下子就上256叉樹，即使那樣在海量節點情況下也抗不住，因此這種盲目寬度換高度的方案沒有可擴展性。我們需要找出一種動態的機制，讓一棵樹動態調整保持平衡。
為了更加容易找出這個機制，讓它更加容易現形，暫時不斷增加樹的寬度，如果增加到3叉樹還找不到方案，就增加到4叉樹...我們說的N叉樹并不是說一個節點一定有N個子節點，而是說它最多有N個子節點。
迄今為止，以前都是我自己形而上的觀點，幾年前我的想法就到此為止，原因在于那段時間特別郁悶，就想找出些技術上的形而上思想，可是突然自己變好了，就沒有繼續下去。幸運的是，我現在發現確實有這么一個方案，而紅黑樹就是從3叉樹回退過去的。
讓我高興的是，我的思路并沒有跑偏。
如果是二叉樹，那么你插入一個節點，你只有最多1次機會保持子樹的高度不變，如果是一個三叉樹，那么就有2次機會。現在開始，我們為二叉樹添了一叉，變成了三叉樹。
二叉樹的時候，一個節點有兩個分支，三叉樹的時候，有三個分支。一個點可以將區間分為兩個部分區域，要想將一個區間分為三個部分區域，就需要兩個點，因此三叉的情形下，節點存儲的是兩個點而不是一個，如下圖所示：
現在考慮插入一個新節點，這個2-3樹怎么保持平衡。非常簡單，我們知道，插入的位置一定是葉子，假設當前的樹是平衡的，現在分兩種情況：
這種情況最簡單，二叉節點變三叉節點即可，如下圖所示：
這種情況比較復雜。樹總是要長高的，保持平衡的方式就是同時長高，而這是不可能的，插入一個節點只能讓該節點所在的子樹長高。然而，如果能將這個信息上升到根部，在根部長高，就實現了“同時長高”！
還是循著上面的那個思路，我們繼續增加樹叉的數量，我們把它增加到4！新節點的插入如下圖所示：
很遺憾，沒有完成任務，但是最終我們提出了兩個問題，只要解決了這兩個問題，所有問題就解決了。
解決這兩個問題，無疑都要牽扯到節點P的父節點以及再往上的節點，有兩種可能：
可能性1：P的父節點PP是一個二叉節點
這個太爽，我們直接把P以及它的子樹全部提到PP節點即可，類似B插入的情景，如下圖所示：
問題2解決。
可能性2：P的父節點PP是一個三叉節點
這就有點不好辦了，不過有最后一擊！不管怎樣先把P節點以及其子節點全部上提到PP，保持最底部的平衡性，這樣就可以遞歸解決了，此時我們又一次遇到了往一個三叉節點里面插入子節點的問題了，為了不增加樹高，唯一的方式就是膨脹成一個四叉節點-寬度換高度。如下圖所示：
最后，我們發現，在遞歸的過程中，要么碰到了P..P是個二叉節點，此時按照問題2的解決方式將當前節點的值直接提到P...P中，其子樹降低一個高度，抵消增加的高度，平衡保持，遞歸結束，要么遞歸到了根節點，此時只需要一個分裂操作即可完美結束！
很顯然，通過上面的描述，我們似乎找到了一個使樹保持平衡的方案，而且是相當完美的平衡！核心就是寬度和高度之間的博弈。我們總是可以用一個寬度抵消一層高度，整個過程就是一次或者多次的一加一減，最終的結果還是0！
然而，這也不再是二叉樹了，有的節點變成了三叉，并且保存了兩個值，該兩個值將區間分割成了三部分，是為三叉！因此在使用上就不如二叉樹方便，比較操作復雜化了。事實上，將三叉節點處理成二叉節點，這棵樹就成了紅黑樹！怎么處理呢？很簡單！如下圖所示：
看到了吧，紅色節點就是從2-3樹中分出來的，為了維持一棵二叉樹而不是2-3樹，必須將三叉節點變成二叉節點，這是一個寬度換高度得回退，即高度換寬度，當然代價就是不再完美平衡。
按照以上的這個變換，你自己試試看，可以變出兩個連續的紅節點嗎？NO！還在糾結紅黑樹的性質概念嗎？看了它的演進，你會發現，很多紅黑樹的復雜概念和讓人沒有頭緒的性能都是自然而然的。下面我們來看一下它的最壞情況是什么。
還是以2-3樹分析，如果在一棵2-3樹中，最左邊路徑上的節點全部是三叉節點，而最右邊路徑上的節點都是二叉節點，那么把它變換成二叉紅黑樹之后，就會發現最左邊的路徑上是紅黑間隔的節點，而最右邊的路徑上全部是黑節點，它們的高度差接近2倍。出現這樣的情況是令人悲哀的，但是也是極低概率的。
紅黑樹的所有包括旋轉等操作，都可以映射到2-3樹中，而我們對2-3樹以及高度和寬度之間的博弈已經足夠理解了。請再次去理解紅黑樹吧，再看看它的性質和概念，together with左旋和右旋，是不是有一種新的體會呢？
—— EOF —— 一個我十分佩服的朋友阿秀開發了一個互聯網大廠面試真題記錄網站，支持按照行業、公司、崗位、科目、考察時間等查看面試真題，有意者歡迎掃碼下方二維碼適用~
你好，我是飛宇，本碩均于某中流985 CS就讀，先后于百度搜索以及字節跳動電商等部門擔任Linux C/C++后端研發工程師。
同時，我也是知乎博主@韓飛宇，日常分享C/C++、計算機學習經驗、工作體會，歡迎點擊此處查看我以前的學習筆記&經驗&分享的資源。
我組建了一些社群一起交流，群里有大牛也有小白，如果你有意可以一起進群交流。
歡迎你添加我的微信，我拉你進技術交流群。此外，我也會經常在微信上分享一些計算機學習經驗以及工作體驗，還有一些內推機會。
加個微信，打開另一扇窗
