TreeMap是一種通過(guò)實(shí)現(xiàn)了紅黑樹(shù)數(shù)據(jù)結(jié)構(gòu)的Map集合。
【圖片有英文注釋的均摘抄于國(guó)外文章】
首先，先來(lái)看一些基礎(chǔ)概念。
1. 二叉排序樹(shù)
二叉排序樹(shù)的定義和性質(zhì)：
（1）若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于或等于它的根結(jié)點(diǎn)的值；
（2）若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值；
（3）左、右子樹(shù)也分別為二叉排序樹(shù)；
【摘自百度百科】
.
如下圖是一個(gè)普通的二叉樹(shù)結(jié)構(gòu)：
上圖是相應(yīng)的根據(jù)值比較生成的一個(gè)簡(jiǎn)單的二叉樹(shù)，那么對(duì)應(yīng)查找就非常簡(jiǎn)單，不斷通過(guò)比較節(jié)點(diǎn)的值，大于就向右子樹(shù)走，小于就往左子樹(shù)走，相同則返回當(dāng)前值.
對(duì)應(yīng)插入就可以類(lèi)似查找，先查到當(dāng)前值于節(jié)點(diǎn)比較，如果找到，直接更新，沒(méi)有找到就不斷往子節(jié)點(diǎn)尋找，直到到達(dá)為空的子節(jié)點(diǎn)，將值填入到該空節(jié)點(diǎn)上。
二叉樹(shù)查找的時(shí)候，查找的效率和樹(shù)的形狀有關(guān)，當(dāng)節(jié)點(diǎn)完全平衡時(shí)（最底層子節(jié)點(diǎn)到根節(jié)點(diǎn)的“路程”相同），效率最高；當(dāng)所有節(jié)點(diǎn)都只有一個(gè)子節(jié)點(diǎn)時(shí)，效率最差
2. B樹(shù)
B-樹(shù)是一種多路搜索樹(shù)（并不一定是二叉的）
如下圖，節(jié)點(diǎn)內(nèi)有多個(gè)值（多路）：
上圖展示的最多只有兩個(gè)三個(gè)子節(jié)點(diǎn)的B樹(shù)，這種簡(jiǎn)單結(jié)構(gòu)的樹(shù)可以稱(chēng)為2-3樹(shù)，這里點(diǎn)到為止，后續(xù)將通過(guò)這種樹(shù)去分析后續(xù)的紅黑樹(shù)
3. 2-3樹(shù)
2-3樹(shù)允許每個(gè)節(jié)點(diǎn)保存1個(gè)或2個(gè)值，含有1個(gè)值節(jié)點(diǎn)稱(chēng)為2-node（有兩個(gè)子節(jié)點(diǎn)），含有2個(gè)值的節(jié)點(diǎn)稱(chēng)為3-node（有三個(gè)子節(jié)點(diǎn)）。
如圖：
在2-3樹(shù)中查找，與二叉樹(shù)類(lèi)似，通過(guò)不斷和節(jié)點(diǎn)比較進(jìn)行向下查找，需要注意的是，在3-node節(jié)點(diǎn)中，需要同時(shí)比較兩個(gè)值，如果介于兩個(gè)值之間，需要找的子節(jié)點(diǎn)就是中間的子節(jié)點(diǎn)。
這里重點(diǎn)討論一下插入操作，首先看一種簡(jiǎn)單的，往2-node節(jié)點(diǎn)插入；如果找到的末節(jié)點(diǎn)是一個(gè)2-node的節(jié)點(diǎn)，直接在此節(jié)點(diǎn)上新增當(dāng)前值，將其節(jié)點(diǎn)變成3-node節(jié)點(diǎn)，如圖：
當(dāng)插入的節(jié)點(diǎn)是3-node節(jié)點(diǎn)時(shí)，應(yīng)該怎么操作？首先看一下一個(gè)最簡(jiǎn)單的，只有一個(gè)3-node節(jié)點(diǎn)的樹(shù)：
首先，將值插入到當(dāng)前的3-node節(jié)點(diǎn)，將其變成4-node節(jié)點(diǎn)，然后提取中間的值，讓其分解為一個(gè)普通的二叉樹(shù)即可。
那么如果當(dāng)前插入的3-node節(jié)點(diǎn)有父節(jié)點(diǎn)時(shí)應(yīng)該怎么處理呢，首先還是將3-node變成4-node節(jié)點(diǎn)，然后拆解出一個(gè)父節(jié)點(diǎn)插入到原來(lái)的父節(jié)點(diǎn)中，如果當(dāng)前父節(jié)點(diǎn)是2-node節(jié)點(diǎn)，那么將其變成3-node節(jié)點(diǎn)，如果原來(lái)父節(jié)點(diǎn)已經(jīng)是3-node節(jié)點(diǎn)，那么循環(huán)上面的處理步驟。
總結(jié)一下步驟：
- 查找需要插入值的位置
- 判斷當(dāng)前插入節(jié)點(diǎn)是否是2-node節(jié)點(diǎn)，如果是，則將其變成3-node節(jié)點(diǎn)，如不是，繼續(xù)執(zhí)行一下步驟
- 將當(dāng)前節(jié)點(diǎn)變成4-node節(jié)點(diǎn)
4.分解當(dāng)前4-node節(jié)點(diǎn)，判斷當(dāng)前節(jié)點(diǎn)是否為根節(jié)點(diǎn)，如果是，將整個(gè)2-3樹(shù)，提高一層，如不是，繼續(xù)執(zhí)行一下步驟 - 新增的上層節(jié)點(diǎn)插入到父節(jié)點(diǎn)中，重復(fù)執(zhí)行2-4步，直到結(jié)束
4. 紅黑樹(shù)
紅黑樹(shù)是一種解決平衡二叉樹(shù)的方法。紅黑樹(shù)具有以下性質(zhì)：
- 節(jié)點(diǎn)是紅色或黑色。
- 根節(jié)點(diǎn)是黑色。
- 每個(gè)葉節(jié)點(diǎn)（NIL節(jié)點(diǎn)，空節(jié)點(diǎn)）是黑色的。
- 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))
5.從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
【摘自百度百科】
紅黑樹(shù)其實(shí)是2-3樹(shù)的一種二叉樹(shù)表現(xiàn)方法，如果將紅線連接線水平連接，那么連接的兩個(gè)節(jié)點(diǎn)就是2-3樹(shù)中的3-node節(jié)點(diǎn)，其他沒(méi)有紅線連接的就是2-3樹(shù)中的2-node節(jié)點(diǎn)，如圖：
在講解插入操作前，先了解集中紅黑樹(shù)的平衡操作。第一種是左旋轉(zhuǎn)和右旋轉(zhuǎn)：
第二種是顏色反轉(zhuǎn)，當(dāng)出現(xiàn)一個(gè)節(jié)點(diǎn)下的兩個(gè)節(jié)點(diǎn)均是紅色時(shí)，可以轉(zhuǎn)換到2-3樹(shù)中思考，這是一個(gè)4-node節(jié)點(diǎn)，那么需要將其分解為一個(gè)二叉樹(shù)，并向上合并：
有了2-3樹(shù)的插入講解，這邊，直接分析最復(fù)雜的紅黑樹(shù)插入：
- 查找需要插入值的位置
- 新插入的節(jié)點(diǎn)元素用紅色標(biāo)識(shí)（2-3樹(shù)中插入到2-node節(jié)點(diǎn)，將其變成3-node節(jié)點(diǎn)）
- 如果出現(xiàn)節(jié)點(diǎn)下的兩個(gè)子節(jié)點(diǎn)都是紅色時(shí)（4-node節(jié)點(diǎn)）,需要進(jìn)行顏色轉(zhuǎn)換（或旋轉(zhuǎn)）
選取紅黑樹(shù)比完全平衡二叉樹(shù)的好處就是，紅黑樹(shù)是一種代價(jià)較小就可以實(shí)現(xiàn)較平衡的二叉樹(shù)的結(jié)構(gòu)，最差的情況也就是比完全二叉樹(shù)的深度多一倍，但是在刪除操作的平衡里面可以節(jié)省很多的效率。
5. TreeMap
通過(guò)分析二叉樹(shù)和紅黑樹(shù)的概念，再來(lái)看源碼，首先看TreeMap的容器：
private transient Entry<K,V> root = null;
其中，TreeMap重寫(xiě)了Entry類(lèi)：
K key;
V value;
Entry<K,V> left = null;
Entry<K,V> right = null;
Entry<K,V> parent;
其中key value是為了實(shí)現(xiàn)Map的鍵值結(jié)構(gòu)，left、right、parent表示的是二叉樹(shù)中一個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)的關(guān)系指針。
TreeMap提供了節(jié)點(diǎn)值比較的接口：
private final Comparator<? super K> comparator;
接下來(lái)，看一下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);
... ...
}
首先獲取當(dāng)前的比較器,運(yùn)用當(dāng)前比較器作為后續(xù)比較的工具(比較器為空則用默認(rèn)的,默認(rèn)的邏輯和有比較器的類(lèi)似,不重復(fù)分析).然后小于，則跳到左邊的節(jié)點(diǎn)繼續(xù)比較，如果大于則在右邊子節(jié)點(diǎn)比較，如果相同，則設(shè)置當(dāng)前值。然后調(diào)用fixAfterInsertion平衡紅黑樹(shù)操作。
先偷一下懶，里面的平衡源碼就不分析了。
