TreeMap是一種通過實現(xiàn)了紅黑樹數據結構的Map集合溜腐。
【圖片有英文注釋的均摘抄于國外文章】
首先伏穆，先來看一些基礎概念窥妇。
1. 二叉排序樹
二叉排序樹的定義和性質：
（1）若左子樹不空就谜，則左子樹上所有結點的值均小于或等于它的根結點的值怪蔑；
（2）若右子樹不空，則右子樹上所有結點的值均大于或等于它的根結點的值丧荐；
（3）左缆瓣、右子樹也分別為二叉排序樹；
【摘自百度百科】
.
如下圖是一個普通的二叉樹結構：
上圖是相應的根據值比較生成的一個簡單的二叉樹虹统，那么對應查找就非常簡單弓坞，不斷通過比較節(jié)點的值，大于就向右子樹走车荔，小于就往左子樹走渡冻，相同則返回當前值.
對應插入就可以類似查找，先查到當前值于節(jié)點比較忧便，如果找到族吻，直接更新，沒有找到就不斷往子節(jié)點尋找，直到到達為空的子節(jié)點呼奢，將值填入到該空節(jié)點上宜雀。
二叉樹查找的時候，查找的效率和樹的形狀有關握础，當節(jié)點完全平衡時（最底層子節(jié)點到根節(jié)點的“路程”相同）辐董，效率最高；當所有節(jié)點都只有一個子節(jié)點時禀综，效率最差
2. B樹
B-樹是一種多路搜索樹（并不一定是二叉的）
如下圖简烘，節(jié)點內有多個值（多路）：
上圖展示的最多只有兩個三個子節(jié)點的B樹，這種簡單結構的樹可以稱為2-3樹定枷，這里點到為止孤澎，后續(xù)將通過這種樹去分析后續(xù)的紅黑樹
3. 2-3樹
2-3樹允許每個節(jié)點保存1個或2個值，含有1個值節(jié)點稱為2-node（有兩個子節(jié)點）欠窒，含有2個值的節(jié)點稱為3-node（有三個子節(jié)點）覆旭。
如圖：
在2-3樹中查找，與二叉樹類似岖妄，通過不斷和節(jié)點比較進行向下查找型将，需要注意的是，在3-node節(jié)點中荐虐，需要同時比較兩個值七兜，如果介于兩個值之間，需要找的子節(jié)點就是中間的子節(jié)點福扬。
這里重點討論一下插入操作腕铸，首先看一種簡單的，往2-node節(jié)點插入铛碑；如果找到的末節(jié)點是一個2-node的節(jié)點狠裹，直接在此節(jié)點上新增當前值，將其節(jié)點變成3-node節(jié)點亚茬，如圖：
當插入的節(jié)點是3-node節(jié)點時酪耳，應該怎么操作？首先看一下一個最簡單的刹缝，只有一個3-node節(jié)點的樹：
首先，將值插入到當前的3-node節(jié)點颈将，將其變成4-node節(jié)點梢夯，然后提取中間的值，讓其分解為一個普通的二叉樹即可晴圾。
那么如果當前插入的3-node節(jié)點有父節(jié)點時應該怎么處理呢颂砸，首先還是將3-node變成4-node節(jié)點，然后拆解出一個父節(jié)點插入到原來的父節(jié)點中，如果當前父節(jié)點是2-node節(jié)點人乓，那么將其變成3-node節(jié)點勤篮，如果原來父節(jié)點已經是3-node節(jié)點，那么循環(huán)上面的處理步驟色罚。
總結一下步驟：
- 查找需要插入值的位置
- 判斷當前插入節(jié)點是否是2-node節(jié)點碰缔，如果是，則將其變成3-node節(jié)點戳护，如不是金抡，繼續(xù)執(zhí)行一下步驟
- 將當前節(jié)點變成4-node節(jié)點
4.分解當前4-node節(jié)點，判斷當前節(jié)點是否為根節(jié)點腌且，如果是梗肝，將整個2-3樹，提高一層铺董，如不是巫击，繼續(xù)執(zhí)行一下步驟 - 新增的上層節(jié)點插入到父節(jié)點中，重復執(zhí)行2-4步精续，直到結束
4. 紅黑樹
紅黑樹是一種解決平衡二叉樹的方法喘鸟。紅黑樹具有以下性質：
- 節(jié)點是紅色或黑色。
- 根節(jié)點是黑色驻右。
- 每個葉節(jié)點（NIL節(jié)點什黑，空節(jié)點）是黑色的。
- 每個紅色節(jié)點的兩個子節(jié)點都是黑色堪夭。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)
5.從任一節(jié)點到其每個葉子的所有路徑都包含相同數目的黑色節(jié)點愕把。
【摘自百度百科】
紅黑樹其實是2-3樹的一種二叉樹表現(xiàn)方法，如果將紅線連接線水平連接森爽，那么連接的兩個節(jié)點就是2-3樹中的3-node節(jié)點恨豁，其他沒有紅線連接的就是2-3樹中的2-node節(jié)點，如圖：
在講解插入操作前爬迟，先了解集中紅黑樹的平衡操作橘蜜。第一種是左旋轉和右旋轉：
第二種是顏色反轉，當出現(xiàn)一個節(jié)點下的兩個節(jié)點均是紅色時付呕，可以轉換到2-3樹中思考计福，這是一個4-node節(jié)點，那么需要將其分解為一個二叉樹徽职，并向上合并：
有了2-3樹的插入講解象颖，這邊，直接分析最復雜的紅黑樹插入：
- 查找需要插入值的位置
- 新插入的節(jié)點元素用紅色標識（2-3樹中插入到2-node節(jié)點姆钉，將其變成3-node節(jié)點）
- 如果出現(xiàn)節(jié)點下的兩個子節(jié)點都是紅色時（4-node節(jié)點）,需要進行顏色轉換（或旋轉）
選取紅黑樹比完全平衡二叉樹的好處就是说订，紅黑樹是一種代價較小就可以實現(xiàn)較平衡的二叉樹的結構抄瓦，最差的情況也就是比完全二叉樹的深度多一倍，但是在刪除操作的平衡里面可以節(jié)省很多的效率陶冷。
5. TreeMap
通過分析二叉樹和紅黑樹的概念钙姊，再來看源碼，首先看TreeMap的容器：
private transient Entry<K,V> root = null;
其中埂伦，TreeMap重寫了Entry類：
K key;
V value;
Entry<K,V> left = null;
Entry<K,V> right = null;
Entry<K,V> parent;
其中key value是為了實現(xiàn)Map的鍵值結構煞额，left、right赤屋、parent表示的是二叉樹中一個節(jié)點與其他節(jié)點的關系指針立镶。
TreeMap提供了節(jié)點值比較的接口：
private final Comparator<? super K> comparator;
接下來，看一下put方法：
public V put(K key, V value) {
Entry<K,V> t = root;
... ...
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
... ...
fixAfterInsertion(e);
... ...
}
首先獲取當前的比較器,運用當前比較器作為后續(xù)比較的工具(比較器為空則用默認的,默認的邏輯和有比較器的類似,不重復分析).然后小于类早，則跳到左邊的節(jié)點繼續(xù)比較媚媒，如果大于則在右邊子節(jié)點比較，如果相同涩僻，則設置當前值缭召。然后調用fixAfterInsertion平衡紅黑樹操作。
先偷一下懶逆日，里面的平衡源碼就不分析了嵌巷。
