紅黑樹是60年代中期計算機科學界找尋一種算法復雜度穩定，容易實現的數據存儲算法的產物。在優先級隊列、字典等實用領域都有廣泛地應用，更是70年代提出的關系數據庫模型--B樹的鼻祖。在Linux kernel中，高精度定時器也工作在紅黑樹之上。為便於初學者掌握其基本算法，本文一步一步地演示了紅黑樹的創建過程。
首先回顧一下紅黑樹的基本性質：
1. 紅黑樹本質上是一個二叉查找樹（BST），但是它從根到最遠葉子的長度不會超過到最近葉子長度的兩倍，因此是近似平衡的。
2. 紅黑樹的節點不是黑的就是紅的，不會有第三種顏色。
3. 樹根必須是黑色。
4. 葉子所指的空節點必須是黑色。
5. 如果某個節點是紅色，那麼它的兩個兒子必須都是黑色。
6. 從任意節點出發的所有向下的路徑上包含相同個數的黑節點。這個個數我們稱為黑高度Bh。
有了上面的認識，我們要從無到有構造一顆紅黑樹的話，心裡就有底了。這個構造的過程可以分兩步：
第一步：執行BST的插入算法；
第二步：對節點著色；
第一步不會有什麼問題，關鍵是第二步怎麼對節點著色才不會違反紅黑樹的基本性質；
這是一個難點，我在寫這篇文章的時候腦子也卡了一下，節點不多的時候好辦，但是如果節點很多了，就必須找到一種普遍適用的算法來處理。通過這兩天的觀察，我發現這六條性質中最關鍵的其實是最後一條---從任意結點出發的任意路徑黑高度相等！這才是紅黑樹算法保持近似平衡的精華所在！其它性質要麼是這條性質的產物，要麼就是為這條性質服務的。
現在我演示一下怎麼從無到有生成一棵紅黑樹。
例如我們有一組數：{9，7，15，6，11，19}，現在按照從左到右的順序存放在一顆紅黑樹中。
第一個數是9，很自然地成為了樹根，如圖：
圖-1
每個新節點都默認地被渲染成了紅色，為什麼要這麼做呢？後面我們將會看到它的好處！現在先忽略不談。
根節點9是紅色，這違背了性質3，所以必須改成黑色，如圖：
圖-2
下一個數字是7，顯然要被插入到9的左邊，並且這時滿足紅黑樹的所有性質，如圖:
圖-3
下一個數字是15，要插入到9的右邊，並且也滿足紅黑樹的所有性質，如圖：
圖-4
下一個數字是6，要插入到7的左邊，這回似乎有麻煩了，性質5被違背了，如圖：
圖-5
可能有人會說，那很簡單，既然違背了性質5，那我改一下6的顏色不就OK了？
圖-6
現在，恭喜你---也走進了我曾經走過的誤區：）你的無意之舉改變了新增節點路徑上面的黑高度，這棵樹已經不是紅黑樹了！
寫代碼的人都知道，對樹的遍歷，最簡單的方法就是遞歸，那麼樹的數學模型就是一個可窮舉的遞歸式。遞歸式中每一步的正確性都建立在前一步正確的基礎之上。現在我們回過頭來想想為什麼每次插入的新節點都被渲染成紅色呢？你肯定猜到了，因為我們要保證紅黑樹的核心性質--黑高度不發生變化，雖然犧牲了性質5，但這是可以補救的，並且代價很小。再來看看圖-5
既然我們不能通過改變新插入節點的顏色來維持紅黑樹的性質，那麼就只好從原來的樹結構入手了。
我們注意到新插入的節點的父親是一個紅節點，其叔叔也是一個紅節點。那麼假如我把它的父親改成黑色，則恢復了性質5，可是從樹根出發的黑高度還是不相等，干脆把它的叔叔也改成黑色吧！結果如下：
圖-7
現在它滿足紅黑樹所有的性質。好了，我們繼續。
插入數字11和19的過程平淡無奇，不深入探討，最終的樹如圖：
圖-8
如果現在要插入數字10怎麼辦？它肯定會是11的左節點：
圖-9
明顯違背了性質5！難道依葫蘆畫瓢，把11和19都改成黑色？這樣從樹根出發的左邊路徑黑高度還是2，而右邊兩條路徑的黑高度將變成了3，老辦法失效了！
圖-10
其實不然，改了新增節點的父親和叔叔的顏色以後，右邊路徑黑高度全加一，但我們只要把它的爺爺改成紅色不就又減去了多出來的黑高度嗎？
圖-11
如果你認真看到這裡，我想你的潛意識一定告訴你---這裡存在某種規律等著我們去發現。
讓我們再仔細審視一下圖-5
在生成樹的過程中，我們已經兩次遇到類似情況了，歸納一下，這個場景就是：新節點的父親是紅色，叔叔也是紅色。
至於別的節點，我們大可不必關心，因為很顯然，這個場景是原子的。
我們的處理辦法是把7和15渲染成黑色，就像圖-7那樣，可是因為這是一個普遍適用的場景，所以要做一個擴展：假設在這個原子樹的每個節點上還有別的分支。那麼圖-7就不能保證所有路徑的黑高度相等了，即使把9改成紅色也無濟於事，因為9也許還有父節點，所以也許它的父節點又是紅色，這就再次違反了性質5。我最喜歡的作家之一--柯南.道爾，曾說過：“歷史就像車輪的輻條，每一根都終將再次轉回來。”眼前的場景正是如此---我們設計的原子場景再次出現。
一個清晰的遞歸算法呈現在我們面前：
1. 新增節點渲染成紅色；
2. 如果它的父親是紅色，則違反了性質5；
3. 如果它的叔叔也是紅色，則通過同時修改其父親和叔叔的顏色為黑色來恢復性質5；
4. 如果它的爺爺不是根節點，則有可能在另外的路徑上再次違反性質5，於是我們把它的爺爺改成紅色；
5. 可是如果他的太爺爺也是紅色呢？很自然地，我們重新回到步驟2；
6. 不斷循環，直到第二步滿足就可以結束。
最後留給感興趣的同學兩個問題：
1. 如果新增節點的父親是紅色，但它的叔叔是黑色，該怎麼辦？（提示：使用旋轉）
2. 有人說，下面這種場景，我設計的算法就失效了，真的嗎？（粉色的6是新插入的節點）
Linux內核之於紅黑樹and AVL樹 http://www.linuxidc.com/Linux/2015-07/119425.htm
AVL樹 VS 紅黑樹 http://www.linuxidc.com/Linux/2014-04/99736.htm
紅黑樹插入操作的C++實現 http://www.linuxidc.com/Linux/2012-11/74483.htm
