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

    1.查找-在高度不在寬度對于查找而言，如果一棵二叉樹的高度是N，那么最多可以在N步內完成查找，這個不用解釋，解釋這個有點喧賓奪主了，

真正理解紅黑樹，真正的(Linux內核里大量用到的數據

。這就是說，樹的高度要盡可能矮。考慮到查找的平均情況，葉子節點到根節點的距離不能差別太大。

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

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

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

    5.2-3樹的平衡變換如果是二叉樹，那么你插入一個節點，你只有最多1次機會保持子樹的高度不變，如果是一個三叉樹，那么就有2次機會。現在開始，我們為二叉樹添了一叉，變成了三叉樹。

    1).插入的新葉子節點的父節點是一個二叉節點這種情況最簡單，二叉節點變三叉節點即可，如下圖所示：

    vc+4tNTToaPK99fcysfSqrOkuN+1xKOssaOz1sa9uuK1xLe9yr2+zcrHzazKsbOkuN+jrLb41eLKx7K7v8nE3LXEo6yy5cjr0ru49r3atePWu8TcyMO4w73atePL+dTatcTX08r3s6S436GjyLu2+KOsyOe5+8TcvavV4rj20MXPosnPyf21vbj5sr+jrNTauPmyv7OkuN+jrL7NyrXP1sHLobDNrMqxs6S436Gxo6E8YnIgLyZndDsgICAgICAgu7nKx9Gt18XJz8PmtcTEx7j2y7zCt6OsztLDx7zM0PjU9rzTyvey5rXEyv3Bv6OsztLDx7DRy/zU9rzTtb00o6HQwr3ateO1xLLlyOvI58/CzbzL+cq+o7o8YnIgLyZndDs8YnIgLyZndDs8aW1nIHNyYz0="http://img.blog.csdn.net/20150627234418953?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvZG9nMjUw/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="\" />

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

電腦資料

《真正理解紅黑樹，真正的(Linux內核里大量用到的數據》(http://salifelink.com)。

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

    可能性1：P的父節點PP是一個二叉節點

   

    問題2解決。

可能性2：P的父節點PP是一個三叉節點

   

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

    6.演進到紅黑樹很顯然，通過上面的描述，我們似乎找到了一個使樹保持平衡的方案，而且是相當完美的平衡！核心就是寬度和高度之間的博弈。我們總是可以用一個寬度抵消一層高度，整個過程就是一次或者多次的一加一減，最終的結果還是0！

   

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

按照以上的這個變換，你自己試試看，可以變出兩個連續的紅節點嗎？NO！還在糾結紅黑樹的性質概念嗎？看了它的演進，你會發現，很多紅黑樹的復雜概念和讓人沒有頭緒的性能都是自然而然的。下面我們來看一下它的最壞情況是什么。
還是以2-3樹分析，如果在一棵2-3樹中，最左邊路徑上的節點全部是三叉節點，而最右邊路徑上的節點都是二叉節點，那么把它變換成二叉紅黑樹之后，就會發現最左邊的路徑上是紅黑間隔的節點，而最右邊的路徑上全部是黑節點，它們的高度差接近2倍。出現這樣的情況是令人悲哀的，但是也是極低概率的。
紅黑樹的所有包括旋轉等操作，都可以映射到2-3樹中，而我們對2-3樹以及高度和寬度之間的博弈已經足夠理解了。請再次去理解紅黑樹吧，再看看它的性質和概念，together with左旋和右旋，是不是有一種新的體會呢？