上一篇寫了關于紅黑樹基本性質的東西，這篇來說一說如何建立一棵紅黑樹吧。
紅黑樹是一種二叉查找樹，那麼我們可以使用插入的方法來建立一棵紅黑樹，為此，我們先來介紹關于紅黑樹的一些基本操作。
1. 旋轉
旋轉是一種能保持二叉查找樹性質的查找樹局部操作，包括左旋和右旋兩種操作。
如下圖所示，在x結點上做左旋時，我們假設它的右孩子不是nil[T]；x可以是樹内任意右孩子不是nil[T]的結點。算法導論裡面講到“左旋以x到y之間的鍊為支軸進行。”我沒太了解這句話，但是我是這麼想象的，如下圖中的曲線箭頭所示，左旋就是x下移，y上移，箭頭所示方向為左，右旋就是x上移，y下移，箭頭所示方向為右。
值得注意的是，在旋轉過程中，隻會有指針結構的變化，不會有顔色的變化，是以在上面的圖中，我沒有畫出結點的顔色。
旋轉的僞代碼，我就不寫了，在算法導論裡面都有，下面我把我寫的旋轉代碼給貼過來吧，當然還是Java版的。
2. 插入
我們來分析一下，在插入過程中可能違反的性質有哪幾個。為此，我把紅黑樹的性質再抄寫一次。
一棵二叉查找樹如果滿足下面的紅黑性質，則為一棵紅黑樹：
1) 每個結點是或是紅的，或是黑的。
2) 根結點是黑的。
3) 每個葉結點（nil[T]）是黑的。
4) 如果一個結點是紅的，那麼它的兩個兒子是黑的。
5) 對每個結點，從該結點到其子孫結點的所有路徑上包含相同數目的黑結點。
首先，我們插入的結點是紅色的，是以不會違反性質1)和性質5)，性質3)自然成立。唯一可能被破壞的是2)和4)。而且，2)和4)至多有一個性質被破壞。性質2)被破壞時的修複很簡單，隻需要将根結點重新着色為黑色即可。而性質4)被破壞的修複則要複雜一些，具體分為三種請況。
情況1)：z的叔叔y是紅色的。
如下圖所示，如果z的叔叔y是紅色的，将z的父結點和y着色為黑色，然後将z的祖父結點着色為紅色，最後将z的祖父結點作為新的z結點進行疊代檢查，因為z的祖父結點原來是紅色的，被着色為黑色的時候，有可能會引起紅黑樹性質的破壞。
情況2)：z的叔叔y是黑色的，而且z是右孩子。
情況3)：z的叔叔y是黑色的，而且z是左孩子。
如下圖所示，如果是情況2)，我們可以立即使用一個左旋變成情況3)。情況3)中，首先交換了B和C的顔色，然後通過一個右旋來使整個樹達到了滿足性質4)。
從這三種情況來看，可以發現一個非常有趣的事情，那就是該過程所做的旋轉從不超過兩次，因為隻有情況1)會繼續将z上移進行紅黑性質檢查，而一旦進入了情況2)或者情況3)，就不會再進行檢查了。
同樣，僞代碼就不寫了，算法導論上都有，在此隻寫Java實作代碼。
ps：寫部落格很累，轉載的朋友請注明出處，謝謝。