快捷導(dǎo)航

通過(guò)java.util.TreeMap源碼加強(qiáng)紅黑樹(shù)的理解

更新時(shí)間：2017年11月20日 10:34:17 投稿：laozhang

通過(guò)分析java.util.TreeMap源碼來(lái)對(duì)經(jīng)典問(wèn)題紅黑樹(shù)加強(qiáng)理解和理清思路。

在此之前，腳本之家已經(jīng)為大家整理了很多關(guān)于經(jīng)典問(wèn)題紅黑樹(shù)的思路和解決辦法。本篇文章，是通過(guò)分析java.util.TreeMap源碼，讓大家通過(guò)實(shí)例來(lái)對(duì)紅黑樹(shù)這個(gè)問(wèn)題有更加深入的理解。

本篇將結(jié)合JDK1.6的TreeMap源碼，來(lái)一起探索紅-黑樹(shù)的奧秘。紅黑樹(shù)是解決二叉搜索樹(shù)的非平衡問(wèn)題。

當(dāng)插入（或者刪除）一個(gè)新節(jié)點(diǎn)時(shí)，為了使樹(shù)保持平衡，必須遵循一定的規(guī)則，這個(gè)規(guī)則就是紅-黑規(guī)則：
1) 每個(gè)節(jié)點(diǎn)不是紅色的就是黑色的
2) 根總是黑色的
3) 如果節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的（反之倒不一定必須為真）
4) 從跟到葉節(jié)點(diǎn)或者空子節(jié)點(diǎn)的每條路徑，必須包含相同數(shù)目的黑色節(jié)點(diǎn)

插入一個(gè)新節(jié)點(diǎn)

紅-黑樹(shù)的插入過(guò)程和普通的二叉搜索樹(shù)基本一致：從跟朝插入點(diǎn)位置走，在每個(gè)節(jié)點(diǎn)處通過(guò)比較節(jié)點(diǎn)的關(guān)鍵字相對(duì)大小來(lái)決定向左走還是向右走。

public V put(K key, V value) {
Entry<K,V> t = root;
int cmp;
Entry<K,V> parent;
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退出方法 
return t.setValue(value); 
}
} while (t != null);
Entry<K,V> e = new Entry<K,V>(key, value, parent);
if (cmp < 0) {
parent.left = e;
} else {
parent.right = e;
}
fixAfterInsertion(e);
size++;
modCount++;
return null;
}

但是，在紅-黑樹(shù)種，找到插入點(diǎn)更復(fù)雜，因?yàn)橛蓄伾儞Q和旋轉(zhuǎn)。fixAfterInsertion()方法就是處理顏色變換和旋轉(zhuǎn)，需重點(diǎn)掌握它是如何保持樹(shù)的平衡(use rotations and the color rules to maintain the tree's balance)。

下面的討論中，使用X、P、G表示關(guān)聯(lián)的節(jié)點(diǎn)。X表示一個(gè)特殊的節(jié)點(diǎn)， P是X的父，G是P的父。

X is a node that has caused a rule violation. (Sometimes X refers to a newly inserted node, and sometimes to the child node when a parent and child have a redred conflict.)

On the way down the tree to find the insertion point, you perform a color flip whenever you find a black node with two red children (a violation of Rule 2). Sometimes the flip causes a red-red conflict (a violation of Rule 3). Call the red child X and the red parent P. The conflict can be fixed with a single rotation or a double rotation, depending on whether X is an outside or inside grandchild of G. Following color flips and rotations, you continue down to the insertion point and insert the new node.

After you've inserted the new node X, if P is black, you simply attach the new red node. If P is red, there are two possibilities: X can be an outside or inside grandchild of G. If X is an outside grandchild, you perform one rotation, and if it's an inside grandchild, you perform two. This restores the tree to a balanced state.

按照上面的解釋，討論可分為3個(gè)部分，按復(fù)雜程度排列，分別是:
1) 在下行路途中的顏色變換（Color flips on the way down）
2) 插入節(jié)點(diǎn)之后的旋轉(zhuǎn)（Rotations after the node is inserted）
3) 在向下路途上的旋轉(zhuǎn)（Rotations on the way down）

在下行路途中的顏色變換（Color flips on the way down）

Here's the rule: Every time the insertion routine encounters a black node that has two red children, it must change the children to black and the parent to red (unless the parent is the root, which always remains black)

The flip leaves unchanged the number of black nodes on the path from the root on down through P to the leaf or null nodes.

盡管顏色變換不會(huì)違背規(guī)則4，但是可能會(huì)違背規(guī)則3。如果P的父是黑色的，則P由黑色變成紅色時(shí)不會(huì)有任何問(wèn)題，但是，如果P的父是紅色的，那么在P的顏色變化之后，就有兩個(gè)紅色節(jié)點(diǎn)相連接了。這個(gè)問(wèn)題需要在繼續(xù)向下沿著路徑插入新節(jié)點(diǎn)之前解決，可以通過(guò)旋轉(zhuǎn)修正這個(gè)問(wèn)題，下文將會(huì)看到。

插入節(jié)點(diǎn)之后的旋轉(zhuǎn)（Rotations after the node is inserted）

新節(jié)點(diǎn)在插入之前，樹(shù)是符合紅-黑規(guī)則，在插入新節(jié)點(diǎn)之后，樹(shù)就不平衡了，此時(shí)需要通過(guò)旋轉(zhuǎn)來(lái)調(diào)整樹(shù)的平衡，使之重新符合紅-黑規(guī)則。

可能性1：P是黑色的，就什么事情也不用做。插入即可。

可能性2：P是紅色，X是G的一個(gè)外側(cè)子孫節(jié)點(diǎn)，則需要一次旋轉(zhuǎn)和一些顏色的變化。
以插入50,25,75,12,6為例，注意節(jié)點(diǎn)6是一個(gè)外側(cè)子孫節(jié)點(diǎn)，它和它的父節(jié)點(diǎn)都是紅色。

在這個(gè)例子中，X是一個(gè)外側(cè)子孫節(jié)點(diǎn)而且是左子節(jié)點(diǎn)，X是外側(cè)子孫節(jié)點(diǎn)且為右子節(jié)點(diǎn)，是一種與此對(duì)稱的情況。通過(guò)用50,25,75,87,93創(chuàng)建樹(shù)，同理再畫一畫圖，這里就省略了。

可能性3：P是紅色，X是G的一個(gè)內(nèi)側(cè)子孫節(jié)點(diǎn)，則需要兩次旋轉(zhuǎn)和一些顏色的改變。
以插入50,25,75,12,18為例，注意節(jié)點(diǎn)18是一個(gè)內(nèi)側(cè)子孫節(jié)點(diǎn)，它和它的父節(jié)點(diǎn)都是紅色。

在向下路途上的旋轉(zhuǎn)（Rotations on the way down）

在插入新節(jié)點(diǎn)之前，實(shí)際上樹(shù)已經(jīng)違背了紅-黑規(guī)則，所以需要插入新節(jié)點(diǎn)之前做調(diào)整。所以我們本次討論的主題是“在向下路途準(zhǔn)備插入新節(jié)點(diǎn)時(shí)，上面先進(jìn)行調(diào)整，使上面成為標(biāo)準(zhǔn)的紅黑樹(shù)后，再進(jìn)行新節(jié)點(diǎn)插入”。

外側(cè)子孫節(jié)點(diǎn)

以插入50,25,75,12,37,6,18,3為例，例子中違背規(guī)則的節(jié)點(diǎn)是一個(gè)外側(cè)子孫節(jié)點(diǎn)。

內(nèi)側(cè)子孫節(jié)點(diǎn)

以插入50,25,75,12,37,31,43為例，例子中違背規(guī)則的節(jié)點(diǎn)是一個(gè)內(nèi)側(cè)子孫節(jié)點(diǎn)。

紅-黑樹(shù)的效率

和一般的二叉搜索樹(shù)類似，紅-黑樹(shù)的查找、插入和刪除的時(shí)間復(fù)雜度為O(log2N)。

紅-黑樹(shù)的查找時(shí)間和普通的二叉搜索樹(shù)的查找時(shí)間應(yīng)該幾乎完全一樣。因?yàn)樵诓檎疫^(guò)程中并沒(méi)用到紅-黑特征。額外的開(kāi)銷只是每個(gè)節(jié)點(diǎn)的存儲(chǔ)空間都稍微增加了一點(diǎn)，來(lái)存儲(chǔ)紅黑顏色（一個(gè)boolean變量）。

final Entry<K, V> getEntry(Object key) {
Comparable <? super K > k = (Comparable <? super K > ) key;
Entry<K, V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0) {
p = p.left;
} else if (cmp > 0) {
p = p.right;
} else {
return p;
}
}
return null;
}