紅黑樹之插入實作紅黑樹

紅黑樹的結點都是紅色或者黑色

根結點是黑色

所有葉子都是黑色（這裡的葉子結點是空結點）

每個紅色結點必須有兩個黑色的子結點

從任何一個節點到其每個葉子的所有簡單路徑都包含相同數目的黑色結點

性質1和性質3總是能夠保持着；

性質4隻有在這些情況下才會發生作用：

增加紅色結點

将黑色結點重新繪制成紅色結點

旋轉

性質5在這些情況下才會發生作用：

增加黑色結點

将紅色結點重新繪制黑色結點

舉例：

用BST的方法将結點插入，将該結點标記為紅色的（因為如果标記為黑色，則會導緻根結點到葉子結點的路徑會多出一個黑結點，無法滿足性質5，而且不容易進行調整），插入的情況包括下面幾種：

插入到一個空的樹，插入結點則為根結點，隻需要将紅色結點重新轉染成黑色結點來滿足性質2；

新結點的父結點為黑色，滿足所有條件；

新結點的父結點為紅色，因為性質2和性質4，是以樹必然有祖父結點，則又包括以下的情況：

新插入結點為父親結點的左子結點，那麼就構成了一個左左的情況，在之前平衡樹中提到過，如果要将其進行平衡，則需要對父結點進行一次單右旋轉，形成一個父親結點為相對根結點，子結點和祖父結點為子結點的樹，同時将父親結點的紅色改為黑色，祖父結點更改為紅色，這下之前無法滿足的性質4和性質5就滿足了；

新插入結點為父親結點的右子結點，那麼就會構成一個左右的情況，在之前的平衡樹也提到過要進行一次雙旋轉，先對新結點進行一次單左旋轉，變成了左左的結構，再進行一次單右旋轉，進而達到滿足所有性質；

父親結點和叔父結點均為紅色，顯然無法滿足性質4，則将父親結點和叔父結點繪制成黑色，祖父結點設定成紅色，但是仍然無法滿足情況，比如考慮到祖父結點可能是根結點，則無法滿足性質2，或者祖父結點的父結點是紅色的，則無法滿足性質4，這時需要将祖父結點作為新的結點來看待進行各種情況的判斷，涉及到對祖父結點的遞歸；

父親結點為紅色同時叔父結點為黑色或者從缺，這裡又分為兩種情況，新插入結點為父親結點的左子結點和右子結點（假設其中父親結點為祖父結點的左子結點），差別在于旋轉的方向，顯然，這棵樹父親結點既然為紅色，那麼其祖父結點則為黑色（性質4），不然無法滿足前提。

父親結點是祖父結點的右結點，參考平衡樹進行相應的操作，原理是一緻的

自然先看頭檔案，如下：

當然，為了使用更友善，還定義了一些紅定義和内聯函數；

真正的實作在這裡，其操作可以參考平衡二叉樹：

      本文轉自zsdnr  51CTO部落格，原文連結：http://blog.51cto.com/12942149/1929342，如需轉載請自行聯系原作者