前言
今天來介紹下TreeMap,TreeMap是基于紅黑樹結構實現的一種Map，要分析TreeMap的實現首先就要對紅黑樹有所了解。
構造圖如下:
藍色線條：繼承
綠色線條：接口實現
正文
TreeMap底層是基于紅黑樹（Red-Black tree）實現，所以在學習TreeMap之前我們先來了解下紅黑樹。
紅黑樹又稱紅-黑二叉樹，它首先是一顆二叉樹，它具體二叉樹所有的特性。同時紅黑樹更是一顆自平衡的排序二叉樹。
我們知道一顆基本的二叉樹他們都需要滿足一個基本性質--即樹中的任何節(jié)點的值大于它的左子節(jié)點，且小于它的右子節(jié)點。按照這個基本性質使得樹的檢索效率大大提高。我們知道在生成二叉樹的過程是非常容易失衡的，最壞的情況就是一邊倒（只有右/左子樹），這樣勢必會導致二叉樹的檢索效率大大降低（O(n)），所以為了維持二叉樹的平衡，大牛們提出了各種實現的算法，如：AVL，SBT，伸展樹，TREAP ，紅黑樹等等。
平衡二叉樹必須具備如下特性：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。也就是說該二叉樹的任何一個等等子節(jié)點，其左右子樹的高度都相近。
紅黑樹顧名思義就是節(jié)點是紅色或者黑色的平衡二叉樹，它通過顏色的約束來維持著二叉樹的平衡。對于一棵有效的紅黑樹二叉樹而言我們必須增加如下規(guī)則：
- 每個節(jié)點都只能是紅色或者黑色
- 根節(jié)點是黑色
- 每個葉節(jié)點（NIL節(jié)點，空節(jié)點）是黑色的。
- 如果一個結點是紅的，則它兩個子節(jié)點都是黑的。也就是說在一條路徑上不能出現相鄰的兩個紅色結點。
- 從任一節(jié)點到其每個葉子的所有路徑都包含相同數目的黑色節(jié)點。
紅黑樹示意圖如下：
上面的規(guī)則前4條都好理解，第5條規(guī)則到底是什么情況，下面簡單解釋下，比如圖中紅8到1左邊的葉子節(jié)點的路徑包含兩個黑色節(jié)點，到6下面的葉子節(jié)點的路徑也包含兩個黑色節(jié)點。
但是在在添加或刪除節(jié)點后，紅黑樹就發(fā)生了變化，可能不再滿足上面的5個特性，為了保持紅黑樹的以上特性，就有了三個動作：左旋、右旋、著色。
下面來看下什么是紅黑樹的左旋和右旋：
對x進行左旋，意味著"將x變成一個左節(jié)點"。
對y進行右旋，意味著"將y變成一個右節(jié)點"。
如果還是沒看明白，下面找了兩張左旋和右旋的動態(tài)圖
ok，對二叉樹、紅黑樹的概念有所了解后，我們來看下紅黑樹的兩個主要邏輯添加和刪除，看看TreeMap是怎么實現的。
TreeMap簡介
TreeMap定義
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
TreeMap 是一個有序的key-value集合，它是通過紅黑樹實現的。
TreeMap 繼承于AbstractMap，所以它是一個Map，即一個key-value集合。
TreeMap 實現了NavigableMap接口，意味著它支持一系列的導航方法。比如返回有序的key集合。
TreeMap 實現了Cloneable接口，意味著它能被克隆。
TreeMap 實現了java.io.Serializable接口，意味著它支持序列化。
TreeMap基于紅黑樹（Red-Black tree）實現。該映射根據其鍵的自然順序進行排序，或者根據創(chuàng)建映射時提供的 Comparator 進行排序，具體取決于使用的構造方法。
TreeMap的基本操作 containsKey、get、put 和 remove 的時間復雜度是 log(n) 。
另外，TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fast的。
TreeMap屬性
// 比較器
private final Comparator<? super K> comparator;
// 紅黑樹根節(jié)點
private transient Entry<K,V> root = null;
// 集合元素數量
private transient int size = 0;
// "fail-fast"集合修改記錄
private transient int modCount = 0;
TreeMap的本質是R-B Tree(紅黑樹)，它包含幾個重要的成員變量： root, size, comparator。
- root 是紅黑數的根節(jié)點。它是Entry類型，Entry是紅黑數的節(jié)點，它包含了紅黑數的6個基本組成成分：key(鍵)、value(值)、left(左孩子)、right(右孩子)、parent(父節(jié)點)、color(顏色)。Entry節(jié)點根據key進行排序，Entry節(jié)點包含的內容為value。
- 紅黑數排序時，根據Entry中的key進行排序；Entry中的key比較大小是根據比較器comparator來進行判斷的。
- size是紅黑數中節(jié)點的個數。
Entry是樹的節(jié)點類，我們來看一下Entry的定義：
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
// 左孩子節(jié)點
Entry<K,V> left = null;
// 右孩子節(jié)點
Entry<K,V> right = null;
// 父節(jié)點
Entry<K,V> parent;
// 紅黑樹用來表示節(jié)點顏色的屬性，默認為黑色
boolean color = BLACK;
/**
* 用key，value和父節(jié)點構造一個Entry，默認為黑色
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
public K getKey() {
return key ;
}
public V getValue() {
return value ;
}
public V setValue(V value) {
V oldValue = this.value ;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return valEquals( key,e.getKey()) && valEquals( value,e.getValue());
}
public int hashCode() {
int keyHash = (key ==null ? 0 : key.hashCode());
int valueHash = (value ==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}
public String toString() {
return key + "=" + value;
}
}
Entry類理解起來比較簡單（因為我們前面看過很多的Entry類了），主要是定義了樹的孩子和父親節(jié)點引用，和紅黑顏色屬性，并對equals和hashCode進行重寫，以利于比較是否相等。
HashMap構造函數
/**
* 默認構造方法，comparator為空，代表使用key的自然順序來維持TreeMap的順序，這里要求key必須實現Comparable接口
*/
public TreeMap() {
comparator = null;
}
/**
* 用指定的比較器構造一個TreeMap
*/
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
/**
* 構造一個指定map的TreeMap，同樣比較器comparator為空，使用key的自然順序排序
*/
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
/**
* 構造一個指定SortedMap的TreeMap，根據SortedMap的比較器來來維持TreeMap的順序
*/
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
從構造方法中可以看出，要創(chuàng)建一個紅黑樹實現的TreeMap必須要有一個用于比較大小的比較器，因為只有能夠比較大小才能實現紅黑樹的左孩子<樹根<右孩子的特點。
API方法摘要
TreeMap源碼解析(基于JDK1.6.0_45)
紅黑樹的添加原理及TreeMap的put實現
將一個節(jié)點添加到紅黑樹中，通常需要下面幾個步驟：
- 將紅黑樹當成一顆二叉查找樹，將節(jié)點插入.
這一步比較簡單，就上開始我們自己寫的二叉查找樹的操作一樣，至于為什么可以這樣插入，是因為紅黑樹本身就是一個二叉查找樹。 - 將新插入的節(jié)點設置為紅色
有沒有疑問，為什么新插入的節(jié)點一定要是紅色的，因為新插入節(jié)點為紅色，不會違背紅黑規(guī)則第（5）條，少違背一條就少處理一種情況。 - 通過旋轉和著色，使它恢復平衡，重新變成一顆符合規(guī)則的紅黑樹。
要想知道怎么樣進行左旋和右旋，首先就要知道為什么要進行左旋和右旋。
我們來對比下紅黑樹的規(guī)則和新插入節(jié)點后的情況，看下新插入節(jié)點會違背哪些規(guī)則。
（1）節(jié)點是紅色或黑色。
這一點肯定是不會違背的了。
（2）根節(jié)點是黑色。
這一點也不會違背了，如果是根節(jié)點，只需將根節(jié)點插入就好了，因為默認是黑色。
（3）每個葉節(jié)點（NIL節(jié)點，空節(jié)點）是黑色的。
這一點也不會違背的，我們插入的是非空的節(jié)點，不會影響空節(jié)點。
（4）每個紅色節(jié)點的兩個子節(jié)點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)
這一點是有可能違背的，我們將新插入的節(jié)點都設置成紅色，如果其父節(jié)點也是紅色的話，那就產生沖突了。
（5）從任一節(jié)點到其每個葉子的所有路徑都包含相同數目的黑色節(jié)點。
這一點也不會違背，因為我們將新插入的節(jié)點都設置成紅色。
了解了紅黑樹左旋和右旋操作，以及新插入節(jié)點主要是可能會違背紅黑樹的規(guī)則（4）后，我們來分析下，添加新節(jié)點的過程有哪幾種情況：
（1）新插入節(jié)點為根節(jié)點。這種情況直接將新插入節(jié)點設置為根節(jié)點即可，無需進行后續(xù)的旋轉和著色處理。
（2）新插入節(jié)點的父節(jié)點是黑色。這種情況直接將新節(jié)點插入即可，不會違背規(guī)則（4）。
（3）新插入節(jié)點的父節(jié)點是紅色。這種情況會違背規(guī)則（4），而這種情況又分為了以下幾種，下面進行圖解：
①新插入節(jié)點N的父節(jié)點P和叔叔節(jié)點U都是紅色。方法是：將祖父節(jié)點G設置為紅色，父節(jié)點P和叔叔節(jié)點U設置為黑色，這時候就看似平衡了。但是，如果祖父節(jié)點G的父節(jié)點也是紅色，這時候又違背規(guī)則（4）了，怎么辦，方法是：將GPUN這一組看成一個新的節(jié)點，按照前面的方案遞歸；又但是根節(jié)點為紅就違反規(guī)則（2）了，怎么辦，方法是直接將根節(jié)點設置為黑色（兩個連續(xù)黑色是沒問題的）。
②新插入節(jié)點N的父節(jié)點P是紅色，叔叔節(jié)點U是黑色或者缺少，且新節(jié)點N是P的右孩子。方法是：左旋父節(jié)點P。左旋后N和P角色互換，但是P和N還是連續(xù)的兩個紅色節(jié)點，還沒有平衡，怎么辦，看第三種情況。
③新插入節(jié)點N的父節(jié)點P是紅色，叔叔節(jié)點U是黑色或者缺少，且新節(jié)點N是P的左孩子。方法是：右旋祖父節(jié)點G，然后將P設置為黑色，G設置為紅色，達到平衡。此時父節(jié)點P是黑色，所有不用擔心P的父節(jié)點是紅色。
當然上面說的三種情況都是基于一個前提：新插入節(jié)點N的父節(jié)點P是祖父節(jié)點G的左孩子，如果P是G的右孩子又是什么情況呢？其實情況和上面是相似的，只需要調整左旋還是右旋，這里就不細講了。
上面分析了這么多，到底TreeMap是怎么實現的呢，我們來看下：
public V put(K key, V value) {
// 根節(jié)點
Entry<K,V> t = root;
// 如果根節(jié)點為空，則直接創(chuàng)建一個根節(jié)點，返回
if (t == null) {
// TBD:
// 5045147: (coll) Adding null to an empty TreeSet should
// throw NullPointerException
//
// compare(key, key); // type check
root = new Entry<K,V>(key, value, null);
size = 1;
modCount++;
return null;
}
// 記錄比較結果
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
// 當前使用的比較器
Comparator<? super K> cpr = comparator ;
// 如果比較器不為空，就是用指定的比較器來維護TreeMap的元素順序
if (cpr != null) {
// do while循環(huán)，查找key要插入的位置（也就是新節(jié)點的父節(jié)點是誰）
do {
// 記錄上次循環(huán)的節(jié)點t
parent = t;
// 比較當前節(jié)點的key和新插入的key的大小
cmp = cpr.compare(key, t. key);
// 新插入的key小的話，則以當前節(jié)點的左孩子節(jié)點為新的比較節(jié)點
if (cmp < 0)
t = t. left;
// 新插入的key大的話，則以當前節(jié)點的右孩子節(jié)點為新的比較節(jié)點
else if (cmp > 0)
t = t. right;
else
// 如果當前節(jié)點的key和新插入的key想的的話，則覆蓋map的value，返回
return t.setValue(value);
// 只有當t為null，也就是沒有要比較節(jié)點的時候，代表已經找到新節(jié)點要插入的位置
} while (t != null);
}
else {
// 如果比較器為空，則使用key作為比較器進行比較
// 這里要求key不能為空，并且必須實現Comparable接口
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
// 和上面一樣，喜歡查找新節(jié)點要插入的位置
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é)點的父節(jié)點后，創(chuàng)建節(jié)點對象
Entry<K,V> e = new Entry<K,V>(key, value, parent);
// 如果新節(jié)點key的值小于父節(jié)點key的值，則插在父節(jié)點的左側
if (cmp < 0)
parent. left = e;
// 如果新節(jié)點key的值大于父節(jié)點key的值，則插在父節(jié)點的右側
else
parent. right = e;
// 插入新的節(jié)點后，為了保持紅黑樹平衡，對紅黑樹進行調整
fixAfterInsertion(e);
// map元素個數+1
size++;
modCount++;
return null;
}
/** 新增節(jié)點后對紅黑樹的調整方法 */
private void fixAfterInsertion(Entry<K,V> x) {
// 將新插入節(jié)點的顏色設置為紅色
x. color = RED;
// while循環(huán)，保證新插入節(jié)點x不是根節(jié)點或者新插入節(jié)點x的父節(jié)點不是紅色（這兩種情況不需要調整）
while (x != null && x != root && x. parent.color == RED) {
// 如果新插入節(jié)點x的父節(jié)點是祖父節(jié)點的左孩子
if (parentOf(x) == leftOf(parentOf (parentOf(x)))) {
// 取得新插入節(jié)點x的叔叔節(jié)點
Entry<K,V> y = rightOf(parentOf (parentOf(x)));
// 如果新插入x的父節(jié)點是紅色-------------------①
if (colorOf(y) == RED) {
// 將x的父節(jié)點設置為黑色
setColor(parentOf (x), BLACK);
// 將x的叔叔節(jié)點設置為黑色
setColor(y, BLACK);
// 將x的祖父節(jié)點設置為紅色
setColor(parentOf (parentOf(x)), RED);
// 將x指向祖父節(jié)點，如果x的祖父節(jié)點的父節(jié)點是紅色，按照上面的步奏繼續(xù)循環(huán)
x = parentOf(parentOf (x));
} else {
// 如果新插入x的叔叔節(jié)點是黑色或缺少，且x的父節(jié)點是祖父節(jié)點的右孩子-------------------②
if (x == rightOf( parentOf(x))) {
// 左旋父節(jié)點
x = parentOf(x);
rotateLeft(x);
}
// 如果新插入x的叔叔節(jié)點是黑色或缺少，且x的父節(jié)點是祖父節(jié)點的左孩子-------------------③
// 將x的父節(jié)點設置為黑色
setColor(parentOf (x), BLACK);
// 將x的祖父節(jié)點設置為紅色
setColor(parentOf (parentOf(x)), RED);
// 右旋x的祖父節(jié)點
rotateRight( parentOf(parentOf (x)));
}
} else { // 如果新插入節(jié)點x的父節(jié)點是祖父節(jié)點的右孩子，下面的步奏和上面的相似，只不過左旋右旋的區(qū)分，不在細講
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)));
}
}
}
// 最后將根節(jié)點設置為黑色，不管當前是不是紅色，反正根節(jié)點必須是黑色
root.color = BLACK;
}
/**
* 對紅黑樹的節(jié)點(x)進行左旋轉
*
* 左旋示意圖(對節(jié)點x進行左旋)：
* px px
* / /
* x y
* / \ --(左旋)-- / \
* lx y x ry
* / \ / \
* ly ry lx ly
*
*/
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
// 取得要選擇節(jié)點p的右孩子
Entry<K,V> r = p. right;
// "p"和"r的左孩子"的相互指向...
// 將"r的左孩子"設為"p的右孩子"
p. right = r.left ;
// 如果r的左孩子非空，將"p"設為"r的左孩子的父親"
if (r.left != null)
r. left.parent = p;
// "p的父親"和"r"的相互指向...
// 將"p的父親"設為"y的父親"
r. parent = p.parent ;
// 如果"p的父親"是空節(jié)點，則將r設為根節(jié)點
if (p.parent == null)
root = r;
// 如果p是它父節(jié)點的左孩子，則將r設為"p的父節(jié)點的左孩子"
else if (p.parent. left == p)
p. parent.left = r;
else
// 如果p是它父節(jié)點的左孩子，則將r設為"p的父節(jié)點的左孩子"
p. parent.right = r;
// "p"和"r"的相互指向...
// 將"p"設為"r的左孩子"
r. left = p;
// 將"p的父節(jié)點"設為"r"
p. parent = r;
}
}
/**
* 對紅黑樹的節(jié)點進行右旋轉
*
* 右旋示意圖(對節(jié)點y進行右旋)：
* py py
* / /
* y x
* / \ --(右旋)-- / \
* x ry lx y
* / \ / \
* lx rx rx ry
*
*/
private void rotateRight(Entry<K,V> p) {
if (p != null) {
// 取得要選擇節(jié)點p的左孩子
Entry<K,V> l = p. left;
// 將"l的右孩子"設為"p的左孩子"
p. left = l.right ;
// 如果"l的右孩子"不為空的話，將"p"設為"l的右孩子的父親"
if (l.right != null) l. right.parent = p;
// 將"p的父親"設為"l的父親"
l. parent = p.parent ;
// 如果"p的父親"是空節(jié)點，則將l設為根節(jié)點
if (p.parent == null)
root = l;
// 如果p是它父節(jié)點的右孩子，則將l設為"p的父節(jié)點的右孩子"
else if (p.parent. right == p)
p. parent.right = l;
//如果p是它父節(jié)點的左孩子，將l設為"p的父節(jié)點的左孩子"
else p.parent .left = l;
// 將"p"設為"l的右孩子"
l. right = p;
// 將"l"設為"p父節(jié)點"
p. parent = l;
}
}
單純的看代碼和注釋，絕對會發(fā)出，cha這是什么亂七八糟的，任誰也看不懂，所以一定要結合上面的圖解，不懂了就看看圖，然后動手畫一下。
紅黑樹的刪除原理及TreeMap的remove實現
相比添加，紅黑樹的刪除顯得更加復雜了?？聪录t黑樹的刪除需要哪幾個步奏：
- 將紅黑樹當成一顆二叉查找樹，將節(jié)點刪除。
- 通過旋轉和著色，使它恢復平衡，重新變成一顆符合規(guī)則的紅黑樹。
刪除節(jié)點的關鍵是：
- 如果刪除的是紅色節(jié)點，不會違背紅黑樹的規(guī)則。
- 如果刪除的是黑色節(jié)點，那么這個路徑上就少了一個黑色節(jié)點，則違背了紅黑樹的規(guī)則。
來看下紅黑樹刪除節(jié)點會有哪幾種情況：
（1）被刪除的節(jié)點沒有孩子節(jié)點，即葉子節(jié)點。可直接刪除。
（2）被刪除的節(jié)點只有一個孩子節(jié)點，那么直接刪除該節(jié)點，然后用它的孩子節(jié)點頂替它的位置。
（3）被刪除的節(jié)點有兩個孩子節(jié)點。這種情況二叉樹的刪除有一個技巧，就是查找到要刪除的節(jié)點X，接著我們找到它左子樹的最大元素M，或者它右子樹的最小元素M，交換X和M的值，然后刪除節(jié)點M。此時M就最多只有一個子節(jié)點N(若是左子樹則沒有右子節(jié)點，若是右子樹則沒有左子節(jié)點 )，若M沒有孩子則進入(1)的情況，否則進入(2)的情況。
如上圖，我們假定節(jié)點X是要刪除的節(jié)點，而節(jié)點M是找到X右子樹的最小元素，所以節(jié)點M是X的替代節(jié)點，也就是說M是真正要刪除的節(jié)點。上面我們分析了此時的M只會有一個子節(jié)點N，當刪除節(jié)點M后，N將替代M作為M節(jié)點的父節(jié)點的子節(jié)點。刪除的節(jié)點M是黑色（刪除紅色不影響上面分析了），此時如果N是紅色，只需將N設置為黑色，就會重新達到平衡，不會出現該路徑上少了一個黑色節(jié)點的情況；但是如果N是紅色，情況則比較復雜，需要對紅黑樹進行調整，而這種情況又分為了以下幾種，下面進行圖解：
①N的兄弟節(jié)點B是紅色。方法是：交換P和B的顏色，左旋父節(jié)點P。此時并未完成平衡，左子樹仍然少了一個黑色節(jié)點，進入情況③。（B為紅色，P必然為黑色）
②N的父節(jié)點P是黑色，且兄弟節(jié)點B和它的兩個孩子節(jié)點也都是黑色。方法是：將N的兄弟節(jié)點B改為紅色，這樣從P出發(fā)到葉子節(jié)點的路徑都包含了相同的黑色節(jié)點，但是，對于節(jié)點P這個子樹，P的父節(jié)點G到P的葉子節(jié)點路徑上的黑色節(jié)點就少了一個，此時需要將P整體看做一個節(jié)點，繼續(xù)調整。
③N的父節(jié)點P為紅色，兄弟節(jié)點B和它的兩個孩子節(jié)點也都是黑色。此時只需要交換P和B的顏色，將P改為黑色，B改為紅色，則可到達平衡。這相當于既然節(jié)點N路徑少了一個黑色節(jié)點，那么B路徑也少一個黑色節(jié)點，這兩個路徑達到平衡，為了防止P路徑少一個黑色節(jié)點，將P節(jié)點置黑，則達到最終平衡。
④N的兄弟節(jié)點B是黑色，B的左孩子節(jié)點BL是紅色，B的右孩子節(jié)點BR是黑色，P為任意顏色。方法是：交換B和BL的顏色，右旋節(jié)點B。此時N子樹路徑并沒有增加黑色節(jié)點，也就是沒有達到平衡，此時進入下一種情況⑤。
⑤N的兄弟節(jié)點B是黑色，B的右孩子節(jié)點BR是紅色，B的左孩子節(jié)點BL任意顏色，P任意顏色。方法是：BR變?yōu)楹谏琍變?yōu)楹谏?，B變?yōu)镻的顏色；左旋節(jié)點B。首先給N路徑增加一個黑色節(jié)點P，P原位置上的顏色不變；S路徑少了一個黑色節(jié)點，于是將BR改為黑色，最終達到了平衡。
上面對紅黑樹刪除的原理和刪除過程中遇到的情況進行了分析說明，我們得到的結論是紅黑樹的刪除遇到的主要問題就是被刪除路徑上的黑色節(jié)點減少，于是需要進行一系列旋轉和著色，當然上面的情況是基于M是X右子樹的最小元素，而M如果是X左子樹的最大元素和上面的情況是相似的，我們具體看下TreeMap的代碼是怎么實現的：
public V remove(Object key) {
// 根據key查找到對應的節(jié)點對象
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
// 記錄key對應的value，供返回使用
V oldValue = p. value;
// 刪除節(jié)點
deleteEntry(p);
return oldValue;
}
private void deleteEntry(Entry<K,V> p) {
modCount++;
// map容器的元素個數減一
size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
// 如果被刪除的節(jié)點p的左孩子和右孩子都不為空，則查找其替代節(jié)點-----------這里表示要刪除的節(jié)點有兩個孩子（3）
if (p.left != null && p. right != null) {
// 查找p的替代節(jié)點
Entry<K,V> s = successor (p);
p. key = s.key ;
p. value = s.value ;
// 將p指向替代節(jié)點，※※※※※※從此之后的p不再是原先要刪除的節(jié)點p，而是替代者p（就是圖解里面講到的M） ※※※※※※
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
// replacement為替代節(jié)點p的繼承者（就是圖解里面講到的N），p的左孩子存在則用p的左孩子替代，否則用p的右孩子
Entry<K,V> replacement = (p. left != null ? p.left : p. right);
if (replacement != null) { // 如果上面的if有兩個孩子不通過--------------這里表示要刪除的節(jié)點只有一個孩子（2）
// Link replacement to parent
// 將p的父節(jié)點拷貝給替代節(jié)點
replacement. parent = p.parent ;
// 如果替代節(jié)點p的父節(jié)點為空，也就是p為跟節(jié)點，則將replacement設置為根節(jié)點
if (p.parent == null)
root = replacement;
// 如果替代節(jié)點p是其父節(jié)點的左孩子，則將replacement設置為其父節(jié)點的左孩子
else if (p == p.parent. left)
p. parent.left = replacement;
// 如果替代節(jié)點p是其父節(jié)點的左孩子，則將replacement設置為其父節(jié)點的右孩子
else
p. parent.right = replacement;
// Null out links so they are OK to use by fixAfterDeletion.
// 將替代節(jié)點p的left、right、parent的指針都指向空，即解除前后引用關系（相當于將p從樹種摘除），使得gc可以回收
p. left = p.right = p.parent = null;
// Fix replacement
// 如果替代節(jié)點p的顏色是黑色，則需要調整紅黑樹以保持其平衡
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
// 如果要替代節(jié)點p沒有父節(jié)點，代表p為根節(jié)點，直接刪除即可
root = null;
} else { // No children. Use self as phantom replacement and unlink.
// 判斷進入這里說明替代節(jié)點p沒有孩子--------------這里表示沒有孩子則直接刪除（1）
// 如果p的顏色是黑色，則調整紅黑樹
if (p.color == BLACK)
fixAfterDeletion(p);
// 下面刪除替代節(jié)點p
if (p.parent != null) {
// 解除p的父節(jié)點對p的引用
if (p == p.parent .left)
p. parent.left = null;
else if (p == p.parent. right)
p. parent.right = null;
// 解除p對p父節(jié)點的引用
p. parent = null;
}
}
}
/**
* 查找要刪除節(jié)點的替代節(jié)點
*/
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;
}
}
/** From CLR */
private void fixAfterDeletion(Entry<K,V> x) {
// while循環(huán)，保證要刪除節(jié)點x不是跟節(jié)點，并且是黑色（根節(jié)點和紅色不需要調整）
while (x != root && colorOf (x) == BLACK) {
// 如果要刪除節(jié)點x是其父親的左孩子
if (x == leftOf( parentOf(x))) {
// 取出要刪除節(jié)點x的兄弟節(jié)點
Entry<K,V> sib = rightOf(parentOf (x));
// 如果刪除節(jié)點x的兄弟節(jié)點是紅色---------------------------①
if (colorOf(sib) == RED) {
// 將x的兄弟節(jié)點顏色設置為黑色
setColor(sib, BLACK);
// 將x的父節(jié)點顏色設置為紅色
setColor(parentOf (x), RED);
// 左旋x的父節(jié)點
rotateLeft( parentOf(x));
// 將sib重新指向旋轉后x的兄弟節(jié)點 ，進入else的步奏③
sib = rightOf(parentOf (x));
}
// 如果x的兄弟節(jié)點的兩個孩子都是黑色-------------------------③
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf (sib)) == BLACK) {
// 將兄弟節(jié)點的顏色設置為紅色
setColor(sib, RED);
// 將x的父節(jié)點指向x，如果x的父節(jié)點是黑色，需要將x的父節(jié)點整天看做一個節(jié)點繼續(xù)調整-------------------------②
x = parentOf(x);
} else {
// 如果x的兄弟節(jié)點右孩子是黑色，左孩子是紅色-------------------------④
if (colorOf(rightOf(sib)) == BLACK) {
// 將x的兄弟節(jié)點的左孩子設置為黑色
setColor(leftOf (sib), BLACK);
// 將x的兄弟節(jié)點設置為紅色
setColor(sib, RED);
// 右旋x的兄弟節(jié)點
rotateRight(sib);
// 將sib重新指向旋轉后x的兄弟節(jié)點，進入步奏⑤
sib = rightOf(parentOf (x));
}
// 如果x的兄弟節(jié)點右孩子是紅色-------------------------⑤
setColor(sib, colorOf (parentOf(x)));
// 將x的父節(jié)點設置為黑色
setColor(parentOf (x), BLACK);
// 將x的兄弟節(jié)點的右孩子設置為黑色
setColor(rightOf (sib), BLACK);
// 左旋x的父節(jié)點
rotateLeft( parentOf(x));
// 達到平衡，將x指向root，退出循環(huán)
x = root;
}
} else { // symmetric // 如果要刪除節(jié)點x是其父親的右孩子，和上面情況一樣，這里不再細講
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);
}
刪除相對來說更加復雜，還是那句話一定要對照著圖解看代碼，否則是讀不懂的，別問我是怎么看懂得，我n天不看再看代碼也不知道123了。
終于看完了紅黑樹的增加和刪除，下面來看個稍微簡單的查詢：
紅黑樹的查詢
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p. value);
}
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
// 如果比較器為空，只是用key作為比較器查詢
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
// 取得root節(jié)點
Entry<K,V> p = root;
// 從root節(jié)點開始查找，根據比較器判斷是在左子樹還是右子樹
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;
}
final Entry<K,V> getEntryUsingComparator(Object key) {
K k = (K) key;
Comparator<? super K> cpr = comparator ;
if (cpr != null) {
Entry<K,V> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key );
if (cmp < 0)
p = p. left;
else if (cmp > 0)
p = p. right;
else
return p;
}
}
return null;
}
TreeMap遍歷方式
遍歷TreeMap的鍵值對
第一步：根據entrySet()獲取TreeMap的“鍵值對”的Set集合。
第二步：通過Iterator迭代器遍歷“第一步”得到的集合。
// 假設map是TreeMap對象
// map中的key是String類型，value是Integer類型
Integer integ = null;
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()) {
Map.Entry entry = (Map.Entry)iter.next();
// 獲取key
key = (String)entry.getKey();
// 獲取value
integ = (Integer)entry.getValue();
}
遍歷TreeMap的鍵
第一步：根據keySet()獲取TreeMap的“鍵”的Set集合。
第二步：通過Iterator迭代器遍歷“第一步”得到的集合。
// 假設map是TreeMap對象
// map中的key是String類型，value是Integer類型
String key = null;
Integer integ = null;
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
// 獲取key
key = (String)iter.next();
// 根據key，獲取value
integ = (Integer)map.get(key);
}
遍歷TreeMap的值
第一步：根據value()獲取TreeMap的“值”的集合。
第二步：通過Iterator迭代器遍歷“第一步”得到的集合。
// 假設map是TreeMap對象
// map中的key是String類型，value是Integer類型
Integer value = null;
Collection c = map.values();
Iterator iter= c.iterator();
while (iter.hasNext()) {
value = (Integer)iter.next();
}
TreeMap示例
下面通過實例來學習如何使用TreeMap
import java.util.*;
/**
* @desc TreeMap測試程序
*
* @author skywang
*/
public class TreeMapTest {
public static void main(String[] args) {
// 測試常用的API
testTreeMapOridinaryAPIs();
// 測試TreeMap的導航函數
//testNavigableMapAPIs();
// 測試TreeMap的子Map函數
//testSubMapAPIs();
}
/**
* 測試常用的API
*/
private static void testTreeMapOridinaryAPIs() {
// 初始化隨機種子
Random r = new Random();
// 新建TreeMap
TreeMap tmap = new TreeMap();
// 添加操作
tmap.put("one", r.nextInt(10));
tmap.put("two", r.nextInt(10));
tmap.put("three", r.nextInt(10));
System.out.printf("\n ---- testTreeMapOridinaryAPIs ----\n");
// 打印出TreeMap
System.out.printf("%s\n",tmap );
// 通過Iterator遍歷key-value
Iterator iter = tmap.entrySet().iterator();
while(iter.hasNext()) {
Map.Entry entry = (Map.Entry)iter.next();
System.out.printf("next : %s - %s\n", entry.getKey(), entry.getValue());
}
// TreeMap的鍵值對個數
System.out.printf("size: %s\n", tmap.size());
// containsKey(Object key) :是否包含鍵key
System.out.printf("contains key two : %s\n",tmap.containsKey("two"));
System.out.printf("contains key five : %s\n",tmap.containsKey("five"));
// containsValue(Object value) :是否包含值value
System.out.printf("contains value 0 : %s\n",tmap.containsValue(new Integer(0)));
// remove(Object key) ： 刪除鍵key對應的鍵值對
tmap.remove("three");
System.out.printf("tmap:%s\n",tmap );
// clear() ： 清空TreeMap
tmap.clear();
// isEmpty() : TreeMap是否為空
System.out.printf("%s\n", (tmap.isEmpty()?"tmap is empty":"tmap is not empty") );
}
/**
* 測試TreeMap的子Map函數
*/
public static void testSubMapAPIs() {
// 新建TreeMap
TreeMap tmap = new TreeMap();
// 添加“鍵值對”
tmap.put("a", 101);
tmap.put("b", 102);
tmap.put("c", 103);
tmap.put("d", 104);
tmap.put("e", 105);
System.out.printf("\n ---- testSubMapAPIs ----\n");
// 打印出TreeMap
System.out.printf("tmap:\n\t%s\n", tmap);
// 測試 headMap(K toKey)
System.out.printf("tmap.headMap(\"c\"):\n\t%s\n", tmap.headMap("c"));
// 測試 headMap(K toKey, boolean inclusive)
System.out.printf("tmap.headMap(\"c\", true):\n\t%s\n", tmap.headMap("c", true));
System.out.printf("tmap.headMap(\"c\", false):\n\t%s\n", tmap.headMap("c", false));
// 測試 tailMap(K fromKey)
System.out.printf("tmap.tailMap(\"c\"):\n\t%s\n", tmap.tailMap("c"));
// 測試 tailMap(K fromKey, boolean inclusive)
System.out.printf("tmap.tailMap(\"c\", true):\n\t%s\n", tmap.tailMap("c", true));
System.out.printf("tmap.tailMap(\"c\", false):\n\t%s\n", tmap.tailMap("c", false));
// 測試 subMap(K fromKey, K toKey)
System.out.printf("tmap.subMap(\"a\", \"c\"):\n\t%s\n", tmap.subMap("a", "c"));
// 測試
System.out.printf("tmap.subMap(\"a\", true, \"c\", true):\n\t%s\n",
tmap.subMap("a", true, "c", true));
System.out.printf("tmap.subMap(\"a\", true, \"c\", false):\n\t%s\n",
tmap.subMap("a", true, "c", false));
System.out.printf("tmap.subMap(\"a\", false, \"c\", true):\n\t%s\n",
tmap.subMap("a", false, "c", true));
System.out.printf("tmap.subMap(\"a\", false, \"c\", false):\n\t%s\n",
tmap.subMap("a", false, "c", false));
// 測試 navigableKeySet()
System.out.printf("tmap.navigableKeySet():\n\t%s\n", tmap.navigableKeySet());
// 測試 descendingKeySet()
System.out.printf("tmap.descendingKeySet():\n\t%s\n", tmap.descendingKeySet());
}
/**
* 測試TreeMap的導航函數
*/
public static void testNavigableMapAPIs() {
// 新建TreeMap
NavigableMap nav = new TreeMap();
// 添加“鍵值對”
nav.put("aaa", 111);
nav.put("bbb", 222);
nav.put("eee", 333);
nav.put("ccc", 555);
nav.put("ddd", 444);
System.out.printf("\n ---- testNavigableMapAPIs ----\n");
// 打印出TreeMap
System.out.printf("Whole list:%s%n", nav);
// 獲取第一個key、第一個Entry
System.out.printf("First key: %s\tFirst entry: %s%n",nav.firstKey(), nav.firstEntry());
// 獲取最后一個key、最后一個Entry
System.out.printf("Last key: %s\tLast entry: %s%n",nav.lastKey(), nav.lastEntry());
// 獲取“小于/等于bbb”的最大鍵值對
System.out.printf("Key floor before bbb: %s%n",nav.floorKey("bbb"));
// 獲取“小于bbb”的最大鍵值對
System.out.printf("Key lower before bbb: %s%n", nav.lowerKey("bbb"));
// 獲取“大于/等于bbb”的最小鍵值對
System.out.printf("Key ceiling after ccc: %s%n",nav.ceilingKey("ccc"));
// 獲取“大于bbb”的最小鍵值對
System.out.printf("Key higher after ccc: %s%n\n",nav.higherKey("ccc"));
}
}
運行結果：
{one=8, three=4, two=2}
next : one - 8
next : three - 4
next : two - 2
size: 3
contains key two : true
contains key five : false
contains value 0 : false
tmap:{one=8, two=2}
tmap is empty
總結
到此TreeMap就分析完了，其實大部分時間都在整理紅黑樹，在數據結構中樹是比較難懂的一個，其算法也比較復雜，對于樹的理解一定要多看圖畫圖，要明白這么做是為了解決什么問題，這么做又有什么好處，當然看一遍看不懂就要多看幾遍了。什么你問我平時工作中會用到樹嗎？那真的要看你做的什么性質的工作，如果是web、客戶端開發(fā)，調用api就可以了對吧，如果是從事底層開發(fā)，比如文件系統，存儲系統，緩存等工作必須是需要的。當然就算用不到，理解了也是有益無害的。
參考
該文為本人學習的筆記，方便以后自己跳槽前復習。參考網上各大帖子，取其精華整合自己的理解而成。集合框架源碼面試經常會問，所以解讀源碼十分必要,希望對你有用。
Java提高篇（二七）-----TreeMap
Java 集合系列12之 TreeMap詳細介紹(源碼解析)和使用示例
給jdk寫注釋系列之jdk1.6容器(7)-TreeMap源碼解析
紅黑樹(五)之 Java的實現 - 如果天空不死
整理的集合框架思維導圖
個人整理的Java集合框架思維導圖，動態(tài)維護。導出的圖片無法查看備注的一些信息，所以需要源文件的童鞋可以關注我個人主頁上的公眾號，回復Java集合框架即可獲取源文件。
一直覺得自己寫的不是技術，而是情懷，一篇篇文章是自己這一路走來的痕跡?？繉I(yè)技能的成功是最具可復制性的，希望我的這條路能讓你少走彎路，希望我能幫你抹去知識的蒙塵，希望我能幫你理清知識的脈絡，希望未來技術之巔上有你也有我。
