這篇文章主要介紹如何通過java.util.TreeMap源碼加強紅黑樹，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！

創(chuàng)新互聯(lián)公司主要從事成都網(wǎng)站設(shè)計、做網(wǎng)站、網(wǎng)頁設(shè)計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)城東,十多年網(wǎng)站建設(shè)經(jīng)驗,價格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):028-86922220

將結(jié)合JDK1.6的TreeMap源碼，來一起探索紅-黑樹的奧秘。紅黑樹是解決二叉搜索樹的非平衡問題。

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

插入一個新節(jié)點

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

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;
}

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

下面的討論中，使用X、P、G表示關(guān)聯(lián)的節(jié)點。X表示一個特殊的節(jié)點， 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個部分，按復(fù)雜程度排列，分別是: 
1) 在下行路途中的顏色變換（Color flips on the way down） 
2) 插入節(jié)點之后的旋轉(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.

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

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

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

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

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

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

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

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

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

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

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

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

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

紅-黑樹的效率

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

紅-黑樹的查找時間和普通的二叉搜索樹的查找時間應(yīng)該幾乎完全一樣。因為在查找過程中并沒用到紅-黑特征。額外的開銷只是每個節(jié)點的存儲空間都稍微增加了一點，來存儲紅黑顏色（一個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;
}

插入和刪除的時間要增加一個常數(shù)因子，因為不得不在下行的路徑上和插入點執(zhí)行顏色變換和旋轉(zhuǎn)。平均起來一次插入大約需要一次旋轉(zhuǎn)。

因為在大多數(shù)應(yīng)用中，查找的次數(shù)比插入和刪除的次數(shù)多，所以應(yīng)用紅-黑樹取代普通的二叉搜索樹總體上不會增加太多的時間開銷。

以上是“如何通過java.util.TreeMap源碼加強紅黑樹”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對大家有幫助，更多相關(guān)知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

網(wǎng)頁題目：如何通過java.util.TreeMap源碼加強紅黑樹-創(chuàng)新互聯(lián)
本文URL：http://www.rwnh.cn/article34/dhhspe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供建站公司、定制網(wǎng)站、品牌網(wǎng)站制作、靜態(tài)網(wǎng)站、微信公眾號、商城網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)