前言：
在上一篇文章：Java集合框架—LinkedHashMap—源碼研讀 中，我們深入學習了LinkedHashMap，現在，讓我們開始學習更進階一點的內容——TreeMap。學習TreeMap前汁蝶，最好需要先了解一下比較器Comparat、二叉排序樹论悴、紅黑樹據結構的知識穿仪。
所以此篇文章，分為3個部分：
1.比較器Comparator和Comparable接口
2.紅黑樹和二叉排序樹
3.紅黑樹的左旋和右旋
4.TreeMap的源碼分析-put()方法意荤、fixAfterInsertion()解讀
1.比較器Comparator和Comparable接口
首先啊片，HashMap中的鍵值對是無序的，LinkedHashMap的出現使得鍵值對可以按照插入順序被遍歷玖像，但是有很多場景下紫谷，我需要根據插入其中的鍵值對中的key來進行排序，而不是簡單的根據插入順序捐寥。那么此時LinkedHashMap便無能為力了笤昨！這時，TreeMap就派上了用場握恳，因為TreeMap天生就實現了SortedMap接口瞒窒，而SortedMap是為了排序而存在的。
讓我們先看一下Map接口的關系圖和TreeMap的類關系圖：
可見：TreeMap繼承自AbstractMap乡洼，實現了NavigableMap崇裁、Cloneable和Serializable接口。
其中有一點需要注意束昵，NavigableMap繼承自SortedMap拔稳，而SortedMap接口就是TreeMap中對象有序的核心。
SortedMap接口是干嘛的锹雏？簡單來說SortedMap接口中包含Comparator比較器巴比，可以自定義比較方法用于實現key的比較。即實現SortedMap的類礁遵，其中的對象即可根據比較器中定義的方法轻绞，對key進行排序從而達到類中對象有序的目的。
目前java中SortedMap接口的實現類只有TreeMap佣耐。如果對Comparable和Comparator還不太熟悉政勃，可以看看下面的內容，否則可以pass掉晰赞。
Comparable 和 Comparator的區(qū)別：
首先稼病，Comparable和Comparator都是用于比較的接口，全名：java.lang.Comparable 和 java.util.Comparator
Comparable接口主要用于自然比較掖鱼，里面只有一個方法：public int compareTo(T o);
Integer然走、String都實現了Comparable接口并實現了接口中的compareTo方法，Integer中的compareTo方法如下：
public int compareTo(Integer anotherInteger) {
return compare(this.value, anotherInteger.value);
}
public static int compare(int x, int y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1);
}
Comparator主要用于外部定義的比較器戏挡，譬如自定義的某個bean對象需要進行比較芍瑞，那么比較的規(guī)則就可以通過Comparator來實現。
詳細可以參考:Java 解惑：Comparable 和 Comparator 的區(qū)別
說了前面的Comparator其實是為了給今天的主角TreeMap做鋪墊褐墅，因為TreeMap正是通過比較器Comparator中的方法來實現的排序拆檬，從而達到有序的目的。現在讓我們看看TreeMap的類定義：
private final Comparator<? super K> comparator;
private transient Entry<K,V> root;
private transient int size = 0;
private transient int modCount = 0;
類變量中第一位就是Comparator類的變量comparator妥凳，這個comparator即treeMap用于制定排序規(guī)則的比較器竟贯。root，即treeMap中的根節(jié)點逝钥；size和modCount我們都已經見過很多次屑那，就不說了。除了類變量外艘款，我們也注意到TreeMap的初始化有4種方式持际，分別是：
空構造器、定義了comparator的構造方法哗咆、初始Map作為參數的構造方法蜘欲、初始SortedMap作為參數的構造方法。現在晌柬，想一下如果初始化時未定義比較器comparator姥份，那么TreeMap還可以正常排序么？如果可以是怎樣排序的年碘？
答案是：YES
如果初始未定義比較器殿衰，則如果key是Integer、Double盛泡、String等已經實現了Comparable接口的類闷祥，否則會默認調用其compareTo方法來比較key的大小。
如果key沒有實現Comparable接口傲诵，則會報ClassCastException異常凯砍。
2.紅黑樹和二叉排序樹
紅黑樹，是一種近似平衡的二叉排序樹拴竹。
二叉排序樹(二叉搜索樹)或者是一棵空樹悟衩，或者是具有下列性質的二叉樹：
（1）若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值栓拜；
（2）若右子樹不空座泳，則右子樹上所有結點的值均大于它的根結點的值惠昔；
（3）左、右子樹也分別為二叉排序樹挑势；
（4）沒有鍵值相等的節(jié)點镇防。
紅黑樹，顧名思義潮饱，通過給樹節(jié)點增加一位来氧，顏色屬性，來標記節(jié)點的顏色香拉。顏色只能為紅或者黑色啦扬。這些顏色位用于確保樹在插入和刪除期間保持近似平衡。
讓我們看一下維基百科中對【紅黑樹】規(guī)則的講解：
除了對二叉搜索樹施加的要求之外凫碌，紅黑樹還必須滿足以下要求：[16]
- 每個節(jié)點都是紅色或黑色扑毡。
- 根是黑色的。有時會省略此規(guī)則盛险。由于根始終可以從紅色變?yōu)楹谏爬悖灰欢ㄏ喾矗虼嗽撘?guī)則對分析幾乎沒有影響枉层。
- 所有葉子（NIL）都是黑色的泉褐。
- 如果節(jié)點為紅色，則其子節(jié)點均為黑色鸟蜡。
- 從給定節(jié)點到其任何后代NIL節(jié)點的每條路徑都包含相同數量的黑色節(jié)點膜赃。
一些定義：從根到節(jié)點的黑色節(jié)點數是節(jié)點的黑色深度 ; 從根到葉子的所有路徑中的黑色節(jié)點的統一數量被稱為紅黑樹的黑色高度。[17]
這些約束強制執(zhí)行紅黑樹的關鍵屬性：從根到最遠葉子的路徑不超過從根到最近葉子的路徑的兩倍揉忘。結果是樹大致高度平衡跳座。由于諸如插入，刪除和查找值之類的操作需要與樹的高度成比例的最壞情況時間泣矛，因此與最普通的二叉搜索樹不同疲眷，這種高度的理論上限允許紅黑樹在最壞的情況下是有效的。
要了解為什么這是有保證的您朽，只需考慮屬性4和5的影響就足夠了狂丝。對于紅黑樹T，設B為屬性5中的黑色節(jié)點數哗总。讓從T的根到任何葉子的最短可能路徑由B個黑色節(jié)點組成几颜。可以通過插入紅色節(jié)點來構造更長的可能路徑讯屈。但是蛋哭，屬性4使得無法插入多個連續(xù)的紅色節(jié)點。因此涮母，忽略任何黑色NIL葉谆趾，最長可能路徑包括2 * B節(jié)點躁愿，交替黑色和紅色（這是最壞的情況）。計算黑色NIL葉沪蓬，最長可能路徑由2 * B-1個節(jié)點組成彤钟。
最短路徑具有所有黑色節(jié)點，并且最長路徑在紅色和黑色節(jié)點之間交替怜跑。由于所有最大路徑具有相同數量的黑色節(jié)點样勃，因此通過屬性5吠勘，這表明沒有路徑是任何其他路徑的兩倍多性芬。
紅黑樹，除了定義中規(guī)定的要求以外剧防，在Java實現中還增加了如下要求：
1..新插入的節(jié)點必須為紅色植锉。
2.任意節(jié)點其左右子樹最多相差2層紅節(jié)點。
3.插入過程（僅限于插入點那條路徑上）中不允許任一節(jié)點有2個紅色兒子節(jié)點峭拘。
這些規(guī)定使得紅黑樹的實際表現近似平衡的二叉排序樹俊庇，即一個n個節(jié)點的紅黑樹，其平均高度為logN,最差情況高度為2log(N+1). 故其查找效率為O(logN)鸡挠。綜合查找辉饱、插入和刪除節(jié)點所引起的時間開銷，其實際表現通常優(yōu)于平衡二叉樹拣展。
3.紅黑樹的左旋和右旋
為什么要介紹紅黑樹的左旋和右旋操作呢彭沼？因為，這是紅黑樹中最核心的操作备埃，在TreeMap源碼中插入或刪除紅黑樹中節(jié)點時姓惑，可能會引發(fā)紅黑樹結構的變化，那為了重新調整結構變化過的樹按脚，使之成為符合紅黑樹5項要求的樹于毙，最重要的操作就是1.改變某些節(jié)點的顏色；2.左旋rotateLeft和右旋rotateRight辅搬。
改變顏色比較容易唯沮，關鍵在于左旋和右旋操作，下面還是借用一下圖片來舉例說明堪遂，關于紅黑樹的左旋烂翰、右旋等詳細過程的圖文講解，部分引用于一篇github上不錯的文章：
A.左旋
如上圖所示蚤氏，以3號節(jié)點為中心的左旋操作甘耿，實際上是逆時針旋轉，對應的右旋即順時針旋轉竿滨〖烟瘢可以想象下捏境，3在左旋逆時針向下的過程中必然會和10號節(jié)點左下角的6發(fā)生碰撞，結果是3號節(jié)點成功上位毁葱，成為了10號節(jié)點新的左孩子垫言，那么被【碰撞出去】的6號節(jié)點只能順勢成為了3號節(jié)點的孩子(右孩子)
B.右旋
10號節(jié)點右旋，即順時針旋轉倾剿。旋轉到3號節(jié)點右下角成為其右孩子筷频。3號節(jié)點原本的右孩子6號節(jié)點被擠掉，成為了10號節(jié)點的左孩子前痘。
4.TreeMap的源碼分析-put()方法
在進入put方法前凛捏，我們先看一下TreeMap中紅黑樹Entry節(jié)點的定義：
如圖所示，Entry類的成員變量除了key-value外還有l(wèi)eftt芹缔、right用于標記左坯癣、右孩子節(jié)點；
parent用于標記父節(jié)點最欠。boolean類型的color變量用于記錄紅黑樹的顏色BLACK或RED示罗。
OK，現在讓我們看一下TreeMap中的put()方法：
首先芝硬，判斷紅黑樹的root節(jié)點蚜点，若為空則new一個root節(jié)點，將key拌阴、value值放置進去绍绘。
不空則進入下面：
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
創(chuàng)建一個Comparator比較器變量cpr，這個comparator可以由外部傳入皮官，如果不傳則為null脯倒。
然后：
if (cpr != null) {
...
}
else {...}
如果cpr！=null則進入第一個分支捺氢，若cpr==null則進入else分支藻丢，由于分支內操作類似，我們以else分支為例看一下操作：
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
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);
}
else分支下首先會進行判斷：if (key == null)摄乒，如果成立則throw new NullPointerException();
否則創(chuàng)建一個Comparable比較器變量k悠反，值為key。這一步需要注意的是馍佑，如果初始沒有設置比較器斋否，而且key的類型并沒有實現Comparable接口，則會拋出ClassCastException拭荤，表示類型轉換異常茵臭。當然，如果key是Integer,String等實現了Comparable接口舅世，且覆寫了compareTo方法的類型旦委，則不會拋異常奇徒。
下一步，進入do...while循環(huán)中去缨硝，循環(huán)從根節(jié)點開始遍歷摩钙，直到遍歷到葉子節(jié)點t = null時跳出，或者找到key值相等的節(jié)點t.key= k,則將新value值覆蓋原value值后跳出循環(huán)查辩。
最后：
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
新建一個紅黑樹節(jié)點e胖笛，根據cmp<0或>0來決定將其插入至parent節(jié)點的左邊或者右邊。
插入完成后宜岛，調用fixAfterInsertion()方法來判斷是否需要對整個紅黑樹進行結構調整长踊。
為什么需要結構調整？因為紅黑樹存在是要符合如下要求的：
- 每個節(jié)點都是紅色或黑色谬返。
- 根是黑色的之斯。有時會省略此規(guī)則日杈。由于根始終可以從紅色變?yōu)楹谏猜粒灰欢ㄏ喾矗虼嗽撘?guī)則對分析幾乎沒有影響莉擒。
- 所有葉子（NIL）都是黑色的酿炸。
- 如果節(jié)點為紅色，則其子節(jié)點均為黑色涨冀。
- 從給定節(jié)點到其任何后代NIL節(jié)點的每條路徑都包含相同數量的黑色節(jié)點填硕。
新插入的節(jié)點默認是黑色的，這樣必然會違反第5條原則鹿鳖，故必須通過fixAfterInsertion()來調整扁眯。讓我們看一下TreeMap中的精髓之一操作紅黑樹的fixAfterInsertion()方法：
直接看代碼肯定不容易理解，特別是結合了紅黑樹的左旋翅帜、右旋操作更是容易看暈姻檀，所以此處我們還是對著圖片講解，以圖(a)中新插入了一個6號節(jié)點為例涝滴，對著代碼看一下紅黑樹調整的過程绣版。
通過代碼我們能夠看到，情況2其實是落在情況3內的歼疮。情況4～情況6跟前三種情況是對稱的杂抽，因此圖解中并沒有畫出后三種情況，讀者可以參考代碼自行理解韩脏。
到此缩麸，我們TreeMap中put()方法的源碼就已經分析完成了，紅黑樹的部分關鍵在于看圖理解赡矢，之后再看代碼就很清楚了看完文章覺得不錯親盆好友們杭朱，麻煩動動小手愚屁，點個??哦，謝謝
