文章目錄`

一 樹的概念與應(yīng)用場(chǎng)景

1.1 二叉查找樹

1.2 AVL樹

1.3 紅黑樹

1.4 B樹

二 樹的操作與源碼實(shí)現(xiàn)

2.1 TreeMap/TreeSet實(shí)現(xiàn)原理

寫在前面 

之前在網(wǎng)上看到過很多關(guān)于Java集合框架實(shí)現(xiàn)原理文章，但大都在講接口的作用與各類集合的實(shí)現(xiàn)，對(duì)其中數(shù)據(jù)結(jié)構(gòu)的闡述的不多，例如紅黑樹的染色和旋轉(zhuǎn)是怎么進(jìn)行的等等，本篇文章從 數(shù)據(jù)結(jié)構(gòu)的基本原理出發(fā)，逐步去分析Java集合里數(shù)據(jù)結(jié)構(gòu)的應(yīng)用與實(shí)現(xiàn)。

一 樹的概念與應(yīng)用場(chǎng)景

樹是一種抽象數(shù)據(jù)類型（ADT）或是實(shí)作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>0）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把 它叫做“樹”是因?yàn)樗雌饋硐褚豢玫箳斓臉?，也就是說它是根朝上，而葉朝下的。

樹有以下特點(diǎn)：

每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)；
沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)；
每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)；
除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹；
與樹相關(guān)的概念

節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度；
樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度；
葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為零的節(jié)點(diǎn)；
非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為零的節(jié)點(diǎn)；
父親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)；
孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)；
兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)；
節(jié)點(diǎn)的層次：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推；
深度：對(duì)于任意節(jié)點(diǎn)n, n的深度為從根到n的唯一路徑長，根的深度為0；
高度：對(duì)于任意節(jié)點(diǎn)n, n的高度為從n到一片樹葉的最長路徑長，所有樹葉的高度為0；
堂兄弟節(jié)點(diǎn)：父節(jié)點(diǎn)在同一層的節(jié)點(diǎn)互為堂兄弟；
節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；
子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。
森林：由m（m>=0）棵互不相交的樹的集合稱為森林；
注：參照親戚關(guān)系，這些概念很好理解，家族譜也是一種樹結(jié)構(gòu)。:grinning:

樹的分類

無序樹：樹中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間沒有順序關(guān)系，這種樹稱為無序樹，也稱為自由樹；
有序樹：樹中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間有順序關(guān)系，這種樹稱為有序樹；
其中有序樹又分為：

二叉樹：每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子樹的樹稱為二叉樹；
完全二叉樹：對(duì)于一顆二叉樹，假設(shè)其深度為d（d>1）。除了第d層外，其它各層的節(jié)點(diǎn)數(shù)目均已達(dá)最大值，且第d層所有節(jié)點(diǎn)從左向右連續(xù)地緊密排列，這樣的二叉樹被稱為完全二叉樹；
滿二叉樹：所有葉節(jié)點(diǎn)都在最底層的完全二叉樹；
AVL樹：當(dāng)且僅當(dāng)任何節(jié)點(diǎn)的兩棵子樹的高度差不大于1的二叉樹；
二叉查找樹：樹中的每個(gè)節(jié)點(diǎn)，它的左子樹中所有項(xiàng)小于X中的項(xiàng)，它的右子樹中的所有項(xiàng)大于X中的項(xiàng)。
霍夫曼樹：帶權(quán)路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹；
B樹：一種對(duì)讀寫操作進(jìn)行優(yōu)化的自平衡的二叉查找樹，能夠保持?jǐn)?shù)據(jù)有序，擁有多余兩個(gè)子樹。
1.1 二叉查找樹

二叉查找樹是一種有序二叉樹，它的查找、插入的時(shí)間復(fù)雜度為O(logN)

二叉查找是是一種有序二叉樹.

主要特點(diǎn)

若任意節(jié)點(diǎn)的左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值。
若任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值。
任意節(jié)點(diǎn)的左右子樹葉為二叉查找樹
沒有鍵值相等的節(jié)點(diǎn)。
就就是說二叉查找樹上的節(jié)點(diǎn)是排好序的：左子樹 < 根節(jié)點(diǎn) < 右子樹。

性能分析

在最壞的情況下，即當(dāng)先后插入的關(guān)鍵字有序時(shí)，構(gòu)造成的二叉查找樹蛻變?yōu)閱沃?，輸?shù)纳疃葹閚，其平均查找長度為(n+1)/2。
在最好的情況下，二叉查找樹的形態(tài)和折半查找的判定樹相同，其時(shí)間復(fù)雜度為O(log2(N))。
我們來看看二叉查找樹上的相關(guān)操作。

構(gòu)造

當(dāng)我們用一組數(shù)值構(gòu)造一棵二叉查找樹時(shí)，就相當(dāng)于對(duì)這組數(shù)值進(jìn)行了排序，在最壞情況下，即該組數(shù)值是從小到達(dá)排好序的，構(gòu)造出來的二叉樹的所有節(jié)點(diǎn)都 沒有左子樹，這種情況下的時(shí)間復(fù)雜度為O(N2)。（N的平方）

另外，樹排序的問題使得CPU Cache性能較差，特別是當(dāng)節(jié)點(diǎn)是動(dòng)態(tài)內(nèi)存分配時(shí)。而堆排序的CPU Cache性能較好。另一方面，樹排序是最優(yōu)的增量排序（incremental sorting）算法， 保持一個(gè)數(shù)值序列的有序性。

查找

由于二叉查找樹具有左子樹 < 根節(jié)點(diǎn) < 右子樹的特點(diǎn)，因此在二叉查找樹b中查找x的過程如下：

若b是空樹，則查找失敗，否則：
若x等于根節(jié)點(diǎn)的值，則查找成功，否則：
若x小于b根節(jié)點(diǎn)的值，則查找左子樹，否則
若x大于b根節(jié)點(diǎn)的值，則查找右子樹。
整個(gè)流程是一個(gè)遞歸的過程。

插入

插入的過程也是查找的過程，在二叉查找樹中插入節(jié)點(diǎn)x的過程如下：

若b是空樹，則x作為根節(jié)點(diǎn)插入，否則：
若x的值等于根節(jié)點(diǎn)的值，則直接返回，否則：
若x的值小于根節(jié)點(diǎn)的值，則將x插入當(dāng)該根節(jié)點(diǎn)的左子樹中，否則
將x插入該根節(jié)點(diǎn)的右子樹中。
這也是一個(gè)遞歸的過程，這里我們要關(guān)注兩點(diǎn)：

插入的過程也是查找的過程

二叉查找樹不允許有相同值的節(jié)點(diǎn)

刪除

在二叉查找樹上刪除一個(gè)節(jié)點(diǎn)，分為三種情況：

若刪除的是葉子節(jié)點(diǎn)，則不會(huì)破壞樹的結(jié)構(gòu)，只需要修改其雙親節(jié)點(diǎn)的指針即可。
若刪除的節(jié)點(diǎn)只有一個(gè)孩子節(jié)點(diǎn)，則用它的孩子節(jié)點(diǎn)代替它的位置即可，如此也不會(huì)破壞紅黑樹的結(jié)構(gòu)。
若刪除的節(jié)點(diǎn)有兩個(gè)孩子節(jié)點(diǎn)，這種情況復(fù)雜一下，我們通常會(huì)找到要?jiǎng)h除節(jié)點(diǎn)X的左子樹里的最大元素或者右子樹里的最小元素，然后用M替換掉X，再刪除節(jié)點(diǎn)，因?yàn)榇藭r(shí)M最多只會(huì)有一個(gè)
節(jié)點(diǎn)（如果左子樹最大元素則沒有右子節(jié)點(diǎn)，若是右子樹最小元素則沒有左子節(jié)點(diǎn)），若M沒有孩子節(jié)點(diǎn)，直接進(jìn)入情況1處理，若M只有一個(gè)孩子，則直接進(jìn)入情況2處理。
另外，如果刪除的次數(shù)不多，可以采用 懶惰刪除 的方式，即當(dāng)一個(gè)元素刪除時(shí)，它仍然留在樹中，只是被比較為已刪除，這種方式在有重復(fù)項(xiàng)是特別有用， 另外如果刪除的元素又重新插入，這種方式可以避免新單元的創(chuàng)建開銷。

1.2 AVL樹

AVL樹是帶有平衡條件的二叉查找樹。

主要特點(diǎn)

AVL樹中的任何階段的兩棵子樹高度最大差別為1.
AVL樹還有個(gè)平衡因子的概念，平衡因子 = 左子樹高度 - 右子樹高度，因此平衡因子為-1，0，1的為平衡二叉樹，其他的都是不平衡的。

另外，把一棵不平衡的二叉查找樹變成一棵平衡二叉樹，我們稱之為 AVL旋轉(zhuǎn) 。

我們來看看不同情況下AVL旋轉(zhuǎn)如何進(jìn)行。

左左情況：右旋
右右情況：左旋
左右情況：先左旋，再右旋
右左情況：先右旋，再左旋
注：所謂左左指的是左邊的左子樹多了一個(gè)，其他的依此類推。

具體操作如下所示，我們可以看到左左情況和右右情況只需要單旋轉(zhuǎn)就可以完成，左右情況與右左情況需要先把它們變成左左情況與右右情況 再進(jìn)行旋轉(zhuǎn)，因此這兩種情況需要雙旋轉(zhuǎn)才能完成。

性能分析

查找、插入與刪除在平均和最壞的情況下的時(shí)間復(fù)雜度為O(logN)。

AVL樹也是二叉查找樹的一種，它的很多操作都可以向我們上面描述的二叉查找樹的操作那樣進(jìn)行。刪除操作有點(diǎn)例外，我們?cè)谶M(jìn)行刪除操作

時(shí)可以把要?jiǎng)h除的節(jié)點(diǎn)向下旋轉(zhuǎn)形成一個(gè)葉子節(jié)點(diǎn)，然后直接刪除這個(gè)葉子節(jié)點(diǎn)，因?yàn)樾D(zhuǎn)成葉子節(jié)點(diǎn)期間，做多有l(wèi)ogN個(gè)節(jié)點(diǎn)被旋轉(zhuǎn)，每次 AVL旋轉(zhuǎn)花費(fèi)的事件固定，所以刪除操作的時(shí)間復(fù)雜度是O(logN)。

1.3 紅黑樹

紅黑樹是平衡二叉樹的變種，它的操作的時(shí)間復(fù)雜度是O(logN).

紅黑樹是一種具有著色性質(zhì)的樹，具有以下特點(diǎn)：

每個(gè)節(jié)點(diǎn)被著成紅色或者黑色
根是黑色的
葉子節(jié)點(diǎn)都是黑色的，葉子節(jié)點(diǎn)指的是NULL節(jié)點(diǎn)，有些紅黑樹圖中可能沒有標(biāo)記出來。
如果一個(gè)節(jié)點(diǎn)是紅色的，那么他額子節(jié)點(diǎn)必須是黑色的，也就是不會(huì)存在兩個(gè)紅色節(jié)點(diǎn)毗鄰。
從一個(gè)節(jié)點(diǎn)到一個(gè)葉子節(jié)點(diǎn)（NULL節(jié)點(diǎn)）的每一條路徑必須包含相同數(shù)目的黑色節(jié)點(diǎn)。
紅黑樹也是一種二叉查找樹，查找操作與二叉查找樹相同，插入與刪除操作有所不同。

1.4 B樹

B樹是一種自平衡的樹，能夠保持?jǐn)?shù)據(jù)有序，B樹為系統(tǒng)大塊數(shù)據(jù)的讀寫操作做了優(yōu)化，通常用在數(shù)據(jù)庫與文件系統(tǒng)的實(shí)現(xiàn)上。

我們前面講解了二叉查找樹、AVL樹，紅黑樹，這三種都是典型的二叉查找樹結(jié)構(gòu)，其查找的事件復(fù)雜度O(logN)與樹的深度有關(guān)，考慮這么一種情況，如果有 大量的數(shù)據(jù)，而節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)有限，這種情況下，我們只能去擴(kuò)充樹的深度，就會(huì)導(dǎo)致查找效率低下。

怎么解決這種問題，一個(gè)簡(jiǎn)單的想法就是：二叉變多叉。

這里我們想象一下常見的文件系統(tǒng)，它也是一種樹結(jié)構(gòu)，在查找文件時(shí)，樹的深度就決定了查找的效率。因此B樹就是為了減少數(shù)的深度從而提高查找效率的一種 數(shù)據(jù)結(jié)構(gòu)。

主要特點(diǎn)

一個(gè)階為M的B樹具有以下特點(diǎn)：

注：M階指的是M叉查找樹，例如M = 2，則為二叉查找樹。

數(shù)據(jù)項(xiàng)存儲(chǔ)在樹葉上
非葉節(jié)點(diǎn)存儲(chǔ)直到M-1個(gè)關(guān)鍵字以指示搜索方向：關(guān)鍵字代表子樹i+1中最小的關(guān)鍵字
樹的根或者是一片樹葉，或者其兒子數(shù)都在2和M之間。
除根外，所有非樹葉節(jié)點(diǎn)的兒子樹在M/2與M之間。
所有的樹葉都在相同的深度上擁有的數(shù)據(jù)項(xiàng)都在L/2與L之間。
性能分析

B樹在查找、插入以及刪除等操作中，時(shí)間復(fù)雜度為O(logN)。

二 樹的操作與源碼實(shí)現(xiàn)

在文章 01Java關(guān)于數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)：表、棧與隊(duì)列 中我們 討論了ArrayList與LinkedList的實(shí)現(xiàn)，它們的瓶頸在于查找效率低下。因而Java集合設(shè)計(jì)了Set與Map接口，它們?cè)诓迦?、刪除與查找等基本操作都有良好的表現(xiàn)。

2.1 TreeMap/TreeSet實(shí)現(xiàn)原理

TreeSet實(shí)際上是基于TreeMap的NavigableSet的實(shí)現(xiàn)，它在功能上完全依賴于TreeMap，TreeMap是一個(gè)基于紅黑樹實(shí)現(xiàn)的Map，它在存儲(chǔ)時(shí)對(duì)元素進(jìn)行排序。

因此只要理解了TreeMap實(shí)現(xiàn)即可，TreeSet在功能上完全依賴于TreeMap。

TreeMap具有以下特點(diǎn)：

TreeMap是一個(gè)有序的key-value集合，基于紅黑樹實(shí)現(xiàn)。
沒有實(shí)現(xiàn)同步
TreeMap實(shí)現(xiàn)以下接口：

NavigableMap：支持一系列導(dǎo)航方法，比如返回有序的key集合。
Cloneable：可以被克隆。
Serializable：支持序列化。
成員變量

//比較器 
private final Comparator<? super K> comparator;  
//根節(jié)點(diǎn) 
private transient TreeMapEntry<K,V> root = null;  
//集合大小 
private transient int size = 0;  
//修改次數(shù) 
private transient int modCount = 0; 

構(gòu)造方法

 

public TreeMap() {  
//默認(rèn)比較器 
comparator = null; 
} 
 
public TreeMap(Comparator<? super K> comparator) {  
//指定比較器 
this.comparator = comparator; 
} 
 
 
public TreeMap(Map<? extends K, ? extends V> m) {  
//默認(rèn)比較器 
comparator = null; 
putAll(m); 
} 
 
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) { 
} 
} 

內(nèi)部類

TreeMap里面定義了靜態(tài)內(nèi)部類TreeMapEntry來描述節(jié)點(diǎn)信息。

 

static final class TreeMapEntry<K,V> implements Map.Entry<K,V> { 
//鍵 
K key; 
//值 
V value; 
//指向左子樹的引用 
TreeMapEntry<K,V> left = null; 
//指向右子樹的引用 
TreeMapEntry<K,V> right = null; 
//指向父節(jié)點(diǎn)的引用 
TreeMapEntry<K,V> parent; 
//節(jié)點(diǎn)顏色，默認(rèn)為黑色 
boolean color = BLACK; 
 
/** 
* Make a new cell with given key, value, and parent, and with 
* {@code null} child links, and BLACK color. 
*/ 
TreeMapEntry(K key, V value, TreeMapEntry<K,V> parent) { 
this.key = key; 
this.value = value; 
this.parent = parent; 
} 
 
/** 
* Returns the key. 
* 
* @return the key 
*/ 
public K getKey() { 
return key; 
} 
 
/** 
* Returns the value associated with the key. 
* 
* @return the value associated with the key 
*/ 
public V getValue() { 
return value; 
} 
 
/** 
* Replaces the value currently associated with the key with the given 
* value. 
* 
* @return the value associated with the key before this method was 
* called 
*/ 
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; 
} 
} 

操作方法

在正式介紹TreeMap里的增、刪、改、查操作之前，我們先來看看TreeMop里關(guān)于節(jié)點(diǎn)染色，樹的旋轉(zhuǎn)等操作的實(shí)現(xiàn)，它們是TreeMap實(shí)現(xiàn)的基礎(chǔ)。

節(jié)點(diǎn)染色

在介紹染色規(guī)則之前，我們先來回顧一下紅黑樹的特點(diǎn)：

每個(gè)節(jié)點(diǎn)被著成紅色或者黑色
根是黑色的
葉子節(jié)點(diǎn)都是黑色的，葉子節(jié)點(diǎn)指的是NULL節(jié)點(diǎn)，有些紅黑樹圖中可能沒有標(biāo)記出來。
如果一個(gè)節(jié)點(diǎn)是紅色的，那么他額子節(jié)點(diǎn)必須是黑色的，也就是不會(huì)存在兩個(gè)紅色節(jié)點(diǎn)毗鄰。
從一個(gè)節(jié)點(diǎn)到一個(gè)葉子節(jié)點(diǎn)（NULL節(jié)點(diǎn)）的每一條路徑必須包含相同數(shù)目的黑色節(jié)點(diǎn)。
關(guān)于節(jié)點(diǎn)染色，我們有多種情況需要考慮。

首先說明

若新節(jié)點(diǎn)位于樹的根上，沒有父節(jié)點(diǎn)，直接將其染成黑色即可。這個(gè)在代碼中無需操作，因?yàn)楣?jié)點(diǎn)默認(rèn)就是黑色的。
若新節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色，這個(gè)時(shí)候樹依然滿足紅黑樹的性質(zhì)，并不需要額外的處理。
以上兩種情況無需額外的處理，我們?cè)賮砜紤]需要處理的情況。

情況1：如果新節(jié)點(diǎn)N的父節(jié)點(diǎn)P是紅色，且其叔父節(jié)點(diǎn)U也為紅色，我們可以將父節(jié)點(diǎn)P與叔父節(jié)點(diǎn)U染成黑色，祖父節(jié)點(diǎn)G染成紅色。
情況2：如果新節(jié)點(diǎn)N的父節(jié)點(diǎn)P是紅色，且其叔父節(jié)點(diǎn)U為黑色或者沒有叔父節(jié)點(diǎn)，P為其父節(jié)點(diǎn)P的右子節(jié)點(diǎn)，P為為其父節(jié)點(diǎn)G的左子節(jié)點(diǎn)。這種情況我們針對(duì)祖父節(jié)點(diǎn)G做一次右旋。并將P染成黑色，染成紅色
情況3：如果新節(jié)點(diǎn)N的父節(jié)點(diǎn)P是紅色，且其叔父節(jié)點(diǎn)U為黑色或者沒有叔父節(jié)點(diǎn)，P為其父節(jié)點(diǎn)P的右子節(jié)點(diǎn)，P為為其父節(jié)點(diǎn)G的左子節(jié)點(diǎn)。這種情況下我們對(duì)做一次左旋調(diào)換，調(diào)換P與N的位置，這樣情況3變成了 情況2，剩下的按照情況2處理即可。
我們來看看具體的源碼實(shí)現(xiàn)。

 

public class TreeMap<K,V>  
extends AbstractMap<K,V> 
implements NavigableMap<K,V>, Cloneable, java.io.Serializable{ 
 
//染色 
private void fixAfterInsertion(TreeMapEntry<K,V> x) { 
x.color = RED; 
 
while (x != null && x != root && x.parent.color == RED) { 
 
//新節(jié)點(diǎn)N（即x）在其祖父節(jié)點(diǎn)的左子樹上，叔父節(jié)點(diǎn)在左子樹上。 
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { 
TreeMapEntry<K,V> y = rightOf(parentOf(parentOf(x))); 
//情況1：如果新節(jié)點(diǎn)N的父節(jié)點(diǎn)P是紅色，且其叔父節(jié)點(diǎn)U也為紅色，我們可以將父節(jié)點(diǎn)P與叔父節(jié)點(diǎn)U染成黑色，祖父節(jié)點(diǎn)G染成紅色。 
if (colorOf(y) == RED) { 
setColor(parentOf(x), BLACK); 
setColor(y, BLACK); 
setColor(parentOf(parentOf(x)), RED); 
x = parentOf(parentOf(x)); 
}  
//情況2：如果新節(jié)點(diǎn)N的父節(jié)點(diǎn)P是紅色，且其叔父節(jié)點(diǎn)U為黑色或者沒有叔父節(jié)點(diǎn)，P為其父節(jié)點(diǎn)P的右子節(jié)點(diǎn)，P為為其父節(jié)點(diǎn)G的左 
//子節(jié)點(diǎn)。這種情況我們針對(duì)祖父節(jié)點(diǎn)G做一次右旋。并將P染成黑色，染成紅色 
else { 
//情況3：x為其父節(jié)點(diǎn)的右子節(jié)點(diǎn)，先對(duì)其父節(jié)點(diǎn)進(jìn)行左旋，調(diào)換兩者的位置 
if (x == rightOf(parentOf(x))) { 
x = parentOf(x); 
rotateLeft(x); 
} 
setColor(parentOf(x), BLACK); 
setColor(parentOf(parentOf(x)), RED); 
rotateRight(parentOf(parentOf(x))); 
} 
}  
//情況1：新節(jié)點(diǎn)N（即x）在其祖父節(jié)點(diǎn)的右子樹上，叔父節(jié)點(diǎn)在左子樹上，這種情況和在右子節(jié)點(diǎn)的情況相似，知識(shí)旋轉(zhuǎn)方向相反罷了。 
else { 
TreeMapEntry<K,V> y = leftOf(parentOf(parentOf(x))); 
//如果新節(jié)點(diǎn)N的父節(jié)點(diǎn)P是紅色，且其叔父節(jié)點(diǎn)U也為紅色，我們可以將父節(jié)點(diǎn)P與叔父節(jié)點(diǎn)U染成黑色，祖父節(jié)點(diǎn)G染成紅色。 
if (colorOf(y) == RED) { 
setColor(parentOf(x), BLACK); 
setColor(y, BLACK); 
setColor(parentOf(parentOf(x)), RED); 
x = parentOf(parentOf(x)); 
}  
//情況2：如果新節(jié)點(diǎn)N的父節(jié)點(diǎn)P是紅色，且其叔父節(jié)點(diǎn)U為黑色或者沒有叔父節(jié)點(diǎn)，P為其父節(jié)點(diǎn)P的右子節(jié)點(diǎn)，P為為其父節(jié)點(diǎn)G的左 
//子節(jié)點(diǎn)。這種情況我們針對(duì)祖父節(jié)點(diǎn)G做一次右旋。并將P染成黑色，染成紅色 
else { 
//情況3：x為其父節(jié)點(diǎn)的左子節(jié)點(diǎn)，先對(duì)其父節(jié)點(diǎn)進(jìn)行右旋，調(diào)換兩者位置。 
if (x == leftOf(parentOf(x))) { 
x = parentOf(x); 
rotateRight(x); 
} 
setColor(parentOf(x), BLACK); 
setColor(parentOf(parentOf(x)), RED); 
rotateLeft(parentOf(parentOf(x))); 
} 
} 
} 
root.color = BLACK; 
} 
} 

節(jié)點(diǎn)旋轉(zhuǎn)

左旋

之前在網(wǎng)上看到一組關(guān)于左旋、右旋的動(dòng)態(tài)圖，很形象，這里也貼出來。

找到要旋轉(zhuǎn)節(jié)點(diǎn)p的右節(jié)點(diǎn)r，然后將r的左子節(jié)點(diǎn)賦值給p的右子節(jié)點(diǎn)，如果r的左子節(jié)點(diǎn)為空，則直接將r節(jié)點(diǎn)設(shè)置為P的父節(jié)點(diǎn)。
將原來p的父節(jié)點(diǎn)設(shè)置成r的父節(jié)點(diǎn)，如果原來p的父節(jié)點(diǎn)為空，則直接接r設(shè)置成根節(jié)點(diǎn)，如果根節(jié)點(diǎn)不空且其做子節(jié)點(diǎn)為p，則將r設(shè)置為新的左子節(jié)點(diǎn)，如果根節(jié)點(diǎn)不空且其右子節(jié)點(diǎn)為p，則將r設(shè)置為新的右子節(jié)點(diǎn)，
再講r的左子節(jié)點(diǎn)設(shè)為p，p的父節(jié)點(diǎn)設(shè)置為r，左旋完成。
右旋

找到要旋轉(zhuǎn)節(jié)點(diǎn)p的左子節(jié)點(diǎn)l，然后將l的右子節(jié)點(diǎn)賦值給p的左子節(jié)點(diǎn)，如果l的右子節(jié)點(diǎn)為空，則直接將l節(jié)點(diǎn)設(shè)置為P的父節(jié)點(diǎn)。
將原來p的父節(jié)點(diǎn)設(shè)置成l的父節(jié)點(diǎn)，如果原來p的父節(jié)點(diǎn)為空，則直接接l設(shè)置成根節(jié)點(diǎn)，如果根節(jié)點(diǎn)不空且其做子節(jié)點(diǎn)為p，則將l設(shè)置為新的左子節(jié)點(diǎn)，如果根節(jié)點(diǎn)不空且其右子節(jié)點(diǎn)為p，則將l設(shè)置為新的右子節(jié)點(diǎn)，
再講l的右子節(jié)點(diǎn)設(shè)為p，p的父節(jié)點(diǎn)設(shè)置為l，右旋完成。
我們來看看具體的源碼實(shí)現(xiàn)。

 

public class TreeMap<K,V>  
extends AbstractMap<K,V> 
implements NavigableMap<K,V>, Cloneable, java.io.Serializable{ 
 
//左旋 
private void rotateLeft(TreeMapEntry<K,V> p) { 
if (p != null) { 
//找到要旋轉(zhuǎn)節(jié)點(diǎn)p的右節(jié)點(diǎn)r 
TreeMapEntry<K,V> r = p.right; 
//然后將r的左子節(jié)點(diǎn)賦值給p的右子節(jié)點(diǎn) 
p.right = r.left; 
//如果r的左子節(jié)點(diǎn)為空，則直接將r節(jié)點(diǎn)設(shè)置為P的父節(jié)點(diǎn) 
if (r.left != null) 
r.left.parent = p; 
//將原來p的父節(jié)點(diǎn)設(shè)置成r的父節(jié)點(diǎn) 
r.parent = p.parent; 
//如果原來p的父節(jié)點(diǎn)為空，則直接接r設(shè)置成根節(jié)點(diǎn) 
if (p.parent == null) 
rroot = r; 
//如果根節(jié)點(diǎn)不空且其做子節(jié)點(diǎn)為p，則將r設(shè)置為新的左子節(jié)點(diǎn) 
else if (p.parent.left == p) 
p.parent.left = r; 
//如果根節(jié)點(diǎn)不空且其右子節(jié)點(diǎn)為p，則將r設(shè)置為新的右子節(jié)點(diǎn)  
else 
p.parent.right = r; 
//再講r的左子節(jié)點(diǎn)設(shè)為p，p的父節(jié)點(diǎn)設(shè)置為r，左旋完成 
r.left = p; 
p.parent = r; 
} 
} 
 
//右旋 
private void rotateRight(TreeMapEntry<K,V> p) { 
if (p != null) { 
//找到要旋轉(zhuǎn)節(jié)點(diǎn)p的左子節(jié)點(diǎn)l 
TreeMapEntry<K,V> l = p.left; 
//然后將l的右子節(jié)點(diǎn)賦值給p的左子節(jié)點(diǎn) 
p.left = l.right; 
//如果l的右子節(jié)點(diǎn)為空，則直接將l節(jié)點(diǎn)設(shè)置為P的父節(jié)點(diǎn) 
if (l.right != null) l.right.parent = p; 
//將原來p的父節(jié)點(diǎn)設(shè)置成l的父節(jié)點(diǎn) 
l.parent = p.parent; 
//如果原來p的父節(jié)點(diǎn)為空，則直接接l設(shè)置成根節(jié) 
if (p.parent == null) 
root = l; 
//如果根節(jié)點(diǎn)不空且其右子節(jié)點(diǎn)為p，則將l設(shè)置為新的右子節(jié)點(diǎn) 
else if (p.parent.right == p) 
p.parent.right = l; 
//如果根節(jié)點(diǎn)不空且其做子節(jié)點(diǎn)為p，則將l設(shè)置為新的左子節(jié)點(diǎn) 
else p.parent.left = l; 
//再講l的右子節(jié)點(diǎn)設(shè)為p，p的父節(jié)點(diǎn)設(shè)置為l，右旋完成。 
l.right = p; 
p.parent = l; 
} 
} 
} 
put 
 
public class TreeMap<K,V>  
extends AbstractMap<K,V> 
implements NavigableMap<K,V>, Cloneable, java.io.Serializable{ 
 
public V put(K key, V value) { 
//找到根節(jié)點(diǎn) 
TreeMapEntry<K,V> t = root; 
//如果根節(jié)點(diǎn)為空，則設(shè)置該元素為 
if (t == null) { 
if (comparator != null) { 
if (key == null) { 
comparator.compare(key, key); 
} 
} else { 
if (key == null) { 
throw new NullPointerException("key == null"); 
} else if (!(key instanceof Comparable)) { 
throw new ClassCastException( 
"Cannot cast" + key.getClass().getName() + " to Comparable."); 
} 
} 
 
root = new TreeMapEntry<>(key, value, null); 
//集合大小為1 
size = 1; 
//修改次數(shù)自增 
modCount++; 
return null; 
} 
int cmp; 
TreeMapEntry<K,V> parent; 
//獲取比較器 
Comparator<? super K> cpr = comparator; 
//如果比較器不空，則用指定的比較器進(jìn)行比較 
if (cpr != null) { 
//循環(huán)遞歸，從根節(jié)點(diǎn)開始查找插入的位置，即查找的它的父節(jié)點(diǎn)，查找方式和我們上面講的二叉排序樹的查找方式相同 
do { 
parent = t; 
cmp = cpr.compare(key, t.key); 
//插入值小于當(dāng)前節(jié)點(diǎn)，則繼續(xù)在左子樹上查詢 
if (cmp < 0) 
tt = t.left; 
//插入值大于當(dāng)前節(jié)點(diǎn)，則繼續(xù)在右子樹上查詢 
else if (cmp > 0) 
tt = t.right; 
//如果相等，則替換當(dāng)前的值 
else 
return t.setValue(value); 
} while (t != null); 
} 
//如果比較器為坤寧宮，則使用默認(rèn)的比較器 
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) 
tt = t.left; 
else if (cmp > 0) 
tt = t.right; 
else 
return t.setValue(value); 
} while (t != null); 
} 
//根據(jù)查找到的父節(jié)點(diǎn)，構(gòu)造節(jié)點(diǎn)，并根據(jù)比結(jié)果將其插入到對(duì)應(yīng)的位置 
TreeMapEntry<K,V> e = new TreeMapEntry<>(key, value, parent); 
if (cmp < 0) 
parent.left = e; 
else 
parent.right = e; 
//給插入的節(jié)點(diǎn)染色 
fixAfterInsertion(e); 
size++; 
modCount++; 
return null; 
} 
} 

插入操作采用了二叉排序樹的查找算法，整個(gè)流程如下：

如果當(dāng)前TreeMap沒有根節(jié)點(diǎn)，將當(dāng)前節(jié)點(diǎn)作為根節(jié)點(diǎn)插入，否則，
根據(jù)提供的比較器（如果沒有提供則使用默認(rèn)的比較器）進(jìn)行查找比較，查找該節(jié)點(diǎn)的插入位置，即它的父節(jié)點(diǎn)的位置。
查找到父節(jié)點(diǎn)后，根據(jù)比較結(jié)果插入到對(duì)應(yīng)位置，并進(jìn)行染色處理。
remove

前面我們講了插入操作，刪除操作要比插入操作復(fù)雜一下，我們先來描述一下刪除操作的大概流程：

將紅黑樹當(dāng)成一棵二叉查找樹，進(jìn)行節(jié)點(diǎn)刪除。
通過旋轉(zhuǎn)和著色，使其重新變成一棵復(fù)合規(guī)則的紅黑樹。
二叉查找樹時(shí)怎么做刪除的。前面我們已經(jīng)說過，在二叉查找樹上刪除一個(gè)節(jié)點(diǎn)，分為三種情況：

若刪除的是葉子節(jié)點(diǎn)，則不會(huì)破壞樹的結(jié)構(gòu)，只需要修改其雙親節(jié)點(diǎn)的指針即可。
若刪除的節(jié)點(diǎn)只有一個(gè)孩子節(jié)點(diǎn)，則用它的孩子節(jié)點(diǎn)代替它的位置即可，如此也不會(huì)破壞紅黑樹的結(jié)構(gòu)。
若刪除的節(jié)點(diǎn)有兩個(gè)孩子節(jié)點(diǎn)，這種情況復(fù)雜一下，我們通常會(huì)找到要?jiǎng)h除節(jié)點(diǎn)X的左子樹里的最大元素或者右子樹里的最小元素，然后用M替換掉X，再刪除節(jié)點(diǎn)，因?yàn)榇藭r(shí)M最多只會(huì)有一個(gè)
節(jié)點(diǎn)（如果左子樹最大元素則沒有右子節(jié)點(diǎn)，若是右子樹最小元素則沒有左子節(jié)點(diǎn)），若M沒有孩子節(jié)點(diǎn)，直接進(jìn)入情況1處理，若M只有一個(gè)孩子，則直接進(jìn)入情況2處理。
注：這里的替換指的是值拷貝，值拷貝并不會(huì)破壞紅黑樹的性質(zhì)。

這樣三種情況都可以當(dāng)做第一種或者第二種情況處理。

在刪除節(jié)點(diǎn)時(shí)，我們有兩個(gè)問題需要注意：

如果刪除的額是紅色節(jié)點(diǎn)，不會(huì)違反紅黑樹的規(guī)則。
如果刪除的是黑色節(jié)點(diǎn)，那么這個(gè)路徑上就少了一個(gè)黑色節(jié)點(diǎn)，則違反了紅黑樹規(guī)則。
這樣我們可以得知只有在插入的節(jié)點(diǎn)是黑色的時(shí)候才需要我們進(jìn)行處理，具體說來：

情況1：若刪除節(jié)點(diǎn)N的兄弟節(jié)點(diǎn)B是紅色，這種情況下，先對(duì)父節(jié)點(diǎn)P進(jìn)行左旋操作，結(jié)合對(duì)換P與B的顏色。此時(shí)左子樹仍然少了一個(gè)黑色節(jié)點(diǎn)，此時(shí)進(jìn)入情況3.
情況2：若刪除節(jié)點(diǎn)N的父親節(jié)點(diǎn)P，兄弟節(jié)點(diǎn)B以及B的兒子節(jié)點(diǎn)都是黑色，則將B染成紅色，這樣P到葉子節(jié)點(diǎn)的所有路徑都包含了相同的黑色節(jié)點(diǎn)，但是P的父節(jié)點(diǎn)G到葉子節(jié)點(diǎn)的路徑卻少了 一個(gè)黑色節(jié)點(diǎn)。這個(gè)時(shí)候我們要重新按照這套規(guī)則對(duì)P節(jié)點(diǎn)再進(jìn)行一次平衡處理。
情況3：若刪除節(jié)點(diǎn)N的父親節(jié)點(diǎn)P是紅色，兄弟節(jié)點(diǎn)B是黑色，則交換P與B顏色，這樣在B所在路徑上增加了一個(gè)黑色節(jié)點(diǎn)，彌補(bǔ)了已經(jīng)刪除的，樹重新達(dá)到平衡。
情況4： 若刪除節(jié)點(diǎn)N的兄弟節(jié)點(diǎn)B是黑澀，B的左孩子節(jié)點(diǎn)BL是紅色，B的右孩子節(jié)點(diǎn)BR是黑色，P為任意顏色。則減緩B與BL的顏色，右旋節(jié)點(diǎn)B。此時(shí)N所在路徑并沒有增加黑色節(jié)點(diǎn)，沒有達(dá)到平衡，進(jìn)入情況5.
情況5：若刪除節(jié)點(diǎn)N的兄弟節(jié)點(diǎn)B是黑色，B的右孩子節(jié)點(diǎn)BR是紅色，B的左孩子節(jié)點(diǎn)BL為任意顏色，P為任意顏色。則BR染成黑色，P染成黑色，B染成原來P的顏色；左旋節(jié)點(diǎn)，這樣 N路徑上增加了一個(gè)黑色節(jié)點(diǎn)，B路徑上少了一個(gè)黑色節(jié)點(diǎn)B，又增加了一個(gè)黑色節(jié)點(diǎn)BR，剛好達(dá)到平衡。
以上的流程看起來比較復(fù)雜，本質(zhì)上來說就是我們刪除了一個(gè)黑色節(jié)點(diǎn)，破壞了當(dāng)前路徑黑色節(jié)點(diǎn)的個(gè)數(shù)，解決的方法要么為這條路徑再添加一個(gè)黑色節(jié)點(diǎn)，要么將其他路徑的黑色節(jié)點(diǎn)都去掉一個(gè)。

 

public class TreeMap<K,V>  
extends AbstractMap<K,V> 
implements NavigableMap<K,V>, Cloneable, java.io.Serializable{ 
 
public V remove(Object key) { 
TreeMapEntry<K,V> p = getEntry(key); 
if (p == null) 
return null; 
 
V oldValue = p.value; 
deleteEntry(p); 
return oldValue; 
} 
 
private void deleteEntry(TreeMapEntry<K,V> p) { 
//操作記錄自增 
modCount++; 
//集合大小自減 
size--; 
 
///如果要?jiǎng)h除的節(jié)點(diǎn)p的左右子節(jié)點(diǎn)都不為空，則查找其替代節(jié)點(diǎn)并進(jìn)行節(jié)點(diǎn)替換 
if (p.left != null && p.right != null) { 
//查找其替代節(jié)點(diǎn)，替代節(jié)點(diǎn)為左子樹的最大元素或者右子樹的最小元素 
TreeMapEntry<K,V> s = successor(p); 
p.key = s.key; 
p.value = s.value; 
p = s; 
} // p has 2 children 
 
//查找替代節(jié)點(diǎn)的孩子節(jié)點(diǎn)，replacement指的是我們圖中說來的N節(jié)點(diǎn)，p指的是圖中的 
TreeMapEntry<K,V> replacement = (p.left != null ? p.left : p.right); 
 
//刪除p，并重新建立replacement節(jié)點(diǎn)的連接 
if (replacement != null) { 
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. 
pp.left = p.right = p.parent = null; 
 
//如果刪除的黑色節(jié)點(diǎn)，則需要重新平衡樹 
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; 
} 
} 
} 
 
//查找其替代節(jié)點(diǎn)，替代節(jié)點(diǎn)為左子樹的最大元素或者右子樹的最小元素 
static <K,V> TreeMapEntry<K,V> successor(TreeMapEntry<K,V> t) { 
if (t == null) 
return null; 
//查找右子樹的最小元素，即最左孩子 
else if (t.right != null) { 
TreeMapEntry<K,V> p = t.right; 
while (p.left != null) 
pp = p.left; 
return p; 
}  
//查找左子樹的最大元素，即最右孩子 
else { 
TreeMapEntry<K,V> p = t.parent; 
TreeMapEntry<K,V> ch = t; 
while (p != null && ch == p.right) { 
ch = p; 
pp = p.parent; 
} 
return p; 
} 
} 
 
static <K,V> TreeMapEntry<K,V> predecessor(TreeMapEntry<K,V> t) { 
if (t == null) 
return null; 
else if (t.left != null) { 
TreeMapEntry<K,V> p = t.left; 
while (p.right != null) 
pp = p.right; 
return p; 
} else { 
TreeMapEntry<K,V> p = t.parent; 
TreeMapEntry<K,V> ch = t; 
while (p != null && ch == p.left) { 
ch = p; 
pp = p.parent;s 
} 
return p; 
} 
} 
} 

我們?cè)賮砜纯磀eleteEntry()方法的實(shí)現(xiàn)流程：

如果要?jiǎng)h除的節(jié)點(diǎn)p的左右子節(jié)點(diǎn)都不為空，則查找其替代節(jié)點(diǎn)并進(jìn)行節(jié)點(diǎn)替換。
查找替代節(jié)點(diǎn)的孩子節(jié)點(diǎn)，replacement指的是我們圖中說來的N節(jié)點(diǎn)，p指的是圖中的M，如果p是黑色節(jié)點(diǎn)，則刪除p后需要重新進(jìn)行
樹的平衡處理。
get

 

public class TreeMap<K,V>  
extends AbstractMap<K,V> 
implements NavigableMap<K,V>, Cloneable, java.io.Serializable{ 
 
public V get(Object key) { 
TreeMapEntry<K,V> p = getEntry(key); 
return (p==null ? null : p.value); 
} 
 
final TreeMapEntry<K,V> getEntry(Object key) { 
// Offload comparator-based version for sake of performance 
if (comparator != null) 
return getEntryUsingComparator(key); 
if (key == null) 
throw new NullPointerException(); 
@SuppressWarnings("unchecked") 
Comparable<? super K> k = (Comparable<? super K>) key; 
TreeMapEntry<K,V> p = root; 
//從根節(jié)點(diǎn)開始查找，根據(jù)比較結(jié)果決定從左子樹開始查找還是從右子樹開始查找 
while (p != null) { 
int cmp = k.compareTo(p.key); 
if (cmp < 0) 
pp = p.left; 
else if (cmp > 0) 
pp = p.right; 
else 
return p; 
} 
return null; 
} 
} 

TreeMap的查找流程和二叉查找樹的查找流程是一樣的，這里是從根節(jié)點(diǎn)開始查找，根據(jù)比較結(jié)果決定是下一步是從左子樹開始查找，還是從右子樹開始查找。