Java集合—TreeMap底层原理
原文出自：http://cmsblogs.com/?p=1013。尊重作者的成果，轉(zhuǎn)載請注明出處！???
個人站點：http://cmsblogs.com
?
TreeMap的實現(xiàn)是紅黑樹算法的實現(xiàn)，所以要了解TreeMap就必須對紅黑樹有一定的了解,其實這篇博文的名字叫做：根據(jù)紅黑樹的算法來分析TreeMap的實現(xiàn)，但是為了與Java提高篇系列博文保持一致還是叫做TreeMap比較好。通過這篇博文你可以獲得如下知識點：
我想通過這篇博文你對TreeMap一定有了更深的認識。好了，下面先簡單普及紅黑樹知識。
一、紅黑樹簡介
紅黑樹又稱紅-黑二叉樹，它首先是一顆二叉樹，它具體二叉樹所有的特性。同時紅黑樹更是一顆自平衡的排序二叉樹。我們知道一顆基本的二叉樹他們都需要滿足一個基本性質(zhì)--即樹中的任何節(jié)點的值大于它的左子節(jié)點，且小于它的右子節(jié)點。按照這個基本性質(zhì)使得樹的檢索效率大大提高。我們知道在生成二叉樹的過程是非常容易失衡的，最壞的情況就是一邊倒（只有右/左子樹），這樣勢必會導(dǎo)致二叉樹的檢索效率大大降低（O(n)），所以為了維持二叉樹的平衡，大牛們提出了各種實現(xiàn)的算法，如：AVL，SBT，伸展樹，TREAP?，紅黑樹等等。平衡二叉樹必須具備如下特性：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。也就是說該二叉樹的任何一個子節(jié)點，其左右子樹的高度都相近。
???????紅黑樹顧名思義就是節(jié)點是紅色或者黑色的平衡二叉樹，它通過顏色的約束來維持著二叉樹的平衡。對于一棵有效的紅黑樹二叉樹而言我們必須增加如下規(guī)則：
???????這些約束強制了紅黑樹的關(guān)鍵性質(zhì): 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結(jié)果是這棵樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。所以紅黑樹它是復(fù)雜而高效的，其檢索效率O(log?n)。下圖為一顆典型的紅黑二叉樹。
對于紅黑二叉樹而言它主要包括三大基本操作：左旋、右旋、著色。
?
???????本節(jié)參考文獻：百度百科，由于本文主要是講解Java中TreeMap，所以并沒有對紅黑樹進行非常深入的了解和研究，如果諸位想對其進行更加深入的研究，Lz提供幾篇較好的博文：
- 紅黑樹系列集錦
- 紅黑樹數(shù)據(jù)結(jié)構(gòu)剖析
- 紅黑樹?
二、TreeMap數(shù)據(jù)結(jié)構(gòu)
>>>>>>回歸主角：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()方法
在了解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。
對于新節(jié)點的插入有如下三個關(guān)鍵地方：
為了保證下面的闡述更加清晰和根據(jù)便于參考，我這里將紅黑樹的五點規(guī)定再貼一遍：
a. 新增節(jié)點N為根節(jié)點：若新插入的節(jié)點N沒有父節(jié)點，則直接當做根據(jù)節(jié)點插入即可，同時將顏色設(shè)置為黑色，如圖一(1)
b. 父節(jié)點為黑色：這種情況新節(jié)點N同樣是直接插入，同時顏色為紅色，由于根據(jù)規(guī)則四它會存在兩個黑色的葉子節(jié)點，值為null。同時由于新增節(jié)點N為紅色，所以通過它的子節(jié)點的路徑依然會保存著相同的黑色節(jié)點數(shù)，同樣滿足規(guī)則5，如圖一(2)
圖一?
c.?若父節(jié)點P和P的兄弟節(jié)點U都為紅色：對于這種情況若直接插入肯定會出現(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é)點當做新增節(jié)點遞歸處理。
d.?若父節(jié)點P為紅色，叔父節(jié)點U為黑色或者缺少，且新增節(jié)點N為P節(jié)點的右孩子：對于這種情況我們對新增節(jié)點N、P進行一次左旋轉(zhuǎn)。這里所產(chǎn)生的結(jié)果其實并沒有完成，還不是平衡的（違反了規(guī)則四），這是我們需要進行情況5的操作。
e.?父節(jié)點P為紅色，叔父節(jié)點U為黑色或者缺少，新增節(jié)點N為父節(jié)點P左孩子：這種情況有可能是由于情況四而產(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。
上面展示了紅黑樹新增節(jié)點的五種情況，這五種情況涵蓋了所有的新增可能，不管這棵紅黑樹多么復(fù)雜，都可以根據(jù)這五種情況來進行生成。下面就來分析Java中的TreeMap是如何來實現(xiàn)紅黑樹的。treemap的put方法java實現(xiàn)。在TreeMap的put()的實現(xiàn)方法中主要分為兩個步驟，第一：構(gòu)建排序二叉樹，第二：平衡二叉樹。對于排序二叉樹的創(chuàng)建，其添加節(jié)點的過程如下：
按照這個步驟我們就可以將一個新增節(jié)點添加到排序二叉樹中合適的位置。如下：
public V put(K key, V value) {//用t表示二叉樹的當前節(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é)點賦予給rootroot = new Entry<>(key, value, null);//容器的size = 1，表示TreeMap集合中存在一個元素size = 1;//修改次數(shù) + 1modCount++;return null;}int cmp; //cmp表示key排序的返回結(jié)果Entry<K,V> parent; //父節(jié)點// split comparator and comparable pathsComparator<??super K> cpr = comparator;?//指定的排序算法//如果cpr不為空，則采用既定的排序算法進行創(chuàng)建TreeMap集合if?(cpr !=?null) {do?{parent?= t;?//parent指向上次循環(huán)后的t//比較新增節(jié)點的key和當前節(jié)點key的大小cmp = cpr.compare(key, t.key);//cmp返回值小于0，表示新增節(jié)點的key小于當前節(jié)點的key，則以當前節(jié)點的左子節(jié)點作為新的當前節(jié)點if?(cmp <?0)t = t.left;//cmp返回值大于0，表示新增節(jié)點的key大于當前節(jié)點的key，則以當前節(jié)點的右子節(jié)點作為新的當前節(jié)點else?if?(cmp >?0)t = t.right;//cmp返回值等于0，表示兩個key值相等，則新值覆蓋舊值，并返回新值elsereturn?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;elsereturn?t.setValue(value);}while?(t !=?null);}//將新增節(jié)點當做parent的子節(jié)點Entry<K,V> e =?new?Entry<>(key, value,?parent);//如果新增節(jié)點的key小于parent的key，則當做左子節(jié)點if?(cmp <?0)parent.left = e;//如果新增節(jié)點的key大于parent的key，則當做右子節(jié)點elseparent.right = e;/** 上面已經(jīng)完成了排序二叉樹的的構(gòu)建，將新增節(jié)點插入該樹中的合適位置* 下面fixAfterInsertion()方法就是對這棵樹進行調(diào)整、平衡，具體過程參考上面的五種情況*/fixAfterInsertion(e);//TreeMap元素數(shù)量 + 1size++;//TreeMap容器修改次數(shù) + 1modCount++;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é)點作為Xx = 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é)點作為Xx = 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）當做其父節(jié)點（P），將其父節(jié)點P當做新增節(jié)點（N）的左子節(jié)點。即：G.left ---> N ,N.left ---> P。
private?void?rotateLeft(Entry<K,V> p) {if?(p !=?null) {//獲取P的右子節(jié)點，其實這里就相當于新增節(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）的右子樹elsep.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é)點的左子樹elsep.parent.left = l;//將P設(shè)置為L的右子樹l.right = p; //將L設(shè)置為P的父節(jié)點p.parent = l;} }?著色setColor()：著色就是改變該節(jié)點的顏色，在紅黑樹中，它是依靠節(jié)點的顏色來維持平衡的。
private?static?<K,V>?void?setColor(Entry<K,V> p,?boolean?c) {if?(p !=?null)p.color = c; }四、TreeMap delete()方法
???????針對于紅黑樹的增加節(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ī)則是：右分支最左邊，或者左分支最右邊的。
紅-黑二叉樹刪除節(jié)點，最大的麻煩是要保持各分支黑色節(jié)點數(shù)目相等。 因為是刪除，所以不用擔心存在顏色沖突問題——插入才會引起顏色沖突。紅黑樹刪除節(jié)點同樣會分成幾種情況，這里是按照待刪除節(jié)點有幾個兒子的情況來進行分類：
下面就論各種刪除情況來進行圖例講解，但是在講解之前請允許我再次啰嗦一句，請時刻牢記紅黑樹的5點規(guī)定：
???????（注：已經(jīng)講三遍了，再不記住我就懷疑你是否適合搞IT了 O(∩_∩)O~）
誠然，既然刪除節(jié)點比較復(fù)雜，那么在這里我們就約定一下規(guī)則：
- 下面要講解的刪除節(jié)點一定是實際要刪除節(jié)點的后繼節(jié)點（N），如前面提到的C。
- 下面提到的刪除節(jié)點的樹都是如下結(jié)構(gòu)，該結(jié)構(gòu)所選取的節(jié)點是待刪除節(jié)點的右樹的最左邊子節(jié)點。這里我們規(guī)定真實刪除節(jié)點為N、父節(jié)點為P、兄弟節(jié)點為W兄弟節(jié)點的兩個子節(jié)點為X1、X2。如下圖（2.1）。
現(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即可。它主要分為四種情況。
- N的兄弟節(jié)點W為紅色
- N的兄弟w是黑色的，且w的倆個孩子都是黑色的。
- N的兄弟w是黑色的，w的左孩子是紅色，w的右孩子是黑色。
- N的兄弟w是黑色的，且w的右孩子時紅色的。
1）情況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)?.2、3.3、3.4中的一種。如下：
2）情況3.2、N的兄弟w是黑色的，且w的倆個孩子都是黑色的
這種情況其父節(jié)點可紅可黑，由于W為黑色，這樣導(dǎo)致N子樹相對于其兄弟W子樹少一個黑色節(jié)點，這時我們可以將W置為紅色。這樣，N子樹與W子樹黑色節(jié)點一致，保持了平衡。如下
將W由黑轉(zhuǎn)變?yōu)榧t，這樣就會導(dǎo)致新節(jié)點new N相對于它的兄弟節(jié)點會少一個黑色節(jié)點。但是如果new x為紅色，我們直接將new x轉(zhuǎn)變?yōu)楹谏?#xff0c;保持整棵樹的平衡。否則情況3.2 會轉(zhuǎn)變?yōu)榍闆r3.1、3.3、3.4中的一種。
3）情況3.3、N的兄弟w是黑色的，w的左孩子是紅色，w的右孩子是黑色
針對這種情況是將節(jié)點W和其左子節(jié)點進行顏色交換，然后對W進行右旋轉(zhuǎn)處理。
此時N的新兄弟X1(new w)是一個有紅色右孩子的黑結(jié)點，于是將情況3轉(zhuǎn)化為情況4.
4）情況3.4、N的兄弟w是黑色的，且w的右孩子時紅色的。
交換W和父節(jié)點P的顏色，同時對P進行左旋轉(zhuǎn)操作。這樣就把左邊缺失的黑色節(jié)點給補回來了。同時將W的右子節(jié)點X2置黑。這樣左右都達到了平衡。
總結(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ù) +1size--;?//元素個數(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é)點直接變成replacementif?(p.parent ==?null)root = replacement;//如果P為左節(jié)點，則用replacement來替代為左節(jié)點else?if?(p == p.parent.left)p.parent.left = replacement;//如果P為右節(jié)點，則用replacement來替代為右節(jié)點elsep.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()。如下：
（2）處是刪除該節(jié)點過程。它主要分為上面提到的三種情況，它與上面的if…else if… else一一對應(yīng) 。如下：
???????刪除完節(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é)習數(shù)據(jù)結(jié)構(gòu)，自認為學(xué)的不錯，現(xiàn)在發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)我還有太多的地方需要學(xué)習了，同時也再一次體味了算法的魅力！！！！
參考資料：
原文出自：http://cmsblogs.com/?p=1013。尊重作者的成果，轉(zhuǎn)載請注明出處！???
個人站點：http://cmsblogs.com
總結(jié)
以上是生活随笔為你收集整理的Java集合—TreeMap底层原理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Java集合—HashMap底层原理
- 下一篇： java常用代码总结