因為看EHCache中溢出文件的管理代碼，它用到了AA－Tree作為文件中的磁盤管理，因而決定先復(fù)習(xí)以下紅黑樹(RBT, Red Black Tree)，順便看看TreeMap的代碼。關(guān)于紅黑樹，網(wǎng)上已經(jīng)有各種相關(guān)的文章了，因而屬于多一篇不多，少一篇不少的狀態(tài)，因而我純粹當(dāng)作是我自己理解的紀(jì)錄，加深印象，如果能對部分思路和我類似的人有一些幫助，那就最好了。基于這樣的目的，我并不打算深入，如果想看更深入的或者更好的，可以讀讀我最后的參考鏈接。
紅黑樹引入的目的
首先要從對有序序列的查找問題開始，對一個靜態(tài)的有序序列數(shù)組，只需要二分查找即可得到O(log(n))的查找效率；然而實現(xiàn)并不會顯得那么“靜態(tài)”，需要實現(xiàn)動態(tài)的插入、刪除同時保持序列的有序性，并且盡量提高插入、刪除、查找的效率。
為實現(xiàn)動態(tài)插入、刪除，最簡單的實現(xiàn)是二叉排序樹(BST, Binary Sort Tree)，它具有以下性質(zhì)：
1. 它可以是一個空樹。
2. 若它的左子樹不為空，則它的左子樹所有節(jié)點的值均小于根節(jié)點的值。
3. 若它的右子樹不為空，則它的右子樹所有節(jié)點的值均大于根節(jié)點的值。
4. 它的左子樹和右子樹都是一個二叉排序樹。
根據(jù)以上性質(zhì)，
對查找，比較查找數(shù)和當(dāng)前節(jié)點，如果查找數(shù)和當(dāng)前節(jié)點相等，則找到返回；如果查找數(shù)小于當(dāng)前節(jié)點，查找其左子樹，如果查找數(shù)大于當(dāng)前節(jié)點，查找其右子樹，直到找到或直到葉子節(jié)點為null，返回null。
對插入，先查找這棵樹，如果找到已存在的節(jié)點，更新節(jié)點值，否則把新值插入到最后一個為null的節(jié)點中。
對刪除，首先找到要刪除的節(jié)點，a）如果找到的節(jié)點P沒有子節(jié)點，直接刪除即可；b）如果找到的節(jié)點P只有左子樹或右子樹，刪除該節(jié)點，并將其父節(jié)點原來的指針指向它唯一的左子樹、或右子樹即可；c）如果找到的節(jié)點P既有左子樹又有右子樹，可以有兩種做法：I）刪除節(jié)點P，把節(jié)點P的父節(jié)點原來指向P的指針指向節(jié)點P的左字節(jié)點，而將節(jié)點P的右節(jié)點插入到節(jié)點P右節(jié)點的最右葉子節(jié)點上（如果節(jié)點P是其父節(jié)點的右節(jié)點，則將節(jié)點P的父節(jié)點原來指向P節(jié)點的指針指向P節(jié)點的右子樹，而將節(jié)點P的左子樹插入到節(jié)點P最左葉子節(jié)點上），II）將節(jié)點P替換成節(jié)點P的直接前驅(qū)（或直接后繼），然后刪除節(jié)點P的直接前驅(qū)（或直接后繼）（注：直接前驅(qū)查找：節(jié)點P左子樹的最右節(jié)點，直接后繼查找：節(jié)點P右子樹的最左節(jié)點）。
二叉排序樹實現(xiàn)比較簡單，但是它查找效率卻不理想，最好的效率是O(log(n))，最會效率為O(n)。
為了提高查找效率，后來有人提出了平衡二叉樹（AVL樹），它具有二叉排序樹的所有特點，并添加了以下性質(zhì)：
1. 左子樹和右子樹的深度之差絕對值不超過1。
2. 左子樹和右子樹都是平衡二叉樹。
為了實現(xiàn)平衡二叉樹，需要在沒個節(jié)點上添加平衡因子字段，在插入后，如果發(fā)現(xiàn)平衡因子不符合性質(zhì)1，則需要經(jīng)過旋轉(zhuǎn)以調(diào)整。平衡二叉樹可以保證其查找的最好、最壞查找時間復(fù)雜度都為O(log(n))。
紅黑樹是平衡二叉樹的變種，它是一種自平衡的二叉排序樹，也需要通過一些旋轉(zhuǎn)調(diào)整以保持它的性質(zhì)，它的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年寫的一篇論文中獲得的。不同于平衡二叉樹的高度平衡，紅黑樹只能保證從根到葉子節(jié)點的最長路徑不超過最短路徑的2倍，因而它的最壞查找時間復(fù)雜度為O(2log(n + 1))，然而有研究表明它的統(tǒng)計性能要好于平衡二叉樹，因而它具有更廣泛的應(yīng)用。
紅黑樹的性質(zhì)
一棵樹需要滿足以下性質(zhì)才能保證它是一顆紅黑樹：
1. 它是一顆二叉查找樹（BST）。
2. 它的所有節(jié)點是紅色或黑色。
3. 它的根節(jié)點是黑色。
4. 它的葉子節(jié)點是黑色（空節(jié)點視為葉子節(jié)點）。
5. 它的紅節(jié)點的子節(jié)點必須是黑色的；而黑節(jié)點的字節(jié)點可以是黑色或紅色。
6. 它任一節(jié)點到其后代的葉子節(jié)點路徑上有相同的黑色節(jié)點數(shù)。
一般的文章都是把性質(zhì)列出來，然后根據(jù)這些性質(zhì)來寫代碼實現(xiàn)（我也一樣:)），但是如何得出這些性質(zhì)呢？多問幾個為什么總是好事，這個問題需要去讀上面提到的論文，我沒讀過也不打算讀，這貌似不是我能涉及的，那就提出問題不回答了。。。
TreeMap中紅黑樹的節(jié)點對一顆樹的節(jié)點，最基礎(chǔ)是該節(jié)點的值、左節(jié)點指針、右節(jié)點指針。對TreeMap，因為它存儲的是鍵值對，因而它包含了key、value，為了紀(jì)錄節(jié)點的顏色，它還需要有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中紅黑樹節(jié)點插入紅黑數(shù)的插入分以下步驟：
1. 如果當(dāng)前為空樹，插入節(jié)點直接作為根節(jié)點，并將該節(jié)點顏色比較
2. 以二叉排序樹的查找算法查找當(dāng)前樹，如果在當(dāng)前樹中找到已存在的節(jié)點，更新節(jié)點的值，并返回。
3. 否則，創(chuàng)建一個新節(jié)點，將其插入到最后一個查找到的葉子節(jié)點上，其初始顏色為紅色。
4. 如果新插入節(jié)點的父節(jié)點是黑節(jié)點，則沒有破壞當(dāng)前紅黑樹的性質(zhì)，直接返回。
5. 如果新插入節(jié)點的父節(jié)點是紅節(jié)點，則需要做一些調(diào)整。
在TreeMap中，key值的比較可以通過構(gòu)造TreeMap傳入的Comparator實例，如果沒有Comparator，則key必須實現(xiàn)Comparable接口作為比較邏輯，key不可以為null。以二叉排序樹的算法插入新節(jié)點的代碼比較簡單：
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;
Entry<K,V> parent;
// 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;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else return t.setValue(value);
}
while (t !=
null);
}
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中紅黑樹新節(jié)點插入后調(diào)整紅黑樹的調(diào)整比較復(fù)雜，首先它會從當(dāng)前節(jié)點向上查找，直到當(dāng)前節(jié)點為null，或是root節(jié)點，或者當(dāng)前節(jié)點的父節(jié)點顏色不是紅色，然后根據(jù)以下不同情況做處理（設(shè)當(dāng)前節(jié)點為C（紅色），其父節(jié)點為P（紅色），其祖先節(jié)點為A（黑色），其叔叔節(jié)點為U（待定））：
1. P是A的左子樹，U節(jié)點顏色為紅色，此時不管C是節(jié)點是P的左子樹還是右子樹，只需要將P和U設(shè)為黑色，A設(shè)為紅色，則可保證當(dāng)前局部樹符合紅黑樹定義，把A作為新插入節(jié)點重新調(diào)整，如果當(dāng)前樹已經(jīng)是整棵樹，則因為根節(jié)點為紅色，不符合紅黑樹定義，此時只需要將根節(jié)點顏色設(shè)置為黑色即可，即fixAfterInsertion()最后一句代碼的作用。
2. P是A的左子樹，U節(jié)點顏色為黑色，C是P的左子樹，將P設(shè)置為黑色，A設(shè)置為紅色，并對A做右旋操作。此時C的父節(jié)點已變?yōu)楹谏h(huán)可以直接退出。
3. P是A的左子樹，U節(jié)點顏色為黑色，C是P的右子樹，此時只需要先對P左旋，然后設(shè)置C為黑色，A為紅色，并對A右旋，此時P的父節(jié)點已變?yōu)楹谏h(huán)可以直接退出。
如下圖所示：
代碼：
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);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
....
}
}
4. P是A的右子樹，U節(jié)點顏色為紅色，此時不管C是節(jié)點是P的左子樹還是右子樹，只需要將P和U設(shè)為黑色，A設(shè)為紅色，則可保證當(dāng)前局部樹符合紅黑樹定義，把A作為新插入節(jié)點重新調(diào)整，如果當(dāng)前樹已經(jīng)是整棵樹，則因為根節(jié)點為紅色，不符合紅黑樹定義，此時只需要將根節(jié)點顏色設(shè)置為黑色即可，即fixAfterInsertion()最后一句代碼的作用。
5. P是A的右子樹，U節(jié)點顏色為黑色，C是P的右子樹，將P設(shè)置為黑色，A設(shè)置為紅色，并對A做左旋操作。此時C的父節(jié)點以變?yōu)楹谏h(huán)可以直接退出。
6. P是A的右子樹，U節(jié)點顏色為黑色，C是P的左子樹，此時只需要先對P左旋，然后設(shè)置C為黑色，A為紅色，并對A右旋，此時P的父節(jié)點已為黑色，循環(huán)可以直接退出。
如下圖所示：
代碼：
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
....
} else {
Entry<K,V> y = leftOf(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 == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
TreeMap中紅黑樹節(jié)點刪除紅黑樹的刪除類似二叉查找樹刪除邏輯類似，在對同時有左子樹和右子樹存在時，TreeMap選擇先將要刪除的節(jié)點替換成其直接后繼節(jié)點，然后刪除其直接后繼節(jié)點（其直接后繼節(jié)點不可能同時存在左子節(jié)點和右子字節(jié)點）。對紅黑樹，由于紅色節(jié)點不影響路徑計算（性質(zhì)6），因而對紅色節(jié)點可以直接刪除。然而在刪除黑色節(jié)點時，如果刪除的節(jié)點不是樹的唯一節(jié)點，那么在某些路徑上的黑色節(jié)點數(shù)會發(fā)生改變，破壞性質(zhì)6；如果被刪除的唯一子節(jié)點為紅色，而父節(jié)點也為紅色，那么性質(zhì)5被破壞，因為存在紅色節(jié)點的子節(jié)點為紅色；如果刪除的是根節(jié)點，而它的唯一子節(jié)點是紅色，則性質(zhì)3被破壞。因而需要做一些調(diào)整。
private void deleteEntry(Entry<K,V> p) {
modCount++;
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.
if (p.color == BLACK)
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中紅黑樹刪除黑色節(jié)點后調(diào)整調(diào)整的邏輯分以下步驟來考慮（假設(shè)新替換的節(jié)點為C，即代碼中的x參數(shù)，C的父節(jié)點為P，C是P的左子節(jié)點，C的兄弟節(jié)點為S，S的左子樹為SL，S的右子樹為SR）：
1. 如果C為紅色，直接將C標(biāo)記為黑色即可，因為刪除的黑節(jié)點數(shù)被該節(jié)點補上，該樹已經(jīng)恢復(fù)成一顆紅黑樹。
2. 如果C為黑色，且C為根節(jié)點，直接返回。
3. 如果C為黑色，且S為紅色，那么節(jié)點P、SL、SR都為黑色，此時設(shè)置P為紅色，S為黑色，對P左旋，并重新計算S，即S變?yōu)镾L，即把問題轉(zhuǎn)換為兄弟節(jié)點為黑色的情況。圖片來自http://blog.csdn.net/v_JULY_v/article/details/6105630，自己畫太麻煩了，雖然圖片的命名規(guī)則和我的不一樣，湊合的看把，囧。
前節(jié)點為黑節(jié)點兄弟節(jié)點為紅節(jié)點-變換前.jpg)
前節(jié)點為黑節(jié)點兄弟節(jié)點為紅節(jié)點-變換后.jpg)
4. 如果C為黑色，S為黑色，且SL、SR都為黑色，將S設(shè)置為紅色，P賦值給C，重新計算。
前節(jié)點為黑節(jié)點兄弟節(jié)點為黑節(jié)點-變換前.jpg)
前節(jié)點為黑節(jié)點兄弟節(jié)點為黑節(jié)點-變換后.jpg)
5. 如果C為黑色，S為黑色，且SL為紅色，SR為黑色，那么設(shè)置SL為黑色，S為紅色，對S右旋，重新設(shè)置S為SL。
前節(jié)點為黑節(jié)點兄弟節(jié)點為黑節(jié)點左子節(jié)點為紅色-變換前.jpg)
前節(jié)點為黑節(jié)點兄弟節(jié)點為黑節(jié)點左子節(jié)點為紅色-變換后.jpg)
6. 如果C為黑色，S為黑色，且SR為紅色，SL為任一顏色，則把S節(jié)點的顏色設(shè)置為P節(jié)點的顏色，設(shè)置P節(jié)點的顏色為黑色，SR節(jié)點的顏色為黑色，對P節(jié)點右旋，算法結(jié)束。
前節(jié)點為黑節(jié)點兄弟節(jié)點為黑節(jié)點右子節(jié)點為紅色-變換前.jpg)
前節(jié)點為黑節(jié)點兄弟節(jié)點為黑節(jié)點右子節(jié)點為紅色-變換后.jpg)
當(dāng)C為P的右子節(jié)點時，其邏輯和以上對稱，不再贅述。
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);
} else {
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else { // symmetric
Entry<K,V> sib = leftOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
TreeMap中紅黑樹節(jié)點查找紅黑樹的節(jié)點查找同二叉查找樹邏輯，不再贅述。這里有一點不太明白：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中其他方法實現(xiàn)比較直觀，只要理解了紅黑樹，基本上很容易理解，不再贅述。
參考鏈接：
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/
posted on 2013-10-26 18:41
DLevin 閱讀(2958)
評論(0) 編輯 收藏 所屬分類:
Core Java