因為看EHCache中溢出文件的管理代碼，它用到了AA－Tree作為文件中的磁盤管理，因而決定先復習以下紅黑樹(RBT, Red Black Tree)，順便看看TreeMap的代碼。關于紅黑樹，網上已經有各種相關的文章了，因而屬于多一篇不多，少一篇不少的狀態，因而我純粹當作是我自己理解的紀錄，加深印象，如果能對部分思路和我類似的人有一些幫助，那就最好了。基于這樣的目的，我并不打算深入，如果想看更深入的或者更好的，可以讀讀我最后的參考鏈接。

紅黑樹引入的目的
首先要從對有序序列的查找問題開始，對一個靜態的有序序列數組，只需要二分查找即可得到O(log(n))的查找效率；然而實現并不會顯得那么“靜態”，需要實現動態的插入、刪除同時保持序列的有序性，并且盡量提高插入、刪除、查找的效率。

為實現動態插入、刪除，最簡單的實現是二叉排序樹(BST, Binary Sort Tree)，它具有以下性質：
1. 它可以是一個空樹。
2. 若它的左子樹不為空，則它的左子樹所有節點的值均小于根節點的值。
3. 若它的右子樹不為空，則它的右子樹所有節點的值均大于根節點的值。
4. 它的左子樹和右子樹都是一個二叉排序樹。
根據以上性質，
對查找，比較查找數和當前節點，如果查找數和當前節點相等，則找到返回；如果查找數小于當前節點，查找其左子樹，如果查找數大于當前節點，查找其右子樹，直到找到或直到葉子節點為null，返回null。
對插入，先查找這棵樹，如果找到已存在的節點，更新節點值，否則把新值插入到最后一個為null的節點中。
對刪除，首先找到要刪除的節點，a）如果找到的節點P沒有子節點，直接刪除即可；b）如果找到的節點P只有左子樹或右子樹，刪除該節點，并將其父節點原來的指針指向它唯一的左子樹、或右子樹即可；c）如果找到的節點P既有左子樹又有右子樹，可以有兩種做法：I）刪除節點P，把節點P的父節點原來指向P的指針指向節點P的左字節點，而將節點P的右節點插入到節點P右節點的最右葉子節點上（如果節點P是其父節點的右節點，則將節點P的父節點原來指向P節點的指針指向P節點的右子樹，而將節點P的左子樹插入到節點P最左葉子節點上），II）將節點P替換成節點P的直接前驅（或直接后繼），然后刪除節點P的直接前驅（或直接后繼）（注：直接前驅查找：節點P左子樹的最右節點，直接后繼查找：節點P右子樹的最左節點）。
二叉排序樹實現比較簡單，但是它查找效率卻不理想，最好的效率是O(log(n))，最會效率為O(n)。

為了提高查找效率，后來有人提出了平衡二叉樹（AVL樹），它具有二叉排序樹的所有特點，并添加了以下性質：
1. 左子樹和右子樹的深度之差絕對值不超過1。
2. 左子樹和右子樹都是平衡二叉樹。
為了實現平衡二叉樹，需要在沒個節點上添加平衡因子字段，在插入后，如果發現平衡因子不符合性質1，則需要經過旋轉以調整。平衡二叉樹可以保證其查找的最好、最壞查找時間復雜度都為O(log(n))。

紅黑樹是平衡二叉樹的變種，它是一種自平衡的二叉排序樹，也需要通過一些旋轉調整以保持它的性質，它的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年寫的一篇論文中獲得的。不同于平衡二叉樹的高度平衡，紅黑樹只能保證從根到葉子節點的最長路徑不超過最短路徑的2倍，因而它的最壞查找時間復雜度為O(2log(n + 1))，然而有研究表明它的統計性能要好于平衡二叉樹，因而它具有更廣泛的應用。

紅黑樹的性質
一棵樹需要滿足以下性質才能保證它是一顆紅黑樹：
1. 它是一顆二叉查找樹（BST）。
2. 它的所有節點是紅色或黑色。
3. 它的根節點是黑色。
4. 它的葉子節點是黑色（空節點視為葉子節點）。
5. 它的紅節點的子節點必須是黑色的；而黑節點的字節點可以是黑色或紅色。
6. 它任一節點到其后代的葉子節點路徑上有相同的黑色節點數。
一般的文章都是把性質列出來，然后根據這些性質來寫代碼實現（我也一樣:)），但是如何得出這些性質呢？多問幾個為什么總是好事，這個問題需要去讀上面提到的論文，我沒讀過也不打算讀，這貌似不是我能涉及的，那就提出問題不回答了。。。

TreeMap中紅黑樹的節點
對一顆樹的節點，最基礎是該節點的值、左節點指針、右節點指針。對TreeMap，因為它存儲的是鍵值對，因而它包含了key、value，為了紀錄節點的顏色，它還需要有color字段：

TreeMap中紅黑樹節點插入
紅黑數的插入分以下步驟：
1. 如果當前為空樹，插入節點直接作為根節點，并將該節點顏色比較
2. 以二叉排序樹的查找算法查找當前樹，如果在當前樹中找到已存在的節點，更新節點的值，并返回。
3. 否則，創建一個新節點，將其插入到最后一個查找到的葉子節點上，其初始顏色為紅色。
4. 如果新插入節點的父節點是黑節點，則沒有破壞當前紅黑樹的性質，直接返回。
5. 如果新插入節點的父節點是紅節點，則需要做一些調整。
在TreeMap中，key值的比較可以通過構造TreeMap傳入的Comparator實例，如果沒有Comparator，則key必須實現Comparable接口作為比較邏輯，key不可以為null。以二叉排序樹的算法插入新節點的代碼比較簡單：

TreeMap中紅黑樹新節點插入后調整
紅黑樹的調整比較復雜，首先它會從當前節點向上查找，直到當前節點為null，或是root節點，或者當前節點的父節點顏色不是紅色，然后根據以下不同情況做處理（設當前節點為C（紅色），其父節點為P（紅色），其祖先節點為A（黑色），其叔叔節點為U（待定））：
1. P是A的左子樹，U節點顏色為紅色，此時不管C是節點是P的左子樹還是右子樹，只需要將P和U設為黑色，A設為紅色，則可保證當前局部樹符合紅黑樹定義，把A作為新插入節點重新調整，如果當前樹已經是整棵樹，則因為根節點為紅色，不符合紅黑樹定義，此時只需要將根節點顏色設置為黑色即可，即fixAfterInsertion()最后一句代碼的作用。
2. P是A的左子樹，U節點顏色為黑色，C是P的左子樹，將P設置為黑色，A設置為紅色，并對A做右旋操作。此時C的父節點已變為黑色，循環可以直接退出。
3. P是A的左子樹，U節點顏色為黑色，C是P的右子樹，此時只需要先對P左旋，然后設置C為黑色，A為紅色，并對A右旋，此時P的父節點已變為黑色，循環可以直接退出。
如下圖所示：

代碼：
4. P是A的右子樹，U節點顏色為紅色，此時不管C是節點是P的左子樹還是右子樹，只需要將P和U設為黑色，A設為紅色，則可保證當前局部樹符合紅黑樹定義，把A作為新插入節點重新調整，如果當前樹已經是整棵樹，則因為根節點為紅色，不符合紅黑樹定義，此時只需要將根節點顏色設置為黑色即可，即fixAfterInsertion()最后一句代碼的作用。
5. P是A的右子樹，U節點顏色為黑色，C是P的右子樹，將P設置為黑色，A設置為紅色，并對A做左旋操作。此時C的父節點以變為黑色，循環可以直接退出。
6. P是A的右子樹，U節點顏色為黑色，C是P的左子樹，此時只需要先對P左旋，然后設置C為黑色，A為紅色，并對A右旋，此時P的父節點已為黑色，循環可以直接退出。
如下圖所示：

代碼：

TreeMap中紅黑樹節點刪除
紅黑樹的刪除類似二叉查找樹刪除邏輯類似，在對同時有左子樹和右子樹存在時，TreeMap選擇先將要刪除的節點替換成其直接后繼節點，然后刪除其直接后繼節點（其直接后繼節點不可能同時存在左子節點和右子字節點）。對紅黑樹，由于紅色節點不影響路徑計算（性質6），因而對紅色節點可以直接刪除。然而在刪除黑色節點時，如果刪除的節點不是樹的唯一節點，那么在某些路徑上的黑色節點數會發生改變，破壞性質6；如果被刪除的唯一子節點為紅色，而父節點也為紅色，那么性質5被破壞，因為存在紅色節點的子節點為紅色；如果刪除的是根節點，而它的唯一子節點是紅色，則性質3被破壞。因而需要做一些調整。

TreeMap中紅黑樹刪除黑色節點后調整
調整的邏輯分以下步驟來考慮（假設新替換的節點為C，即代碼中的x參數，C的父節點為P，C是P的左子節點，C的兄弟節點為S，S的左子樹為SL，S的右子樹為SR）：
1. 如果C為紅色，直接將C標記為黑色即可，因為刪除的黑節點數被該節點補上，該樹已經恢復成一顆紅黑樹。
2. 如果C為黑色，且C為根節點，直接返回。
3. 如果C為黑色，且S為紅色，那么節點P、SL、SR都為黑色，此時設置P為紅色，S為黑色，對P左旋，并重新計算S，即S變為SL，即把問題轉換為兄弟節點為黑色的情況。圖片來自http://blog.csdn.net/v_JULY_v/article/details/6105630，自己畫太麻煩了，雖然圖片的命名規則和我的不一樣，湊合的看把，囧。
 
4. 如果C為黑色，S為黑色，且SL、SR都為黑色，將S設置為紅色，P賦值給C，重新計算。

5. 如果C為黑色，S為黑色，且SL為紅色，SR為黑色，那么設置SL為黑色，S為紅色，對S右旋，重新設置S為SL。

6. 如果C為黑色，S為黑色，且SR為紅色，SL為任一顏色，則把S節點的顏色設置為P節點的顏色，設置P節點的顏色為黑色，SR節點的顏色為黑色，對P節點右旋，算法結束。
 
當C為P的右子節點時，其邏輯和以上對稱，不再贅述。

TreeMap中紅黑樹節點查找
紅黑樹的節點查找同二叉查找樹邏輯，不再贅述。這里有一點不太明白：getEntryUsingComparator()方法注釋中說它從getEntry()方法提取出來是為了性能上的考慮，這是為什么？

TreeMap中其他方法
TreeMap中其他方法實現比較直觀，只要理解了紅黑樹，基本上很容易理解，不再贅述。

參考鏈接：