因為看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字段：
private static final boolean red = false;
private static final boolean black = true;
static final class entry<k,v> implements map.entry<k,v> {
k key;
v value;
entry<k,v> left = null;
entry<k,v> right = null;
entry<k,v> parent;
boolean color = black;
....
}
treemap中紅黑樹節點插入
紅黑數的插入分以下步驟：
1. 如果目前為空樹，插入節點直接作為根節點，并将該節點顔色比較
2. 以二叉排序樹的查找算法查找目前樹，如果在目前樹中找到已存在的節點，更新節點的值，并傳回。
3. 否則，建立一個新節點，将其插入到最後一個查找到的葉子節點上，其初始顔色為紅色。
4. 如果新插入節點的父節點是黑節點，則沒有破壞目前紅黑樹的性質，直接傳回。
5. 如果新插入節點的父節點是紅節點，則需要做一些調整。
在treemap中，key值的比較可以通過構造treemap傳入的comparator執行個體，如果沒有comparator，則key必須實作comparable接口作為比較邏輯，key不可以為null。以二叉排序樹的算法插入新節點的代碼比較簡單：
public v put(k key, v value) {
entry<k,v> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new entry<>(key, value, null);
size = 1;
modcount++;
return null;
}
int cmp;
// split comparator and comparable paths
comparator<? super k> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setvalue(value);
} while (t != null);
else {
if (key == null)
throw new nullpointerexception();
comparable<? super k> k = (comparable<? super k>) key;
cmp = k.compareto(t.key);
entry<k,v> e = new entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixafterinsertion(e);
size++;
modcount++;
return null;
private void fixafterinsertion(entry<k,v> x) {
x.color = red;
..
root.color = black;
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的父節點已變為黑色，循環可以直接退出。
如下圖所示：
代碼：
while (x != null && x != root && x.parent.color == red) {
if (parentof(x) == leftof(parentof(parentof(x)))) {
entry<k,v> y = rightof(parentof(parentof(x)));
if (colorof(y) == red) {
setcolor(parentof(x), black);
setcolor(y, black);
setcolor(parentof(parentof(x)), red);
x = parentof(parentof(x));
} else {
if (x == rightof(parentof(x))) {
x = parentof(x);
rotateleft(x);
}
rotateright(parentof(parentof(x)));
}
} else {
....
}
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的父節點已為黑色，循環可以直接退出。
entry<k,v> y = leftof(parentof(parentof(x)));
if (x == leftof(parentof(x))) {
rotateright(x);
rotateleft(parentof(parentof(x)));
treemap中紅黑樹節點删除
紅黑樹的删除類似二叉查找樹删除邏輯類似，在對同時有左子樹和右子樹存在時，treemap選擇先将要删除的節點替換成其直接後繼節點，然後删除其直接後繼節點（其直接後繼節點不可能同時存在左子節點和右子位元組點）。對紅黑樹，由于紅色節點不影響路徑計算（性質6），因而對紅色節點可以直接删除。然而在删除黑色節點時，如果删除的節點不是樹的唯一節點，那麼在某些路徑上的黑色節點數會發生改變，破壞性質6；如果被删除的唯一子節點為紅色，而父節點也為紅色，那麼性質5被破壞，因為存在紅色節點的子節點為紅色；如果删除的是根節點，而它的唯一子節點是紅色，則性質3被破壞。因而需要做一些調整。
private void deleteentry(entry<k,v> p) {
size--;
// if strictly internal, copy successor's element to p and then make p
// point to successor.
if (p.left != null && p.right != null) {
entry<k,v> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children
// start fixup at replacement node, if it exists.
entry<k,v> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// link replacement to parent
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
// null out links so they are ok to use by fixafterdeletion.
p.left = p.right = p.parent = null;
// fix replacement
if (p.color == black)
fixafterdeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
root = null;
} else { // no children. use self as phantom replacement and unlink.
fixafterdeletion(p);
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
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的右子節點時，其邏輯和以上對稱，不再贅述。
private void fixafterdeletion(entry<k,v> x) {
while (x != root && colorof(x) == black) {
if (x == leftof(parentof(x))) {
entry<k,v> sib = rightof(parentof(x));
if (colorof(sib) == red) {
setcolor(sib, black);
setcolor(parentof(x), red);
rotateleft(parentof(x));
sib = rightof(parentof(x));
if (colorof(leftof(sib)) == black &&
colorof(rightof(sib)) == black) {
setcolor(sib, red);
x = parentof(x);
if (colorof(rightof(sib)) == black) {
setcolor(leftof(sib), black);
setcolor(sib, red);
rotateright(sib);
sib = rightof(parentof(x));
setcolor(sib, colorof(parentof(x)));
setcolor(rightof(sib), black);
x = root;
} else { // symmetric
entry<k,v> sib = leftof(parentof(x));
rotateright(parentof(x));
sib = leftof(parentof(x));
if (colorof(rightof(sib)) == black &&
colorof(leftof(sib)) == black) {
if (colorof(leftof(sib)) == black) {
setcolor(rightof(sib), black);
rotateleft(sib);
sib = leftof(parentof(x));
setcolor(leftof(sib), black);
setcolor(x, black);
treemap中紅黑樹節點查找
紅黑樹的節點查找同二叉查找樹邏輯，不再贅述。這裡有一點不太明白：getentryusingcomparator()方法注釋中說它從getentry()方法提取出來是為了性能上的考慮，這是為什麼？
/**
* version of getentry using comparator. split off from getentry
* for performance. (this is not worth doing for most methods,
* that are less dependent on comparator performance, but is
* worthwhile here.)
*/
final entry<k,v> getentryusingcomparator(object key)
treemap中其他方法
treemap中其他方法實作比較直覺，隻要了解了紅黑樹，基本上很容易了解，不再贅述。
參考連結：
http://blog.csdn.net/v_july_v/article/details/6105630
http://blog.csdn.net/zhaojinjia/article/details/8120403
http://blog.csdn.net/eric491179912/article/details/6179908
http://dongxicheng.org/structure/red-black-tree/