近期看io相關文章，在看到linux下epoll組織結構的時候，偶然發(fā)現(xiàn)epoll居然也是用紅黑樹作為socket的存儲結構。意識到紅黑樹確實是一個性能很良好的組織結構。之前也瀏覽過幾次紅黑樹相關的操作原理，但都沒能理解透徹，這次，希望能夠把它研究透徹，并把它記錄下來。
這一篇，先分析紅黑樹的添加。（以TreeMap源碼作分析）
1，首先，按照先根遍歷找到需要添加節(jié)點的父節(jié)點及在父節(jié)點上的插入位置（左孩子還是右孩子）。
2，然后將此狀態(tài)下的該插入節(jié)點x（默認為紅色）到爺爺節(jié)點g（包含叔叔節(jié)點ps,和堂兄弟節(jié)點psl,psr）的數(shù)據(jù)結構畫出來（只以插入節(jié)點的父親節(jié)點p為pp的做孩子距離，反之鏡像操作）
case1：要插入的節(jié)點是根節(jié)點，這時直接將x置為黑色
case2：p為黑色，這時整棵樹自然符合紅黑樹特性，所以不用做任何操作
case3: p為紅色，ps也為紅色，將p和ps置為黑色，g置為紅色，這樣，就保證g以下符合了紅黑樹的特性，但是因為p換了顏色，將g傳遞給x作遞歸操作。
case4：p為紅色 ，ps為黑色，這時又分兩種情況：
? ? ? ? case4-1: x是p的左孩子，這時x和p同為紅色且緊鄰，這時單純的通過變色已經不能滿足紅黑樹的特性，所以，還要借用旋轉來平衡整棵g以下的紅黑樹，注意，在這里，旋轉在不變色的基礎上并不會立刻改變紅黑樹的既有情況，而是將插入節(jié)點后所得的g以下的紅黑樹更加平衡，再結合變色控制使得整棵樹符合紅黑樹特性。更通俗的講就是將左樹的某一個紅色節(jié)點移到g節(jié)點，然后進行變色。
? ? ? ? case4-2：x是p的右孩子，這時x和p同為紅色且緊鄰，這時同樣期望通過右旋轉來達到平衡整個紅黑樹的目的，但是因為p的左孩子長度不夠，暴力右旋轉的話，會將左子樹的bh（黑色節(jié)點路徑總數(shù)）變小，改變了原有紅黑樹的特性，這違反了紅黑樹的原則，所以，解決辦法是將x先左旋轉，使得g左子樹bh足夠長，滿足右旋條件，再進行右旋轉，最后通過變色方式使得整個樹維持紅黑樹的特性。
最后，附上TreeMap中插入關于紅黑樹特性調整部分源碼，加深理解。
總結一下轉換原則，1，如果可以僅僅通過變色來使得紅黑樹平衡，則只進行變色2，如果需要進行旋轉的話，旋轉的反方向孩子側要確保比旋轉側方向孩子樹高高出兩層，才能保證旋轉后有平衡的可能性，如果此時紅黑樹平衡，則不需要后續(xù)操作，3，如果此時依然不平衡，則將操作節(jié)點的父節(jié)點置為紅色，來擁有后續(xù)通過變色達到平衡的可能性
