TreeMap 的實現(xiàn)是紅黑樹算法的實現(xiàn),所以要了解 TreeMap 就必須對紅黑樹有一定的了解,其實這篇博文的名字叫做:根據(jù)紅黑樹的算法來分析 TreeMap 的實現(xiàn),但是為了與 Java 提高篇系列博文保持一致還是叫做 TreeMap 比較好。通過這篇博文你可以獲得如下知識點:
1、紅黑樹的基本概念。
2、紅黑樹增加節(jié)點、刪除節(jié)點的實現(xiàn)過程。
3、紅黑樹左旋轉(zhuǎn)、右旋轉(zhuǎn)的復(fù)雜過程。
4、Java 中 TreeMap 是如何通過 put、deleteEntry 兩個來實現(xiàn)紅黑樹增加、刪除節(jié)點的。
我想通過這篇博文你對 TreeMap 一定有了更深的認識。好了,下面先簡單普及紅黑樹知識。
紅黑樹又稱紅-黑二叉樹,它首先是一顆二叉樹,它具體二叉樹所有的特性。同時紅黑樹更是一顆自平衡的排序二叉樹。
我們知道一顆基本的二叉樹他們都需要滿足一個基本性質(zhì)–即樹中的任何節(jié)點的值大于它的左子節(jié)點,且小于它的右子節(jié)點。按照這個基本性質(zhì)使得樹的檢索效率大大提高。我們知道在生成二叉樹的過程是非常容易失衡的,最壞的情況就是一邊倒(只有右/左子樹),這樣勢必會導(dǎo)致二叉樹的檢索效率大大降低(O(n)),所以為了維持二叉樹的平衡,大牛們提出了各種實現(xiàn)的算法,如:AVL,SBT,伸展樹,TREAP ,紅黑樹等等。
平衡二叉樹必須具備如下特性:它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過 1,并且左右兩個子樹都是一棵平衡二叉樹。也就是說該二叉樹的任何一個等等子節(jié)點,其左右子樹的高度都相近。
http://wiki.jikexueyuan.com/project/java-enhancement/images/27-1.png" alt="fig.1" />
紅黑樹顧名思義就是節(jié)點是紅色或者黑色的平衡二叉樹,它通過顏色的約束來維持著二叉樹的平衡。對于一棵有效的紅黑樹二叉樹而言我們必須增加如下規(guī)則:
1、每個節(jié)點都只能是紅色或者黑色
2、根節(jié)點是黑色
3、每個葉節(jié)點(NIL 節(jié)點,空節(jié)點)是黑色的。
4、如果一個結(jié)點是紅的,則它兩個子節(jié)點都是黑的。也就是說在一條路徑上不能出現(xiàn)相鄰的兩個紅色結(jié)點。
5、從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點。
這些約束強制了紅黑樹的關(guān)鍵性質(zhì): 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結(jié)果是這棵樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例,這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的,而不同于普通的二叉查找樹。所以紅黑樹它是復(fù)雜而高效的,其檢索效率 O(log n)。下圖為一顆典型的紅黑二叉樹。
http://wiki.jikexueyuan.com/project/java-enhancement/images/27-2.png" alt="fig.2" />
對于紅黑二叉樹而言它主要包括三大基本操作:左旋、右旋、著色。
http://wiki.jikexueyuan.com/project/java-enhancement/images/27-3.gif" alt="fig.3" />
左旋
http://wiki.jikexueyuan.com/project/java-enhancement/images/27-4.gif" alt="fig.4" />
右旋
(圖片來自:http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html)
本節(jié)參考文獻:http://baike.baidu.com/view/133754.htm?fr=aladdin—–百度百科
注:由于本文主要是講解 Java 中 TreeMap,所以并沒有對紅黑樹進行非常深入的了解和研究,如果諸位想對其進行更加深入的研究Lz提供幾篇較好的博文:
1、紅黑樹系列集錦
2、紅黑樹數(shù)據(jù)結(jié)構(gòu)剖析
3、紅黑樹
>>>>>>回歸主角:TreeMap<<<<<<
TreeMap 的定義如下:
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
TreeMap 繼承 AbstractMap,實現(xiàn) NavigableMap、Cloneable、Serializable 三個接口。其中 AbstractMap 表明 TreeMap 為一個 Map 即支持 key-value 的集合,NavigableMap(更多)則意味著它支持一系列的導(dǎo)航方法,具備針對給定搜索目標返回最接近匹配項的導(dǎo)航方法 。
TreeMap 中同時也包含了如下幾個重要的屬性:
//比較器,因為TreeMap是有序的,通過comparator接口我們可以對TreeMap的內(nèi)部排序進行精密的控制
private final Comparator<? super K> comparator;
//TreeMap紅-黑節(jié)點,為TreeMap的內(nèi)部類
private transient Entry<K,V> root = null;
//容器大小
private transient int size = 0;
//TreeMap修改次數(shù)
private transient int modCount = 0;
//紅黑樹的節(jié)點顏色--紅色
private static final boolean RED = false;
//紅黑樹的節(jié)點顏色--黑色
private static final boolean BLACK = true;
對于葉子節(jié)點 Entry 是 TreeMap 的內(nèi)部類,它有幾個重要的屬性:
//鍵
K key;
//值
V value;
//左孩子
Entry<K,V> left = null;
//右孩子
Entry<K,V> right = null;
//父親
Entry<K,V> parent;
//顏色
boolean color = BLACK;
注:前面只是開胃菜,下面是本篇博文的重中之重,在下面兩節(jié)我將重點講解 treeMap 的 put()、delete() 方法。通過這兩個方法我們會了解紅黑樹增加、刪除節(jié)點的核心算法。
在了解 TreeMap 的 put() 方法之前,我們先了解紅黑樹增加節(jié)點的算法。
紅黑樹在新增節(jié)點過程中比較復(fù)雜,復(fù)雜歸復(fù)雜它同樣必須要依據(jù)上面提到的五點規(guī)范,同時由于規(guī)則 1、2、3 基本都會滿足,下面我們主要討論規(guī)則 4、5。假設(shè)我們這里有一棵最簡單的樹,我們規(guī)定新增的節(jié)點為 N、它的父節(jié)點為 P、P 的兄弟節(jié)點為 U、P 的父節(jié)點為 G。
http://wiki.jikexueyuan.com/project/java-enhancement/images/27-5.png" alt="fig.5" />
對于新節(jié)點的插入有如下三個關(guān)鍵地方:
1、插入新節(jié)點總是紅色節(jié)點 。 2、如果插入節(jié)點的父節(jié)點是黑色, 能維持性質(zhì) 。 3、如果插入節(jié)點的父節(jié)點是紅色, 破壞了性質(zhì). 故插入算法就是通過重新著色或旋轉(zhuǎn), 來維持性質(zhì) 。
為了保證下面的闡述更加清晰和根據(jù)便于參考,我這里將紅黑樹的五點規(guī)定再貼一遍:
1、每個節(jié)點都只能是紅色或者黑色
2、根節(jié)點是黑色
3、每個葉節(jié)點(NIL 節(jié)點,空節(jié)點)是黑色的。
4、如果一個結(jié)點是紅的,則它兩個子節(jié)點都是黑的。也就是說在一條路徑上不能出現(xiàn)相鄰的兩個紅色結(jié)點。
5、從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點。
若新插入的節(jié)點N沒有父節(jié)點,則直接當(dāng)做根據(jù)節(jié)點插入即可,同時將顏色設(shè)置為黑色。(如圖一(1))
這種情況新節(jié)點 N 同樣是直接插入,同時顏色為紅色,由于根據(jù)規(guī)則四它會存在兩個黑色的葉子節(jié)點,值為 null。同時由于新增節(jié)點 N 為紅色,所以通過它的子節(jié)點的路徑依然會保存著相同的黑色節(jié)點數(shù),同樣滿足規(guī)則 5。(如圖一(2))
http://wiki.jikexueyuan.com/project/java-enhancement/images/27-6.png" alt="fig.6" />
(圖一)
對于這種情況若直接插入肯定會出現(xiàn)不平衡現(xiàn)象。怎么處理?P、U 節(jié)點變黑、G 節(jié)點變紅。這時由于經(jīng)過節(jié)點 P、U 的路徑都必須經(jīng)過 G 所以在這些路徑上面的黑節(jié)點數(shù)目還是相同的。但是經(jīng)過上面的處理,可能 G 節(jié)點的父節(jié)點也是紅色,這個時候我們需要將 G 節(jié)點當(dāng)做新增節(jié)點遞歸處理。
http://wiki.jikexueyuan.com/project/java-enhancement/images/27-7.png" alt="fig.7" />
對于這種情況我們對新增節(jié)點 N、P 進行一次左旋轉(zhuǎn)。這里所產(chǎn)生的結(jié)果其實并沒有完成,還不是平衡的(違反了規(guī)則四),這是我們需要進行情況5的操作。
http://wiki.jikexueyuan.com/project/java-enhancement/images/27-8.png" alt="fig.8" />
這種情況有可能是由于情況四而產(chǎn)生的,也有可能不是。對于這種情況先已 P 節(jié)點為中心進行右旋轉(zhuǎn),在旋轉(zhuǎn)后產(chǎn)生的樹中,節(jié)點 P 是節(jié)點 N、G 的父節(jié)點。但是這棵樹并不規(guī)范,它違反了規(guī)則 4,所以我們將 P、G 節(jié)點的顏色進行交換,使之其滿足規(guī)范。開始時所有的路徑都需要經(jīng)過 G 其他們的黑色節(jié)點數(shù)一樣,但是現(xiàn)在所有的路徑改為經(jīng)過 P,且 P 為整棵樹的唯一黑色節(jié)點,所以調(diào)整后的樹同樣滿足規(guī)范 5。
http://wiki.jikexueyuan.com/project/java-enhancement/images/27-9.png" alt="fig.9" />
上面展示了紅黑樹新增節(jié)點的五種情況,這五種情況涵蓋了所有的新增可能,不管這棵紅黑樹多么復(fù)雜,都可以根據(jù)這五種情況來進行生成。下面就來分析 Java 中的 TreeMap 是如何來實現(xiàn)紅黑樹的。
在 TreeMap 的 put() 的實現(xiàn)方法中主要分為兩個步驟,第一:構(gòu)建排序二叉樹,第二:平衡二叉樹。
對于排序二叉樹的創(chuàng)建,其添加節(jié)點的過程如下:
1、以根節(jié)點為初始節(jié)點進行檢索。
2、與當(dāng)前節(jié)點進行比對,若新增節(jié)點值較大,則以當(dāng)前節(jié)點的右子節(jié)點作為新的當(dāng)前節(jié)點。否則以當(dāng)前節(jié)點的左子節(jié)點作為新的當(dāng)前節(jié)點。
3、循環(huán)遞歸 2 步驟知道檢索出合適的葉子節(jié)點為止。
4、將新增節(jié)點與 3 步驟中找到的節(jié)點進行比對,如果新增節(jié)點較大,則添加為右子節(jié)點;否則添加為左子節(jié)點。
按照這個步驟我們就可以將一個新增節(jié)點添加到排序二叉樹中合適的位置。如下:
public V put(K key, V value) {
//用t表示二叉樹的當(dāng)前節(jié)點
Entry<K,V> t = root;
//t為null表示一個空樹,即TreeMap中沒有任何元素,直接插入
if (t == null) {
//比較key值,個人覺得這句代碼沒有任何意義,空樹還需要比較、排序?
compare(key, key); // type (and possibly null) check
//將新的key-value鍵值對創(chuàng)建為一個Entry節(jié)點,并將該節(jié)點賦予給root
root = new Entry<>(key, value, null);
//容器的size = 1,表示TreeMap集合中存在一 個元素
size = 1;
//修改次數(shù) + 1
modCount++;
return null;
}
int cmp; //cmp表示key排序的返回結(jié)果
Entry<K,V> parent; //父節(jié)點
// split comparator and comparable paths
Comparator<? super K> cpr = comparator; //指定的排序算法
//如果cpr不為空,則采用既定的排序算法進行創(chuàng)建TreeMap集合
if (cpr != null) {
do {
parent = t; //parent指向上次循環(huán)后的t
//比較新增節(jié)點的key和當(dāng)前節(jié)點key的大小
cmp = cpr.compare(key, t.key);
//cmp返回值小于0,表示新增節(jié)點的key小于當(dāng)前節(jié)點的key,則以當(dāng)前節(jié)點的左子節(jié)點作為新的當(dāng)前節(jié)點
if (cmp < 0)
t = t.left;
//cmp返回值大于0,表示新增節(jié)點的key大于當(dāng)前節(jié)點的key,則以當(dāng)前節(jié)點的右子節(jié)點作為新的當(dāng)前節(jié)點
else if (cmp > 0)
t = t.right;
//cmp返回值等于0,表示兩個key值相等,則新值覆蓋舊值,并返回新值
else
return t.setValue(value);
} while (t != null);
}
//如果cpr為空,則采用默認的排序算法進行創(chuàng)建 TreeMap集合
else {
if (key == null) //key值為空拋出異常
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);
}
//將新增節(jié)點當(dāng)做parent的子節(jié)點
Entry<K,V> e = new Entry<>(key, value, parent);
//如果新增節(jié)點的key小于parent的key,則當(dāng)做左子節(jié)點
if (cmp < 0)
parent.left = e;
//如果新增節(jié)點的key大于parent的key,則當(dāng)做右子節(jié)點
else
parent.right = e;
/*
* 上面已經(jīng)完成了排序二叉樹的的構(gòu)建,將新增節(jié)點 插入該樹中的合適位置
* 下面fixAfterInsertion()方法就是對這棵樹進行調(diào)整、平衡,具體過程參考上面的五種情況
*/
fixAfterInsertion(e);
//TreeMap元素數(shù)量 + 1
size++;
//TreeMap容器修改次數(shù) + 1
modCount++;
return null;
}
上面代碼中 do{} 代碼塊是實現(xiàn)排序二叉樹的核心算法,通過該算法我們可以確認新增節(jié)點在該樹的正確位置。找到正確位置后將插入即可,這樣做了其實還沒有完成,因為我知道 TreeMap 的底層實現(xiàn)是紅黑樹,紅黑樹是一棵平衡排序二叉樹,普通的排序二叉樹可能會出現(xiàn)失衡的情況,所以下一步就是要進行調(diào)整。fixAfterInsertion(e); 調(diào)整的過程務(wù)必會涉及到紅黑樹的左旋、右旋、著色三個基本操作。代碼如下:
/**
* 新增節(jié)點后的修復(fù)操作
* x 表示新增節(jié)點
*/
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED; //新增節(jié)點的顏色為紅色
//循環(huán) 直到 x不是根節(jié)點,且x的父節(jié)點不為紅色
while (x != null && x != root && x.parent.color == RED) {
//如果X的父節(jié)點(P)是其父節(jié)點的父節(jié)點(G)的左節(jié)點
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//獲取X的叔節(jié)點(U)
Entry<K,V> y = rightOf(parentOf (parentOf(x)));
//如果X的叔節(jié)點(U) 為紅色(情況三)
if (colorOf(y) == RED) {
//將X的父節(jié)點(P)設(shè)置為黑色
setColor(parentOf(x), BLACK);
//將X的叔節(jié)點(U)設(shè)置為黑色
setColor(y, BLACK);
//將X的父節(jié)點的父節(jié)點(G)設(shè)置紅色
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
}
//如果X的叔節(jié)點(U為黑色);這里會存在 兩種情況(情況四、情況五)
else {
//如果X節(jié)點為其父節(jié)點(P)的右子 樹,則進行左旋轉(zhuǎn)(情況四)
if (x == rightOf(parentOf(x))) {
//將X的父節(jié)點作為X
x = parentOf(x);
//右旋轉(zhuǎn)
rotateLeft(x);
}
//(情況五)
//將X的父節(jié)點(P)設(shè)置為黑色
setColor(parentOf(x), BLACK);
//將X的父節(jié)點的父節(jié)點(G)設(shè)置紅色
setColor(parentOf(parentOf(x)), RED);
//以X的父節(jié)點的父節(jié)點(G)為中心右旋轉(zhuǎn)
rotateRight(parentOf(parentOf(x)));
}
}
//如果X的父節(jié)點(P)是其父節(jié)點的父節(jié)點(G)的右節(jié)點
else {
//獲取X的叔節(jié)點(U)
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
//如果X的叔節(jié)點(U) 為紅色(情況三)
if (colorOf(y) == RED) {
//將X的父節(jié)點(P)設(shè)置為黑色
setColor(parentOf(x), BLACK);
//將X的叔節(jié)點(U)設(shè)置為黑色
setColor(y, BLACK);
//將X的父節(jié)點的父節(jié)點(G)設(shè)置紅色
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
}
//如果X的叔節(jié)點(U為黑色);這里會存在兩種情況(情況四、情況五)
else {
//如果X節(jié)點為其父節(jié)點(P)的右子樹,則進行左旋轉(zhuǎn)(情況四)
if (x == leftOf(parentOf(x))) {
//將X的父節(jié)點作為X
x = parentOf(x);
//右旋轉(zhuǎn)
rotateRight(x);
}
//(情況五)
//將X的父節(jié)點(P)設(shè)置為黑色
setColor(parentOf(x), BLACK);
//將X的父節(jié)點的父節(jié)點(G)設(shè)置紅色
setColor(parentOf(parentOf(x)), RED);
//以X的父節(jié)點的父節(jié)點(G)為中心右旋轉(zhuǎn)
rotateLeft(parentOf(parentOf(x)));
}
}
}
//將根節(jié)點G強制設(shè)置為黑色
root.color = BLACK;
}
對這段代碼的研究我們發(fā)現(xiàn),其處理過程完全符合紅黑樹新增節(jié)點的處理過程。所以在看這段代碼的過程一定要對紅黑樹的新增節(jié)點過程有了解。在這個代碼中還包含幾個重要的操作。左旋 (rotateLeft())、右旋(rotateRight())、著色(setColor())。
左旋:rotateLeft()
所謂左旋轉(zhuǎn),就是將新增節(jié)點(N)當(dāng)做其父節(jié)點(P),將其父節(jié)點P當(dāng)做新增節(jié)點(N)的左子節(jié)點。即:G.left —> N ,N.left —> P。
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
//獲取P的右子節(jié)點,其實這里就相當(dāng)于新增節(jié)點N(情況四而言)
Entry<K,V> r = p.right;
//將R的左子樹設(shè)置為P的右子樹
p.right = r.left;
//若R的左子樹不為空,則將P設(shè)置為R左子樹的父親
if (r.left != null)
r.left.parent = p;
//將P的父親設(shè)置R的父親
r.parent = p.parent;
//如果P的父親為空,則將R設(shè)置為跟節(jié)點
if (p.parent == null)
root = r;
//如果P為其父節(jié)點(G)的左子樹,則將R設(shè)置為P父 節(jié)點(G)左子樹
else if (p.parent.left == p)
p.parent.left = r;
//否則R設(shè)置為P的父節(jié)點(G)的右子樹
else
p.parent.right = r;
//將P設(shè)置為R的左子樹
r.left = p;
//將R設(shè)置為P的父節(jié)點
p.parent = r;
}
}
右旋:rotateRight()
所謂右旋轉(zhuǎn)即,P.right —> G、G.parent —> P。
private void rotateRight(Entry<K,V> p) {
if (p != null) {
//將L設(shè)置為P的左子樹
Entry<K,V> l = p.left;
//將L的右子樹設(shè)置為P的左子樹
p.left = l.right;
//若L的右子樹不為空,則將P設(shè)置L的右子樹的父節(jié)點
if (l.right != null)
l.right.parent = p;
//將P的父節(jié)點設(shè)置為L的父節(jié)點
l.parent = p.parent;
//如果P的父節(jié)點為空,則將L設(shè)置根節(jié)點
if (p.parent == null)
root = l;
//若P為其父節(jié)點的右子樹,則將L設(shè)置為P的父節(jié)點的右子樹
else if (p.parent.right == p)
p.parent.right = l;
//否則將L設(shè)置為P的父節(jié)點的左子樹
else
p.parent.left = l;
//將P設(shè)置為L的右子樹
l.right = p;
//將L設(shè)置為P的父節(jié)點
p.parent = l;
}
}
左旋、右旋的示意圖如下:
http://wiki.jikexueyuan.com/project/java-enhancement/images/27-3.gif" alt="fig.3" />
(左旋)
http://wiki.jikexueyuan.com/project/java-enhancement/images/27-4.gif" alt="fig.3" />
(右旋)
(圖片來自:http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html)
著色:setColor()
著色就是改變該節(jié)點的顏色,在紅黑樹中,它是依靠節(jié)點的顏色來維持平衡的。
private static <K,V> void setColor(Entry<K,V> p, boolean c) {
if (p != null)
p.color = c;
}
針對于紅黑樹的增加節(jié)點而言,刪除顯得更加復(fù)雜,使原本就復(fù)雜的紅黑樹變得更加復(fù)雜。同時刪除節(jié)點和增加節(jié)點一樣,同樣是找到刪除的節(jié)點,刪除之后調(diào)整紅黑樹。但是這里的刪除節(jié)點并不是直接刪除,而是通過走了“彎路”通過一種捷徑來刪除的:找到被刪除的節(jié)點 D 的子節(jié)點 C,用 C 來替代 D,不是直接刪除 D,因為 D 被 C 替代了,直接刪除 C 即可。所以這里就將刪除父節(jié)點 D 的事情轉(zhuǎn)變?yōu)榱藙h除子節(jié)點 C 的事情,這樣處理就將復(fù)雜的刪除事件簡單化了。子節(jié)點 C 的規(guī)則是:右分支最左邊,或者左分支最右邊的。
http://wiki.jikexueyuan.com/project/java-enhancement/images/27-10.png" alt="fig.10" />
紅-黑二叉樹刪除節(jié)點,最大的麻煩是要保持 各分支黑色節(jié)點數(shù)目相等。 因為是刪除,所以不用擔(dān)心存在顏色沖突問題——插入才會引起顏色沖突。
紅黑樹刪除節(jié)點同樣會分成幾種情況,這里是按照待刪除節(jié)點有幾個兒子的情況來進行分類:
1、沒有兒子,即為葉結(jié)點。直接把父結(jié)點的對應(yīng)兒子指針設(shè)為 NULL,刪除兒子結(jié)點就 OK 了。
2、只有一個兒子。那么把父結(jié)點的相應(yīng)兒子指針指向兒子的獨生子,刪除兒子結(jié)點也 OK 了。
3、有兩個兒子。這種情況比較復(fù)雜,但還是比較簡單。上面提到過用子節(jié)點 C 替代代替待刪除節(jié)點 D,然后刪除子節(jié)點 C 即可。
下面就論各種刪除情況來進行圖例講解,但是在講解之前請允許我再次啰嗦一句,請時刻牢記紅黑樹的 5 點規(guī)定:
1、每個節(jié)點都只能是紅色或者黑色
2、根節(jié)點是黑色
3、每個葉節(jié)點(NIL 節(jié)點,空節(jié)點)是黑色的。
4、如果一個結(jié)點是紅的,則它兩個子節(jié)點都是黑的。也就是說在一條路徑上不能出現(xiàn)相鄰的兩個紅色結(jié)點。
5、從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點。
(注:已經(jīng)講三遍了,再不記住我就懷疑你是否適合搞 IT 了 O(∩_∩)O~)
誠然,既然刪除節(jié)點比較復(fù)雜,那么在這里我們就約定一下規(guī)則:
1、下面要講解的刪除節(jié)點一定是實際要刪除節(jié)點的后繼節(jié)點(N),如前面提到的C。
2、下面提到的刪除節(jié)點的樹都是如下結(jié)構(gòu),該結(jié)構(gòu)所選取的節(jié)點是待刪除節(jié)點的右樹的最左邊子節(jié)點。這里我們規(guī)定真實刪除節(jié)點為 N、父節(jié)點為 P、兄弟節(jié)點為 W 兄弟節(jié)點的兩個子節(jié)點為 X1、X2。如下圖(2.1)。
http://wiki.jikexueyuan.com/project/java-enhancement/images/27-11.png" alt="fig.11" />
現(xiàn)在我們就上面提到的三種情況進行分析、處理。
情況一、無子節(jié)點(紅色節(jié)點)
這種情況對該節(jié)點直接刪除即可,不會影響樹的結(jié)構(gòu)。因為該節(jié)點為葉子節(jié)點它不可能存在子節(jié)點—–如子節(jié)點為黑,則違反黑節(jié)點數(shù)原則(規(guī)定 5),為紅,則違反“顏色”原則(規(guī)定 4)。 如上圖(2.2)。
情況二、有一個子節(jié)點
這種情況處理也是非常簡單的,用子節(jié)點替代待刪除節(jié)點,然后刪除子節(jié)點即可。如上圖(2.3)
情況三、有兩個子節(jié)點
這種情況可能會稍微有點兒復(fù)雜。它需要找到一個替代待刪除節(jié)點(N)來替代它,然后刪除 N 即可。它主要分為四種情況。
1、N 的兄弟節(jié)點 W 為紅色
2、N 的兄弟 w 是黑色的,且w的倆個孩子都是黑色的。
3、N 的兄弟 w 是黑色的,w 的左孩子是紅色,w 的右孩子是黑色。
4、N 的兄弟 w 是黑色的,且 w 的右孩子時紅色的。
情況 3.1、N 的兄弟節(jié)點 W 為紅色
W 為紅色,那么其子節(jié)點 X1、X2 必定全部為黑色,父節(jié)點 P 也為黑色。處理策略是:改變 W、P 的顏色,然后進行一次左旋轉(zhuǎn)。這樣處理就可以使得紅黑性質(zhì)得以繼續(xù)保持。N 的新兄弟 new w 是旋轉(zhuǎn)之前 w 的某個孩子,為黑色。這樣處理后將情況 3.1、轉(zhuǎn)變?yōu)?3.2、3.3、3.4 中的一種。如下:
http://wiki.jikexueyuan.com/project/java-enhancement/images/27-12.png" alt="fig.12" />
情況 3.2、N 的兄弟 w 是黑色的,且 w 的倆個孩子都是黑色的
這種情況其父節(jié)點可紅可黑,由于 W 為黑色,這樣導(dǎo)致 N 子樹相對于其兄弟W子樹少一個黑色節(jié)點,這時我們可以將 W 置為紅色。這樣,N 子樹與 W 子樹黑色節(jié)點一致,保持了平衡。如下
http://wiki.jikexueyuan.com/project/java-enhancement/images/27-13.png" alt="fig.13" />
將 W 由黑轉(zhuǎn)變?yōu)榧t,這樣就會導(dǎo)致新節(jié)點 new N 相對于它的兄弟節(jié)點會少一個黑色節(jié)點。但是如果 new x 為紅色,我們直接將 new x 轉(zhuǎn)變?yōu)楹谏?,保持整棵樹的平衡。否則情況 3.2 會轉(zhuǎn)變?yōu)榍闆r 3.1、3.3、3.4 中的一種。
情況3.3、N的兄弟w是黑色的,w的左孩子是紅色,w的右孩子是黑色
針對這種情況是將節(jié)點 W 和其左子節(jié)點進行顏色交換,然后對 W 進行右旋轉(zhuǎn)處理。
http://wiki.jikexueyuan.com/project/java-enhancement/images/27-14.png" alt="fig.14" />
此時 N 的新兄弟 X1(new w) 是一個有紅色右孩子的黑結(jié)點,于是將情況 3 轉(zhuǎn)化為情況 4.
情況 3.4、N 的兄弟 w 是黑色的,且 w 的右孩子時紅色的
交換 W 和父節(jié)點 P 的顏色,同時對 P 進行左旋轉(zhuǎn)操作。這樣就把左邊缺失的黑色節(jié)點給補回來了。同時將 W 的右子節(jié)點 X2 置黑。這樣左右都達到了平衡。
http://wiki.jikexueyuan.com/project/java-enhancement/images/27-15.png" alt="fig.15" />
總結(jié)
個人認為這四種情況比較難理解,首先他們都不是單一的某種情況,他們之間是可以進行互轉(zhuǎn)的。相對于其他的幾種情況,情況 3.2 比較好理解,僅僅只是一個顏色的轉(zhuǎn)變,通過減少右子樹的一個黑色節(jié)點使之保持平衡,同時將不平衡點上移至 N 與 W 的父節(jié)點,然后進行下一輪迭代。情況 3.1,是將W旋轉(zhuǎn)將其轉(zhuǎn)成情況 2、3、4 情況進行處理。而情況 3.3 通過轉(zhuǎn)變后可以化成情況 3.4 來進行處理,從這里可以看出情況 3.4 應(yīng)該最終結(jié)。情況 3.4、右子節(jié)點為紅色節(jié)點,那么將缺失的黑色節(jié)點交由給右子節(jié)點,通過旋轉(zhuǎn)達到平衡。
通過上面的分析,我們已經(jīng)初步了解了紅黑樹的刪除節(jié)點情況,相對于增加節(jié)點而言它確實是選的較為復(fù)雜。下面我將看到在 Java TreeMap 中是如何實現(xiàn)紅黑樹刪除的。
通過上面的分析我們確認刪除節(jié)點的步驟是:找到一個替代子節(jié)點 C 來替代 P,然后直接刪除 C,最后調(diào)整這棵紅黑樹。下面代碼是尋找替代節(jié)點、刪除替代節(jié)點。
private void deleteEntry(Entry<K,V> p) {
modCount++; //修改次數(shù) +1
size--; //元素個數(shù) -1
/*
* 被刪除節(jié)點的左子樹和右子樹都不為空,那么就用 p節(jié)點的中序后繼節(jié)點代替 p 節(jié)點
* successor(P)方法為尋找P的替代節(jié)點。規(guī)則是右分支 最左邊,或者 左分支最右邊的節(jié)點
* ---------------------(1)
*/
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
}
//replacement為替代節(jié)點,如果P的左子樹存在那么就用左子樹替代,否則用右子樹替代
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
/*
* 刪除節(jié)點,分為上面提到的三種情況
* -----------------------(2)
*/
//如果替代節(jié)點不為空
if (replacement != null) {
replacement.parent = p.parent;
/*
*replacement來替代P節(jié)點
*/
//若P沒有父節(jié)點,則跟節(jié)點直接變成replacement
if (p.parent == null)
root = replacement;
//如果P為左節(jié)點,則用replacement來替代為左節(jié)點
else if (p == p.parent.left)
p.parent.left = replacement;
//如果P為右節(jié)點,則用replacement來替代為右節(jié)點
else
p.parent.right = replacement;
//同時將P節(jié)點從這棵樹中剔除掉
p.left = p.right = p.parent = null;
/*
* 若P為紅色直接刪除,紅黑樹保持平衡
* 但是若P為黑色,則需要調(diào)整紅黑樹使其保持平衡
*/
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { //p沒有父節(jié)點,表示為P根節(jié)點,直接刪除即可
root = null;
} else { //P節(jié)點不存在子節(jié)點,直接刪除即可
if (p.color == BLACK) //如果P節(jié)點的顏色為黑色,對紅黑樹進行調(diào)整
fixAfterDeletion(p);
//刪除P節(jié)點
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;
}
}
}
(1)除是尋找替代節(jié)點 replacement,其實現(xiàn)方法為 successor()。如下:
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
/*
* 尋找右子樹的最左子樹
*/
else if (t.right != null) {
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
}
/*
* 選擇左子樹的最右子樹
*/
else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
(2)處是刪除該節(jié)點過程。它主要分為上面提到的三種情況,它與上面的 if…else if… else一一對應(yīng) 。如下:
1、有兩個兒子。這種情況比較復(fù)雜,但還是比較簡單。上面提到過用子節(jié)點 C 替代代替待刪除節(jié)點 D,然后刪除子節(jié)點 C 即可。
2、沒有兒子,即為葉結(jié)點。直接把父結(jié)點的對應(yīng)兒子指針設(shè)為 NULL,刪除兒子結(jié)點就 OK 了。
3、只有一個兒子。那么把父結(jié)點的相應(yīng)兒子指針指向兒子的獨生子,刪除兒子結(jié)點也 OK 了。
刪除完節(jié)點后,就要根據(jù)情況來對紅黑樹進行復(fù)雜的調(diào)整:fixAfterDeletion()。
private void fixAfterDeletion(Entry<K,V> x) {
// 刪除節(jié)點需要一直迭代,知道 直到 x 不是根節(jié)點,且 x 的顏色是黑色
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) { //若X 節(jié)點為左節(jié)點
//獲取其兄弟節(jié)點
Entry<K,V> sib = rightOf(parentOf(x));
/*
* 如果兄弟節(jié)點為紅色----(情況3.1)
* 策略:改變W、P的顏色,然后進行一次左旋轉(zhuǎn)
*/
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
/*
* 若兄弟節(jié)點的兩個子節(jié)點都為黑色----(情況3.2)
* 策略:將兄弟節(jié)點編程紅色
*/
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
}
else {
/*
* 如果兄弟節(jié)點只有右子樹為黑色---- (情況3.3)
* 策略:將兄弟節(jié)點與其左子樹進行顏色互換然后進行右轉(zhuǎn)
* 這時情況會轉(zhuǎn)變?yōu)?.4
*/
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
/*
*----情況3.4
*策略:交換兄弟節(jié)點和父節(jié)點的顏色,
*同時將兄弟節(jié)點右子樹設(shè)置為黑色,最后左旋轉(zhuǎn)
*/
setColor(sib, colorOf(parentOf (x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
}
/**
* X節(jié)點為右節(jié)點與其為做節(jié)點處理過程差不多,這里 就不在累述了
*/
else {
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);
}
這是紅黑樹在刪除節(jié)點后,對樹的平衡性進行調(diào)整的過程,其實現(xiàn)過程與上面四種復(fù)雜的情況一一對應(yīng),所以在這個源碼的時候一定要對著上面提到的四種情況看。
這篇博文確實是有點兒長,在這里非常感謝各位看客能夠靜下心來讀完,我想你通過讀完這篇博文一定收獲不小。同時這篇博文很大篇幅都在闡述紅黑樹的實現(xiàn)過程,對 Java 的 TreeMap 聊的比較少,但是我認為如果理解了紅黑樹的實現(xiàn)過程,對 TreeMap 那是手到擒來,小菜一碟。
同時這篇博文我寫了四天,看了、參考了大量的博文。同時不免會有些地方存在借鑒之處,在這里對其表示感謝。LZ 大二開始學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu),自認為學(xué)的不錯,現(xiàn)在發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)我還有太多的地方需要學(xué)習(xí)了,同時也再一次體味了算法的魅力?。。?!
參考資料:
1、紅黑樹數(shù)據(jù)結(jié)構(gòu)剖析:http://www.cnblogs.com/fanzhidongyzby/p/3187912.html
2、紅黑二叉樹詳解及理論分析:http://blog.csdn.net/kartorz/article/details/8865997
3、教你透徹了解紅黑樹:http://blog.csdn.net/v_july_v/article/details/6105630
4、經(jīng)典算法研究系列:五、紅黑樹算法的實現(xiàn)與剖析:http://blog.csdn.net/v_JULY_v/article/details/6109153
5、示例,紅黑樹插入和刪除過程:http://saturnman.blog.163.com/blog/static/557611201097221570/
6、紅黑二叉樹詳解及理論分析:http://blog.csdn.net/kartorz/article/details/8865997