一：TreeMap整體認識
我們知道HashMap，它保證了以O(1)的時間複雜度進行增、删、改、查，從存儲角度考慮，這兩種資料結構是非常優秀的。但是HashMap還是有自己的局限性----它不具備統計性能，或者說它的統計性能時間複雜度并不是很好才更準确，所有的統計必須周遊所有Entry，是以時間複雜度為O(N)。
比如Map的Key有1、2、3、4、5、6、7，我現在要統計：
- 所有Key比3大的鍵值對有哪些
- Key最小的和Key最大的是哪兩個
就類似這些操作，HashMap做得比較差，此時我們可以使用TreeMap。TreeMap的Key按照自然順序進行排序或者根據建立映射時提供的Comparator接口進行排序。TreeMap為增、删、改、查這些操作提供了log(N)的時間開銷，從存儲角度而言，這比HashMap的O(1)時間複雜度要差些；但是在統計性能上，TreeMap同樣可以保證log(N)的時間開銷，這又比HashMap的O(N)時間複雜度好不少。
是以：如果隻需要存儲功能，使用HashMap是一種更好的選擇；如果還需要保證統計性能或者需要對Key按照一定規則進行排序，那麼使用TreeMap是一種更好的選擇。
TreeMap是由紅黑樹來實作的，下面看一下紅黑樹
二：紅黑樹
紅黑樹又稱紅-黑二叉樹，它首先是一顆二叉樹，它具體二叉樹所有的特性。同時紅黑樹更是一顆自平衡的排序二叉樹。
我們知道一顆基本的二叉樹他們都需要滿足一個基本性質–即樹中的任何節點的值大于它的左子節點，且小于它的右子節點。按照這個基本性質使得樹的檢索效率大大提高。我們知道在生成二叉樹的過程是非常容易失衡的，最壞的情況就是一邊倒（隻有右/左子樹），這樣勢必會導緻二叉樹的檢索效率大大降低（O(n)），是以為了維持二叉樹的平衡，大牛們提出了各種實作的算法，如：AVL，SBT，伸展樹，TREAP ，紅黑樹等等。
平衡二叉樹必須具備如下特性：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。也就是說該二叉樹的任何一個等等子節點，其左右子樹的高度都相近。
紅黑樹顧名思義就是節點是紅色或者黑色的平衡二叉樹，它通過顔色的限制來維持着二叉樹的平衡。對于一棵有效的紅黑樹二叉樹而言我們必須增加如下規則：
- 每個節點都隻能是紅色或者黑色
- 根節點是黑色
- 每個葉節點（NIL節點，空節點）是黑色的。
- 如果一個結點是紅的，則它兩個子節點都是黑的。也就是說在一條路徑上不能出現相鄰的兩個紅色結點。
- 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。
這些限制強制了紅黑樹的關鍵性質: 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結果是這棵樹大緻上是平衡的。因為操作比如插入、删除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。是以紅黑樹它是複雜而高效的，其檢索效率O(log n)。下圖為一顆典型的紅黑二叉樹。
紅黑樹不是重點，具體了解紅黑樹可以參考：
紅黑樹系列集錦
紅黑樹資料結構剖析
三：源碼分析
類資訊
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
TreeMap繼承AbstractMap，實作NavigableMap、Cloneable、Serializable三個接口。其中AbstractMap表明TreeMap為一個Map即支援key-value的集合， NavigableMap則意味着它支援一系列的導航方法，具備針對給定搜尋目标傳回最接近比對項的導航方法 。
屬性資訊
//比較器，因為TreeMap是有序的，通過comparator接口我們可以對TreeMap的内部排序進行精密的控制
//可以通過構造函數自定義比較器，也可以使用預設比較器
private final Comparator<? super K> comparator;
//treeMap的根節點
private transient Entry<K,V> root = null;
//容器大小
private transient int size = 0;
//修改次數
private transient int modCount = 0;
節點的Entry内部類資訊
static final class Entry<K,V> implements Map.Entry<K,V> {
//鍵
K key;
//值
V value;
//左孩子
Entry<K,V> left = null;
//右孩子
Entry<K,V> right = null;
//父節點
Entry<K,V> parent;
//顔色
boolean color = BLACK;
put方法
put方法步驟如下：
1.擷取根節點，根節點為空，産生一個根節點，将其着色為黑色，退出餘下流程
2.擷取比較器，如果傳入的Comparator接口不為空，使用傳入的Comparator接口實作類進行比較；如果傳入的Comparator接口為空，将Key強轉為Comparable接口進行比較
3.從根節點開始逐一依照規定的排序算法進行比較，取比較值cmp，如果cmp=0，表示插入的Key已存在；如果cmp>0，取目前節點的右子節點；如果cmp<0，取目前節點的左子節點
4.排除插入的Key已存在的情況，第（3）步的比較一直比較到目前節點t的左子節點或右子節點為null，此時t就是我們尋找到的節點，cmp>0則準備往t的右子節點插入新節點，cmp<0則準備往t的左子節點插入新節點
5.new出一個新節點，預設為黑色，根據cmp的值向t的左邊或者右邊進行插入
6.插入之後進行修複，包括左旋、右旋、重新着色這些操作，讓樹保持平衡性
public V put(K key, V value) {
//用t表示二叉樹的目前節點
Entry<K,V> t = root;
//t為null表示一個空樹，即TreeMap中沒有任何元素，直接插入
if (t == null) {
//比較key值，個人覺得這句代碼沒有任何意義，空樹還需要比較、排序？
compare(key, key); // type (and possibly null) check
//将新的key-value鍵值對建立為一個Entry節點，并将該節點賦予給root
root = new Entry<>(key, value, null);
//容器的size = 1，表示TreeMap集合中存在一個元素
size = 1;
//修改次數 + 1
modCount++;
return null;
}
int cmp; //cmp表示key排序的傳回結果
Entry<K,V> parent; //父節點
// split comparator and comparable paths
Comparator<? super K> cpr = comparator; //指定的排序算法
//如果cpr不為空，則采用既定的排序算法進行建立TreeMap集合
if (cpr != null) {
do {
parent = t; //parent指向上次循環後的t
//比較新增節點的key和目前節點key的大小
cmp = cpr.compare(key, t.key);
//cmp傳回值小于0，表示新增節點的key小于目前節點的key，則以目前節點的左子節點作為新的目前節點
if (cmp < 0)
t = t.left;
//cmp傳回值大于0，表示新增節點的key大于目前節點的key，則以目前節點的右子節點作為新的目前節點
else if (cmp > 0)
t = t.right;
//cmp傳回值等于0，表示兩個key值相等，則新值覆寫舊值，并傳回新值
else
return t.setValue(value);
} while (t != null);
}
//如果cpr為空，則采用預設的排序算法進行建立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);
}
//将新增節點當做parent的子節點
Entry<K,V> e = new Entry<>(key, value, parent);
//如果新增節點的key小于parent的key，則當做左子節點
if (cmp < 0)
parent.left = e;
//如果新增節點的key大于parent的key，則當做右子節點
else
parent.right = e;
/*
* 上面已經完成了排序二叉樹的的建構，将新增節點插入該樹中的合适位置
* 下面fixAfterInsertion()方法就是對這棵樹進行調整、平衡，具體過程參考上面的五種情況
*/
fixAfterInsertion(e);
//TreeMap元素數量 + 1
size++;
//TreeMap容器修改次數 + 1
modCount++;
return null;
}
第1~第5步都沒有什麼問題，紅黑樹最核心的應當是第6步插入資料之後進行的修複工作，對應的Java代碼是TreeMap中的fixAfterInsertion方法
/**
* 新增節點後的修複操作
* x 表示新增節點
*/
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED; //新增節點的顔色為紅色
//循環 直到 x不是根節點，且x的父節點不為紅色
while (x != null && x != root && x.parent.color == RED) {
//如果X的父節點（P）是其父節點的父節點（G）的左節點
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//擷取X的叔節點(U)
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
//如果X的叔節點（U） 為紅色（情況三）
if (colorOf(y) == RED) {
//将X的父節點（P）設定為黑色
setColor(parentOf(x), BLACK);
//将X的叔節點（U）設定為黑色
setColor(y, BLACK);
//将X的父節點的父節點（G）設定紅色
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
}
//如果X的叔節點（U為黑色）；這裡會存在兩種情況（情況四、情況五）
else {
//如果X節點為其父節點（P）的右子樹，則進行左旋轉（情況四）
if (x == rightOf(parentOf(x))) {
//将X的父節點作為X
x = parentOf(x);
//右旋轉
rotateLeft(x);
}
//（情況五）
//将X的父節點（P）設定為黑色
setColor(parentOf(x), BLACK);
//将X的父節點的父節點（G）設定紅色
setColor(parentOf(parentOf(x)), RED);
//以X的父節點的父節點（G）為中心右旋轉
rotateRight(parentOf(parentOf(x)));
}
}
//如果X的父節點（P）是其父節點的父節點（G）的右節點
else {
//擷取X的叔節點（U）
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
//如果X的叔節點（U） 為紅色（情況三）
if (colorOf(y) == RED) {
//将X的父節點（P）設定為黑色
setColor(parentOf(x), BLACK);
//将X的叔節點（U）設定為黑色
setColor(y, BLACK);
//将X的父節點的父節點（G）設定紅色
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
}
//如果X的叔節點（U為黑色）；這裡會存在兩種情況（情況四、情況五）
else {
//如果X節點為其父節點（P）的右子樹，則進行左旋轉（情況四）
if (x == leftOf(parentOf(x))) {
//将X的父節點作為X
x = parentOf(x);
//右旋轉
rotateRight(x);
}
//（情況五）
//将X的父節點（P）設定為黑色
setColor(parentOf(x), BLACK);
//将X的父節點的父節點（G）設定紅色
setColor(parentOf(parentOf(x)), RED);
//以X的父節點的父節點（G）為中心右旋轉
rotateLeft(parentOf(parentOf(x)));
}
}
}
//将根節點G強制設定為黑色
root.color = BLACK;
}
get方法
get方法相當于put方法就簡單多了，從根節點開始循環比較。
- 當key大于目前節點，把目前節點指針指向左孩子繼續循環。
- 當key小于目前節點，把目前節點的指針指向右孩子繼續循環。
- 當key等于目前節點，則傳回目前節點。
public V get(Object key) {
// 根據 key 擷取到對應的 Entry
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// 基于比較器的查找
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
//從根節點開始查找，當key小于目前節點，左孩子為目前節點繼續循環，當key大于目前節點
//右孩子為目前節點繼續循環，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;
}
remove方法
針對于紅黑樹的增加節點而言，删除顯得更加複雜，使原本就複雜的紅黑樹變得更加複雜。同時删除節點和增加節點一樣，同樣是找到删除的節點，删除之後調整紅黑樹。但是這裡的删除節點并不是直接删除，而是通過走了“彎路”通過一種捷徑來删除的：找到被删除的節點D的子節點C，用C來替代D，不是直接删除D，因為D被C替代了，直接删除C即可。是以這裡就将删除父節點D的事情轉變為了删除子節點C的事情，這樣處理就将複雜的删除事件簡單化了。子節點C的規則是：右分支最左邊，或者 左分支最右邊的。
紅-黑二叉樹删除節點，最大的麻煩是要保持 各分支黑色節點數目相等。 因為是删除，是以不用擔心存在顔色沖突問題——插入才會引起顔色沖突。
紅黑樹删除節點同樣會分成幾種情況，這裡是按照待删除節點有幾個兒子的情況來進行分類：
- 沒有兒子，即為葉結點。直接把父結點的對應兒子指針設為NULL，删除兒子結點就OK了。
- 隻有一個兒子。那麼把父結點的相應兒子指針指向兒子的獨生子，删除兒子結點也OK了。
- 有兩個兒子。這種情況比較複雜，但還是比較簡單。上面提到過用子節點C替代代替待删除節點D，然後删除子節點C即可。
public V remove(Object key) {
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// Link replacement to parent
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
// Null out links so they are OK to use by fixAfterDeletion.
p.left = p.right = p.parent = null;
// Fix replacement
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
root = null;
} else { // No children. Use self as phantom replacement and unlink.
if (p.color == BLACK)
fixAfterDeletion(p);
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;
}
}
}
删除後的調整
删除元素之後的調整和前面的插入元素調整的過程比起來更複雜。它不是一個簡單的在原來過程中取反。我們先從一個最基本的點開始入手。首先一個，我們要進行調整的這個點肯定是因為我們要删除的這個點破壞了紅黑樹的本質特性。而如果我們删除的這個點是紅色的，則它肯定不會破壞裡面的屬性。因為從前面删除的過程來看，我們這個要删除的點是已經在瀕臨葉節點的附近了，它要麼有一個子節點，要麼就是一個葉節點。如果它是紅色的，删除了，從上面的節點到葉節點所經曆的黑色節點沒有變化。是以，這裡的一個前置條件就是待删除的節點是黑色的。
在前面的那個前提下，我們要調整紅黑樹的目的就是要保證，這個原來是黑色的節點被删除後，我們要通過一定的變化，使得他們仍然是合法的紅黑樹。我們都知道，在一個黑色節點被删除後，從上面的節點到它所在的葉節點路徑所經曆的黑色節點就少了一個。我們需要做一些調整，使得它少的這個在後面某個地方能夠補上。
![通過TreeMap了解紅黑樹 總體介紹 預備知識 方法剖析 TreeSet[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)