TreeMap的實(shí)現(xiàn)是紅黑樹(shù)算法的實(shí)現(xiàn)，所以要了解TreeMap就必須對(duì)紅黑樹(shù)有一定的了解,其實(shí)這篇博文的名字叫做：根據(jù)紅黑樹(shù)的算法來(lái)分析TreeMap的實(shí)現(xiàn)，但是為了與Java提高篇系列博文保持一致還是叫做TreeMap比較好。通過(guò)這篇博文你可以獲得如下知識(shí)點(diǎn)：
1、紅黑樹(shù)的基本概念。
2、紅黑樹(shù)增加節(jié)點(diǎn)、刪除節(jié)點(diǎn)的實(shí)現(xiàn)過(guò)程。
3、紅黑樹(shù)左旋轉(zhuǎn)、右旋轉(zhuǎn)的復(fù)雜過(guò)程。
4、Java 中TreeMap是如何通過(guò)put、deleteEntry兩個(gè)來(lái)實(shí)現(xiàn)紅黑樹(shù)增加、刪除節(jié)點(diǎn)的。
我想通過(guò)這篇博文你對(duì)TreeMap一定有了更深的認(rèn)識(shí)。好了，下面先簡(jiǎn)單普及紅黑樹(shù)知識(shí)。
一、紅黑樹(shù)簡(jiǎn)介
紅黑樹(shù)又稱紅-黑二叉樹(shù)，它首先是一顆二叉樹(shù)，它具體二叉樹(shù)所有的特性。同時(shí)紅黑樹(shù)更是一顆自平衡的排序二叉樹(shù)。
我們知道一顆基本的二叉樹(shù)他們都需要滿足一個(gè)基本性質(zhì)--即樹(shù)中的任何節(jié)點(diǎn)的值大于它的左子節(jié)點(diǎn)，且小于它的右子節(jié)點(diǎn)。按照這個(gè)基本性質(zhì)使得樹(shù)的檢索效率大大提高。我們知道在生成二叉樹(shù)的過(guò)程是非常容易失衡的，最壞的情況就是一邊倒（只有右/左子樹(shù)），這樣勢(shì)必會(huì)導(dǎo)致二叉樹(shù)的檢索效率大大降低（O(n)），所以為了維持二叉樹(shù)的平衡，大牛們提出了各種實(shí)現(xiàn)的算法，如：AVL，SBT，伸展樹(shù)，TREAP ，紅黑樹(shù)等等。
平衡二叉樹(shù)必須具備如下特性：它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。也就是說(shuō)該二叉樹(shù)的任何一個(gè)等等子節(jié)點(diǎn)，其左右子樹(shù)的高度都相近。
紅黑樹(shù)顧名思義就是節(jié)點(diǎn)是紅色或者黑色的平衡二叉樹(shù)，它通過(guò)顏色的約束來(lái)維持著二叉樹(shù)的平衡。對(duì)于一棵有效的紅黑樹(shù)二叉樹(shù)而言我們必須增加如下規(guī)則：
1、每個(gè)節(jié)點(diǎn)都只能是紅色或者黑色
2、根節(jié)點(diǎn)是黑色
3、每個(gè)葉節(jié)點(diǎn)（NIL節(jié)點(diǎn)，空節(jié)點(diǎn)）是黑色的。
4、如果一個(gè)結(jié)點(diǎn)是紅的，則它兩個(gè)子節(jié)點(diǎn)都是黑的。也就是說(shuō)在一條路徑上不能出現(xiàn)相鄰的兩個(gè)紅色結(jié)點(diǎn)。
5、從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
這些約束強(qiáng)制了紅黑樹(shù)的關(guān)鍵性質(zhì): 從根到葉子的最長(zhǎng)的可能路徑不多于最短的可能路徑的兩倍長(zhǎng)。結(jié)果是這棵樹(shù)大致上是平衡的。因?yàn)椴僮鞅热绮迦?、刪除和查找某個(gè)值的最壞情況時(shí)間都要求與樹(shù)的高度成比例，這個(gè)在高度上的理論上限允許紅黑樹(shù)在最壞情況下都是高效的，而不同于普通的二叉查找樹(shù)。所以紅黑樹(shù)它是復(fù)雜而高效的，其檢索效率O(log n)。下圖為一顆典型的紅黑二叉樹(shù)。
對(duì)于紅黑二叉樹(shù)而言它主要包括三大基本操作：左旋、右旋、著色。
注：由于本文主要是講解Java中TreeMap，所以并沒(méi)有對(duì)紅黑樹(shù)進(jìn)行非常深入的了解和研究，如果諸位想對(duì)其進(jìn)行更加深入的研究Lz提供幾篇較好的博文：
**** **1、紅黑樹(shù)系列集錦
**** **2、紅黑樹(shù)數(shù)據(jù)結(jié)構(gòu)剖析
**** **3、紅黑樹(shù)
二、TreeMap數(shù)據(jù)結(jié)構(gòu)
>>>>>>回歸主角：TreeMap<<<<<<
TreeMap的定義如下：
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
TreeMap繼承AbstractMap，實(shí)現(xiàn)NavigableMap、Cloneable、Serializable三個(gè)接口。其中AbstractMap表明TreeMap為一個(gè)Map即支持key-value的集合， NavigableMap（更多）則意味著它支持一系列的導(dǎo)航方法，具備針對(duì)給定搜索目標(biāo)返回最接近匹配項(xiàng)的導(dǎo)航方法 。
** **TreeMap中同時(shí)也包含了如下幾個(gè)重要的屬性：
//比較器，因?yàn)門reeMap是有序的，通過(guò)comparator接口我們可以對(duì)TreeMap的內(nèi)部排序進(jìn)行精密的控制
private final Comparator<? super K> comparator;
//TreeMap紅-黑節(jié)點(diǎn)，為TreeMap的內(nèi)部類
private transient Entry<K,V> root = null;
//容器大小
private transient int size = 0;
//TreeMap修改次數(shù)
private transient int modCount = 0;
//紅黑樹(shù)的節(jié)點(diǎn)顏色--紅色
private static final boolean RED = false;
//紅黑樹(shù)的節(jié)點(diǎn)顏色--黑色
private static final boolean BLACK = true;
對(duì)于葉子節(jié)點(diǎn)Entry是TreeMap的內(nèi)部類，它有幾個(gè)重要的屬性：
K key;
//值
V value;
//左孩子
Entry<K,V> left = null;
//右孩子
Entry<K,V> right = null;
//父親
Entry<K,V> parent;
//顏色
boolean color = BLACK;
注：前面只是開(kāi)胃菜，下面是本篇博文的重中之重，在下面兩節(jié)我將重點(diǎn)講解treeMap的put()、delete()方法。通過(guò)這兩個(gè)方法我們會(huì)了解紅黑樹(shù)增加、刪除節(jié)點(diǎn)的核心算法。
** **三、TreeMap put()方法
** **在了解TreeMap的put()方法之前，我們先了解紅黑樹(shù)增加節(jié)點(diǎn)的算法。
** **紅黑樹(shù)增加節(jié)點(diǎn)
** **紅黑樹(shù)在新增節(jié)點(diǎn)過(guò)程中比較復(fù)雜，復(fù)雜歸復(fù)雜它同樣必須要依據(jù)上面提到的五點(diǎn)規(guī)范，同時(shí)由于規(guī)則1、2、3基本都會(huì)滿足，下面我們主要討論規(guī)則4、5。假設(shè)我們這里有一棵最簡(jiǎn)單的樹(shù)，我們規(guī)定新增的節(jié)點(diǎn)為N、它的父節(jié)點(diǎn)為P、P的兄弟節(jié)點(diǎn)為U、P的父節(jié)點(diǎn)為G。
對(duì)于新節(jié)點(diǎn)的插入有如下三個(gè)關(guān)鍵地方：
1、插入新節(jié)點(diǎn)總是紅色節(jié)點(diǎn) 。
2、如果插入節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色, 能維持性質(zhì) 。
3、如果插入節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色, 破壞了性質(zhì). 故插入算法就是通過(guò)重新著色或旋轉(zhuǎn), 來(lái)維持性質(zhì) 。
為了保證下面的闡述更加清晰和根據(jù)便于參考，我這里將紅黑樹(shù)的五點(diǎn)規(guī)定再貼一遍：
![Uploading image_935926.png . . .]
一、為跟節(jié)點(diǎn)
若新插入的節(jié)點(diǎn)N沒(méi)有父節(jié)點(diǎn)，則直接當(dāng)做根據(jù)節(jié)點(diǎn)插入即可，同時(shí)將顏色設(shè)置為黑色。（如圖一（1））
二、父節(jié)點(diǎn)為黑色
這種情況新節(jié)點(diǎn)N同樣是直接插入，同時(shí)顏色為紅色，由于根據(jù)規(guī)則四它會(huì)存在兩個(gè)黑色的葉子節(jié)點(diǎn)，值為null。同時(shí)由于新增節(jié)點(diǎn)N為紅色，所以通過(guò)它的子節(jié)點(diǎn)的路徑依然會(huì)保存著相同的黑色節(jié)點(diǎn)數(shù)，同樣滿足規(guī)則5。（如圖一（2））
三、若父節(jié)點(diǎn)P和P的兄弟節(jié)點(diǎn)U都為紅色
對(duì)于這種情況若直接插入肯定會(huì)出現(xiàn)不平衡現(xiàn)象。怎么處理？P、U節(jié)點(diǎn)變黑、G節(jié)點(diǎn)變紅。這時(shí)由于經(jīng)過(guò)節(jié)點(diǎn)P、U的路徑都必須經(jīng)過(guò)G所以在這些路徑上面的黑節(jié)點(diǎn)數(shù)目還是相同的。但是經(jīng)過(guò)上面的處理，可能G節(jié)點(diǎn)的父節(jié)點(diǎn)也是紅色，這個(gè)時(shí)候我們需要將G節(jié)點(diǎn)當(dāng)做新增節(jié)點(diǎn)遞歸處理。
四、若父節(jié)點(diǎn)P為紅色，叔父節(jié)點(diǎn)U為黑色或者缺少，且新增節(jié)點(diǎn)N為P節(jié)點(diǎn)的右孩子
對(duì)于這種情況我們對(duì)新增節(jié)點(diǎn)N、P進(jìn)行一次左旋轉(zhuǎn)。這里所產(chǎn)生的結(jié)果其實(shí)并沒(méi)有完成，還不是平衡的（違反了規(guī)則四），這是我們需要進(jìn)行情況5的操作。
五、父節(jié)點(diǎn)P為紅色，叔父節(jié)點(diǎn)U為黑色或者缺少，新增節(jié)點(diǎn)N為父節(jié)點(diǎn)P左孩子
這種情況有可能是由于情況四而產(chǎn)生的，也有可能不是。對(duì)于這種情況先已P節(jié)點(diǎn)為中心進(jìn)行右旋轉(zhuǎn)，在旋轉(zhuǎn)后產(chǎn)生的樹(shù)中，節(jié)點(diǎn)P是節(jié)點(diǎn)N、G的父節(jié)點(diǎn)。但是這棵樹(shù)并不規(guī)范，它違反了規(guī)則4，所以我們將P、G節(jié)點(diǎn)的顏色進(jìn)行交換，使之其滿足規(guī)范。開(kāi)始時(shí)所有的路徑都需要經(jīng)過(guò)G其他們的黑色節(jié)點(diǎn)數(shù)一樣，但是現(xiàn)在所有的路徑改為經(jīng)過(guò)P，且P為整棵樹(shù)的唯一黑色節(jié)點(diǎn)，所以調(diào)整后的樹(shù)同樣滿足規(guī)范5。
上面展示了紅黑樹(shù)新增節(jié)點(diǎn)的五種情況，這五種情況涵蓋了所有的新增可能，不管這棵紅黑樹(shù)多么復(fù)雜，都可以根據(jù)這五種情況來(lái)進(jìn)行生成。下面就來(lái)分析Java中的TreeMap是如何來(lái)實(shí)現(xiàn)紅黑樹(shù)的。
TreeMap put()方法實(shí)現(xiàn)分析
在TreeMap的put()的實(shí)現(xiàn)方法中主要分為兩個(gè)步驟，第一：構(gòu)建排序二叉樹(shù)，第二：平衡二叉樹(shù)。
對(duì)于排序二叉樹(shù)的創(chuàng)建，其添加節(jié)點(diǎn)的過(guò)程如下：
1、以根節(jié)點(diǎn)為初始節(jié)點(diǎn)進(jìn)行檢索。
2、與當(dāng)前節(jié)點(diǎn)進(jìn)行比對(duì)，若新增節(jié)點(diǎn)值較大，則以當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn)。否則以當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn)。
3、循環(huán)遞歸2步驟知道檢索出合適的葉子節(jié)點(diǎn)為止。
4、將新增節(jié)點(diǎn)與3步驟中找到的節(jié)點(diǎn)進(jìn)行比對(duì)，如果新增節(jié)點(diǎn)較大，則添加為右子節(jié)點(diǎn)；否則添加為左子節(jié)點(diǎn)。
按照這個(gè)步驟我們就可以將一個(gè)新增節(jié)點(diǎn)添加到排序二叉樹(shù)中合適的位置。如下：
public V put(K key, V value) {
//用t表示二叉樹(shù)的當(dāng)前節(jié)點(diǎn)
Entry<K,V> t = root;
//t為null表示一個(gè)空樹(shù)，即TreeMap中沒(méi)有任何元素，直接插入
if (t == null) {
//比較key值，個(gè)人覺(jué)得這句代碼沒(méi)有任何意義，空樹(shù)還需要比較、排序？
compare(key, key); // type (and possibly null) check
//將新的key-value鍵值對(duì)創(chuàng)建為一個(gè)Entry節(jié)點(diǎn)，并將該節(jié)點(diǎn)賦予給root
root = new Entry<>(key, value, null);
//容器的size = 1，表示TreeMap集合中存在一個(gè)元素
size = 1;
//修改次數(shù) + 1
modCount++;
return null;
}
int cmp; //cmp表示key排序的返回結(jié)果
Entry<K,V> parent; //父節(jié)點(diǎn)
// split comparator and comparable paths
Comparator<? super K> cpr = comparator; //指定的排序算法
//如果cpr不為空，則采用既定的排序算法進(jìn)行創(chuàng)建TreeMap集合
if (cpr != null) {
do {
parent = t; //parent指向上次循環(huán)后的t
//比較新增節(jié)點(diǎn)的key和當(dāng)前節(jié)點(diǎn)key的大小
cmp = cpr.compare(key, t.key);
//cmp返回值小于0，表示新增節(jié)點(diǎn)的key小于當(dāng)前節(jié)點(diǎn)的key，則以當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn)
if (cmp < 0)
t = t.left;
//cmp返回值大于0，表示新增節(jié)點(diǎn)的key大于當(dāng)前節(jié)點(diǎn)的key，則以當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn)
else if (cmp > 0)
t = t.right;
//cmp返回值等于0，表示兩個(gè)key值相等，則新值覆蓋舊值，并返回新值
else
return t.setValue(value);
} while (t != null);
}
//如果cpr為空，則采用默認(rèn)的排序算法進(jìn)行創(chuàng)建TreeMap集合
else {
if (key == null) //key值為空拋出異常
throw new NullPointerException();
/* 下面處理過(guò)程和上面一樣 */
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);
}
//將新增節(jié)點(diǎn)當(dāng)做parent的子節(jié)點(diǎn)
Entry<K,V> e = new Entry<>(key, value, parent);
//如果新增節(jié)點(diǎn)的key小于parent的key，則當(dāng)做左子節(jié)點(diǎn)
if (cmp < 0)
parent.left = e;
//如果新增節(jié)點(diǎn)的key大于parent的key，則當(dāng)做右子節(jié)點(diǎn)
else
parent.right = e;
/*
* 上面已經(jīng)完成了排序二叉樹(shù)的的構(gòu)建，將新增節(jié)點(diǎn)插入該樹(shù)中的合適位置
* 下面fixAfterInsertion()方法就是對(duì)這棵樹(shù)進(jìn)行調(diào)整、平衡，具體過(guò)程參考上面的五種情況
*/
fixAfterInsertion(e);
//TreeMap元素?cái)?shù)量 + 1
size++;
//TreeMap容器修改次數(shù) + 1
modCount++;
return null;
}
上面代碼中do{}代碼塊是實(shí)現(xiàn)排序二叉樹(shù)的核心算法，通過(guò)該算法我們可以確認(rèn)新增節(jié)點(diǎn)在該樹(shù)的正確位置。找到正確位置后將插入即可，這樣做了其實(shí)還沒(méi)有完成，因?yàn)槲抑繲reeMap的底層實(shí)現(xiàn)是紅黑樹(shù)，紅黑樹(shù)是一棵平衡排序二叉樹(shù)，普通的排序二叉樹(shù)可能會(huì)出現(xiàn)失衡的情況，所以下一步就是要進(jìn)行調(diào)整。fixAfterInsertion(e); 調(diào)整的過(guò)程務(wù)必會(huì)涉及到紅黑樹(shù)的左旋、右旋、著色三個(gè)基本操作。代碼如下：
/**
* 新增節(jié)點(diǎn)后的修復(fù)操作
* x 表示新增節(jié)點(diǎn)
*/
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED; //新增節(jié)點(diǎn)的顏色為紅色
//循環(huán) 直到 x不是根節(jié)點(diǎn)，且x的父節(jié)點(diǎn)不為紅色
while (x != null && x != root && x.parent.color == RED) {
//如果X的父節(jié)點(diǎn)（P）是其父節(jié)點(diǎn)的父節(jié)點(diǎn)（G）的左節(jié)點(diǎn)
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//獲取X的叔節(jié)點(diǎn)(U)
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
//如果X的叔節(jié)點(diǎn)（U） 為紅色（情況三）
if (colorOf(y) == RED) {
//將X的父節(jié)點(diǎn)（P）設(shè)置為黑色
setColor(parentOf(x), BLACK);
//將X的叔節(jié)點(diǎn)（U）設(shè)置為黑色
setColor(y, BLACK);
//將X的父節(jié)點(diǎn)的父節(jié)點(diǎn)（G）設(shè)置紅色
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
}
//如果X的叔節(jié)點(diǎn)（U為黑色）；這里會(huì)存在兩種情況（情況四、情況五）
else {
//如果X節(jié)點(diǎn)為其父節(jié)點(diǎn)（P）的右子樹(shù)，則進(jìn)行左旋轉(zhuǎn)（情況四）
if (x == rightOf(parentOf(x))) {
//將X的父節(jié)點(diǎn)作為X
x = parentOf(x);
//右旋轉(zhuǎn)
rotateLeft(x);
}
//（情況五）
//將X的父節(jié)點(diǎn)（P）設(shè)置為黑色
setColor(parentOf(x), BLACK);
//將X的父節(jié)點(diǎn)的父節(jié)點(diǎn)（G）設(shè)置紅色
setColor(parentOf(parentOf(x)), RED);
//以X的父節(jié)點(diǎn)的父節(jié)點(diǎn)（G）為中心右旋轉(zhuǎn)
rotateRight(parentOf(parentOf(x)));
}
}
//如果X的父節(jié)點(diǎn)（P）是其父節(jié)點(diǎn)的父節(jié)點(diǎn)（G）的右節(jié)點(diǎn)
else {
//獲取X的叔節(jié)點(diǎn)（U）
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
//如果X的叔節(jié)點(diǎn)（U） 為紅色（情況三）
if (colorOf(y) == RED) {
//將X的父節(jié)點(diǎn)（P）設(shè)置為黑色
setColor(parentOf(x), BLACK);
//將X的叔節(jié)點(diǎn)（U）設(shè)置為黑色
setColor(y, BLACK);
//將X的父節(jié)點(diǎn)的父節(jié)點(diǎn)（G）設(shè)置紅色
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
}
//如果X的叔節(jié)點(diǎn)（U為黑色）；這里會(huì)存在兩種情況（情況四、情況五）
else {
//如果X節(jié)點(diǎn)為其父節(jié)點(diǎn)（P）的右子樹(shù)，則進(jìn)行左旋轉(zhuǎn)（情況四）
if (x == leftOf(parentOf(x))) {
//將X的父節(jié)點(diǎn)作為X
x = parentOf(x);
//右旋轉(zhuǎn)
rotateRight(x);
}
//（情況五）
//將X的父節(jié)點(diǎn)（P）設(shè)置為黑色
setColor(parentOf(x), BLACK);
//將X的父節(jié)點(diǎn)的父節(jié)點(diǎn)（G）設(shè)置紅色
setColor(parentOf(parentOf(x)), RED);
//以X的父節(jié)點(diǎn)的父節(jié)點(diǎn)（G）為中心右旋轉(zhuǎn)
rotateLeft(parentOf(parentOf(x)));
}
}
}
//將根節(jié)點(diǎn)G強(qiáng)制設(shè)置為黑色
root.color = BLACK;
}
對(duì)這段代碼的研究我們發(fā)現(xiàn),其處理過(guò)程完全符合紅黑樹(shù)新增節(jié)點(diǎn)的處理過(guò)程。所以在看這段代碼的過(guò)程一定要對(duì)紅黑樹(shù)的新增節(jié)點(diǎn)過(guò)程有了解。在這個(gè)代碼中還包含幾個(gè)重要的操作。左旋(rotateLeft())、右旋（rotateRight()）、著色（setColor()）。
左旋：rotateLeft()
所謂左旋轉(zhuǎn)，就是將新增節(jié)點(diǎn)（N）當(dāng)做其父節(jié)點(diǎn)（P），將其父節(jié)點(diǎn)P當(dāng)做新增節(jié)點(diǎn)（N）的左子節(jié)點(diǎn)。即：G.left ---> N ,N.left ---> P。
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
//獲取P的右子節(jié)點(diǎn)，其實(shí)這里就相當(dāng)于新增節(jié)點(diǎn)N（情況四而言）
Entry<K,V> r = p.right;
//將R的左子樹(shù)設(shè)置為P的右子樹(shù)
p.right = r.left;
//若R的左子樹(shù)不為空，則將P設(shè)置為R左子樹(shù)的父親
if (r.left != null)
r.left.parent = p;
//將P的父親設(shè)置R的父親
r.parent = p.parent;
//如果P的父親為空，則將R設(shè)置為跟節(jié)點(diǎn)
if (p.parent == null)
root = r;
//如果P為其父節(jié)點(diǎn)（G）的左子樹(shù)，則將R設(shè)置為P父節(jié)點(diǎn)(G)左子樹(shù)
else if (p.parent.left == p)
p.parent.left = r;
//否則R設(shè)置為P的父節(jié)點(diǎn)（G）的右子樹(shù)
else
p.parent.right = r;
//將P設(shè)置為R的左子樹(shù)
r.left = p;
//將R設(shè)置為P的父節(jié)點(diǎn)
p.parent = r;
}
}
右旋：rotateRight()
所謂右旋轉(zhuǎn)即，P.right ---> G、G.parent ---> P。
private void rotateRight(Entry<K,V> p) {
if (p != null) {
//將L設(shè)置為P的左子樹(shù)
Entry<K,V> l = p.left;
//將L的右子樹(shù)設(shè)置為P的左子樹(shù)
p.left = l.right;
//若L的右子樹(shù)不為空，則將P設(shè)置L的右子樹(shù)的父節(jié)點(diǎn)
if (l.right != null)
l.right.parent = p;
//將P的父節(jié)點(diǎn)設(shè)置為L(zhǎng)的父節(jié)點(diǎn)
l.parent = p.parent;
//如果P的父節(jié)點(diǎn)為空，則將L設(shè)置根節(jié)點(diǎn)
if (p.parent == null)
root = l;
//若P為其父節(jié)點(diǎn)的右子樹(shù)，則將L設(shè)置為P的父節(jié)點(diǎn)的右子樹(shù)
else if (p.parent.right == p)
p.parent.right = l;
//否則將L設(shè)置為P的父節(jié)點(diǎn)的左子樹(shù)
else
p.parent.left = l;
//將P設(shè)置為L(zhǎng)的右子樹(shù)
l.right = p;
//將L設(shè)置為P的父節(jié)點(diǎn)
p.parent = l;
}
}
著色：setColor()
著色就是改變?cè)摴?jié)點(diǎn)的顏色，在紅黑樹(shù)中，它是依靠節(jié)點(diǎn)的顏色來(lái)維持平衡的。
private static <K,V> void setColor(Entry<K,V> p, boolean c) {
if (p != null)
p.color = c;
}
** **四、TreeMap delete()方法
** 紅黑樹(shù)刪除節(jié)點(diǎn)
** 針對(duì)于紅黑樹(shù)的增加節(jié)點(diǎn)而言，刪除顯得更加復(fù)雜，使原本就復(fù)雜的紅黑樹(shù)變得更加復(fù)雜。同時(shí)刪除節(jié)點(diǎn)和增加節(jié)點(diǎn)一樣，同樣是找到刪除的節(jié)點(diǎn)，刪除之后調(diào)整紅黑樹(shù)。但是這里的刪除節(jié)點(diǎn)并不是直接刪除，而是通過(guò)走了“彎路”通過(guò)一種捷徑來(lái)刪除的：找到被刪除的節(jié)點(diǎn)D的子節(jié)點(diǎn)C，用C來(lái)替代D，不是直接刪除D，因?yàn)镈被C替代了，直接刪除C即可。所以這里就將刪除父節(jié)點(diǎn)D的事情轉(zhuǎn)變?yōu)榱藙h除子節(jié)點(diǎn)C的事情，這樣處理就將復(fù)雜的刪除事件簡(jiǎn)單化了。子節(jié)點(diǎn)C的規(guī)則是：右分支最左邊，或者 左分支最右邊的。
紅-黑二叉樹(shù)刪除節(jié)點(diǎn)，最大的麻煩是要保持 各分支黑色節(jié)點(diǎn)數(shù)目相等。 因?yàn)槭莿h除，所以不用擔(dān)心存在顏色沖突問(wèn)題——插入才會(huì)引起顏色沖突。
紅黑樹(shù)刪除節(jié)點(diǎn)同樣會(huì)分成幾種情況，這里是按照待刪除節(jié)點(diǎn)有幾個(gè)兒子的情況來(lái)進(jìn)行分類：
1、沒(méi)有兒子，即為葉結(jié)點(diǎn)。直接把父結(jié)點(diǎn)的對(duì)應(yīng)兒子指針設(shè)為NULL，刪除兒子結(jié)點(diǎn)就OK了。
2、只有一個(gè)兒子。那么把父結(jié)點(diǎn)的相應(yīng)兒子指針指向兒子的獨(dú)生子，刪除兒子結(jié)點(diǎn)也OK了。
3、有兩個(gè)兒子。這種情況比較復(fù)雜，但還是比較簡(jiǎn)單。上面提到過(guò)用子節(jié)點(diǎn)C替代代替待刪除節(jié)點(diǎn)D，然后刪除子節(jié)點(diǎn)C即可。
下面就論各種刪除情況來(lái)進(jìn)行圖例講解，但是在講解之前請(qǐng)?jiān)试S我再次啰嗦一句，請(qǐng)時(shí)刻牢記紅黑樹(shù)的5點(diǎn)規(guī)定：
1、每個(gè)節(jié)點(diǎn)都只能是紅色或者黑色
2、根節(jié)點(diǎn)是黑色
3、每個(gè)葉節(jié)點(diǎn)（NIL節(jié)點(diǎn)，空節(jié)點(diǎn)）是黑色的。
4、如果一個(gè)結(jié)點(diǎn)是紅的，則它兩個(gè)子節(jié)點(diǎn)都是黑的。也就是說(shuō)在一條路徑上不能出現(xiàn)相鄰的兩個(gè)紅色結(jié)點(diǎn)。
5、從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
（注：已經(jīng)講三遍了，再不記住我就懷疑你是否適合搞IT了 O(∩_∩)O~）
誠(chéng)然，既然刪除節(jié)點(diǎn)比較復(fù)雜，那么在這里我們就約定一下規(guī)則：
1、下面要講解的刪除節(jié)點(diǎn)一定是實(shí)際要?jiǎng)h除節(jié)點(diǎn)的后繼節(jié)點(diǎn)（N），如前面提到的C。
2、下面提到的刪除節(jié)點(diǎn)的樹(shù)都是如下結(jié)構(gòu)，該結(jié)構(gòu)所選取的節(jié)點(diǎn)是待刪除節(jié)點(diǎn)的右樹(shù)的最左邊子節(jié)點(diǎn)。這里我們規(guī)定真實(shí)刪除節(jié)點(diǎn)為N、父節(jié)點(diǎn)為P、兄弟節(jié)點(diǎn)為W兄弟節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)為X1、X2。如下圖（2.1）。
現(xiàn)在我們就上面提到的三種情況進(jìn)行分析、處理。
情況一、無(wú)子節(jié)點(diǎn)（紅色節(jié)點(diǎn)）
這種情況對(duì)該節(jié)點(diǎn)直接刪除即可，不會(huì)影響樹(shù)的結(jié)構(gòu)。因?yàn)樵摴?jié)點(diǎn)為葉子節(jié)點(diǎn)它不可能存在子節(jié)點(diǎn)-----如子節(jié)點(diǎn)為黑，則違反黑節(jié)點(diǎn)數(shù)原則（規(guī)定5），為紅，則違反“顏色”原則（規(guī)定4）。 如上圖（2.2）。
情況二、有一個(gè)子節(jié)點(diǎn)
這種情況處理也是非常簡(jiǎn)單的，用子節(jié)點(diǎn)替代待刪除節(jié)點(diǎn)，然后刪除子節(jié)點(diǎn)即可。如上圖（2.3）
情況三、有兩個(gè)子節(jié)點(diǎn)
這種情況可能會(huì)稍微有點(diǎn)兒復(fù)雜。它需要找到一個(gè)替代待刪除節(jié)點(diǎn)（N）來(lái)替代它，然后刪除N即可。它主要分為四種情況。
1、N的兄弟節(jié)點(diǎn)W為紅色
2、N的兄弟w是黑色的，且w的倆個(gè)孩子都是黑色的。
3、N的兄弟w是黑色的，w的左孩子是紅色，w的右孩子是黑色。
4、N的兄弟w是黑色的，且w的右孩子時(shí)紅色的。
情況3.1、N的兄弟節(jié)點(diǎn)W為紅色
W為紅色，那么其子節(jié)點(diǎn)X1、X2必定全部為黑色，父節(jié)點(diǎn)P也為黑色。處理策略是：改變W、P的顏色，然后進(jìn)行一次左旋轉(zhuǎn)。這樣處理就可以使得紅黑性質(zhì)得以繼續(xù)保持。N的新兄弟new w是旋轉(zhuǎn)之前w的某個(gè)孩子，為黑色。這樣處理后將情況3.1、轉(zhuǎn)變?yōu)?.2、3.3、3.4中的一種。如下：
情況3.2、N的兄弟w是黑色的，且w的倆個(gè)孩子都是黑色的。
這種情況其父節(jié)點(diǎn)可紅可黑，由于W為黑色，這樣導(dǎo)致N子樹(shù)相對(duì)于其兄弟W子樹(shù)少一個(gè)黑色節(jié)點(diǎn)，這時(shí)我們可以將W置為紅色。這樣，N子樹(shù)與W子樹(shù)黑色節(jié)點(diǎn)一致，保持了平衡。如下
將W由黑轉(zhuǎn)變?yōu)榧t，這樣就會(huì)導(dǎo)致新節(jié)點(diǎn)new N相對(duì)于它的兄弟節(jié)點(diǎn)會(huì)少一個(gè)黑色節(jié)點(diǎn)。但是如果new x為紅色，我們直接將new x轉(zhuǎn)變?yōu)楹谏３终脴?shù)的平衡。否則情況3.2 會(huì)轉(zhuǎn)變?yōu)榍闆r3.1、3.3、3.4中的一種。
情況3.3、N的兄弟w是黑色的，w的左孩子是紅色，w的右孩子是黑色。
針對(duì)這種情況是將節(jié)點(diǎn)W和其左子節(jié)點(diǎn)進(jìn)行顏色交換，然后對(duì)W進(jìn)行右旋轉(zhuǎn)處理。
此時(shí)N的新兄弟X1(new w)是一個(gè)有紅色右孩子的黑結(jié)點(diǎn)，于是將情況3轉(zhuǎn)化為情況4.
情況3.4、N的兄弟w是黑色的，且w的右孩子時(shí)紅色的。
交換W和父節(jié)點(diǎn)P的顏色，同時(shí)對(duì)P進(jìn)行左旋轉(zhuǎn)操作。這樣就把左邊缺失的黑色節(jié)點(diǎn)給補(bǔ)回來(lái)了。同時(shí)將W的右子節(jié)點(diǎn)X2置黑。這樣左右都達(dá)到了平衡。
**** 總結(jié)
** **個(gè)人認(rèn)為這四種情況比較難理解，首先他們都不是單一的某種情況，他們之間是可以進(jìn)行互轉(zhuǎn)的。相對(duì)于其他的幾種情況，情況3.2比較好理解，僅僅只是一個(gè)顏色的轉(zhuǎn)變，通過(guò)減少右子樹(shù)的一個(gè)黑色節(jié)點(diǎn)使之保持平衡，同時(shí)將不平衡點(diǎn)上移至N與W的父節(jié)點(diǎn)，然后進(jìn)行下一輪迭代。情況3.1，是將W旋轉(zhuǎn)將其轉(zhuǎn)成情況2、3、4情況進(jìn)行處理。而情況3.3通過(guò)轉(zhuǎn)變后可以化成情況3.4來(lái)進(jìn)行處理，從這里可以看出情況3.4應(yīng)該最終結(jié)。情況3.4、右子節(jié)點(diǎn)為紅色節(jié)點(diǎn)，那么將缺失的黑色節(jié)點(diǎn)交由給右子節(jié)點(diǎn)，通過(guò)旋轉(zhuǎn)達(dá)到平衡。
** **通過(guò)上面的分析，我們已經(jīng)初步了解了紅黑樹(shù)的刪除節(jié)點(diǎn)情況，相對(duì)于增加節(jié)點(diǎn)而言它確實(shí)是選的較為復(fù)雜。下面我將看到在Java TreeMap中是如何實(shí)現(xiàn)紅黑樹(shù)刪除的。
TreeMap deleteEntry()方法實(shí)現(xiàn)分析
通過(guò)上面的分析我們確認(rèn)刪除節(jié)點(diǎn)的步驟是：找到一個(gè)替代子節(jié)點(diǎn)C來(lái)替代P，然后直接刪除C，最后調(diào)整這棵紅黑樹(shù)。下面代碼是尋找替代節(jié)點(diǎn)、刪除替代節(jié)點(diǎn)。
private void deleteEntry(Entry<K,V> p) {
modCount++; //修改次數(shù) +1
size--; //元素個(gè)數(shù) -1
/*
* 被刪除節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)都不為空，那么就用 p節(jié)點(diǎn)的中序后繼節(jié)點(diǎn)代替 p 節(jié)點(diǎn)
* successor(P)方法為尋找P的替代節(jié)點(diǎn)。規(guī)則是右分支最左邊，或者 左分支最右邊的節(jié)點(diǎn)
* ---------------------（1）
*/
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
}
//replacement為替代節(jié)點(diǎn)，如果P的左子樹(shù)存在那么就用左子樹(shù)替代，否則用右子樹(shù)替代
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
/*
* 刪除節(jié)點(diǎn)，分為上面提到的三種情況
* -----------------------（2）
*/
//如果替代節(jié)點(diǎn)不為空
if (replacement != null) {
replacement.parent = p.parent;
/*
*replacement來(lái)替代P節(jié)點(diǎn)
*/
//若P沒(méi)有父節(jié)點(diǎn)，則跟節(jié)點(diǎn)直接變成replacement
if (p.parent == null)
root = replacement;
//如果P為左節(jié)點(diǎn)，則用replacement來(lái)替代為左節(jié)點(diǎn)
else if (p == p.parent.left)
p.parent.left = replacement;
//如果P為右節(jié)點(diǎn)，則用replacement來(lái)替代為右節(jié)點(diǎn)
else
p.parent.right = replacement;
//同時(shí)將P節(jié)點(diǎn)從這棵樹(shù)中剔除掉
p.left = p.right = p.parent = null;
/*
* 若P為紅色直接刪除，紅黑樹(shù)保持平衡
* 但是若P為黑色，則需要調(diào)整紅黑樹(shù)使其保持平衡
*/
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { //p沒(méi)有父節(jié)點(diǎn)，表示為P根節(jié)點(diǎn)，直接刪除即可
root = null;
} else { //P節(jié)點(diǎn)不存在子節(jié)點(diǎn)，直接刪除即可
if (p.color == BLACK) //如果P節(jié)點(diǎn)的顏色為黑色，對(duì)紅黑樹(shù)進(jìn)行調(diào)整
fixAfterDeletion(p);
//刪除P節(jié)點(diǎn)
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;
}
}
}
（1）除是尋找替代節(jié)點(diǎn)replacement，其實(shí)現(xiàn)方法為successor()。如下：
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
/*
* 尋找右子樹(shù)的最左子樹(shù)
*/
else if (t.right != null) {
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
}
/*
* 選擇左子樹(shù)的最右子樹(shù)
*/
else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
（2）處是刪除該節(jié)點(diǎn)過(guò)程。它主要分為上面提到的三種情況，它與上面的if…else if… else一一對(duì)應(yīng) 。如下：
1、有兩個(gè)兒子。這種情況比較復(fù)雜，但還是比較簡(jiǎn)單。上面提到過(guò)用子節(jié)點(diǎn)C替代代替待刪除節(jié)點(diǎn)D，然后刪除子節(jié)點(diǎn)C即可。
2、沒(méi)有兒子，即為葉結(jié)點(diǎn)。直接把父結(jié)點(diǎn)的對(duì)應(yīng)兒子指針設(shè)為NULL，刪除兒子結(jié)點(diǎn)就OK了。
3、只有一個(gè)兒子。那么把父結(jié)點(diǎn)的相應(yīng)兒子指針指向兒子的獨(dú)生子，刪除兒子結(jié)點(diǎn)也OK了。
刪除完節(jié)點(diǎn)后，就要根據(jù)情況來(lái)對(duì)紅黑樹(shù)進(jìn)行復(fù)雜的調(diào)整：fixAfterDeletion()。
private void fixAfterDeletion(Entry<K,V> x) {
// 刪除節(jié)點(diǎn)需要一直迭代，知道 直到 x 不是根節(jié)點(diǎn)，且 x 的顏色是黑色
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) { //若X節(jié)點(diǎn)為左節(jié)點(diǎn)
//獲取其兄弟節(jié)點(diǎn)
Entry<K,V> sib = rightOf(parentOf(x));
/*
* 如果兄弟節(jié)點(diǎn)為紅色----（情況3.1）
* 策略：改變W、P的顏色，然后進(jìn)行一次左旋轉(zhuǎn)
*/
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
/*
* 若兄弟節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都為黑色----（情況3.2）
* 策略：將兄弟節(jié)點(diǎn)編程紅色
*/
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
}
else {
/*
* 如果兄弟節(jié)點(diǎn)只有右子樹(shù)為黑色----（情況3.3）
* 策略：將兄弟節(jié)點(diǎn)與其左子樹(shù)進(jìn)行顏色互換然后進(jìn)行右轉(zhuǎn)
* 這時(shí)情況會(huì)轉(zhuǎn)變?yōu)?.4
*/
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
/*
*----情況3.4
*策略：交換兄弟節(jié)點(diǎn)和父節(jié)點(diǎn)的顏色，
*同時(shí)將兄弟節(jié)點(diǎn)右子樹(shù)設(shè)置為黑色，最后左旋轉(zhuǎn)
*/
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
}
/**
* X節(jié)點(diǎn)為右節(jié)點(diǎn)與其為做節(jié)點(diǎn)處理過(guò)程差不多，這里就不在累述了
*/
else {
Entry<K,V> sib = leftOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
這是紅黑樹(shù)在刪除節(jié)點(diǎn)后，對(duì)樹(shù)的平衡性進(jìn)行調(diào)整的過(guò)程，其實(shí)現(xiàn)過(guò)程與上面四種復(fù)雜的情況一一對(duì)應(yīng)，所以在這個(gè)源碼的時(shí)候一定要對(duì)著上面提到的四種情況看。
五、寫在最后
** **這篇博文確實(shí)是有點(diǎn)兒長(zhǎng)，在這里非常感謝各位看客能夠靜下心來(lái)讀完，我想你通過(guò)讀完這篇博文一定收獲不小。同時(shí)這篇博文很大篇幅都在闡述紅黑樹(shù)的實(shí)現(xiàn)過(guò)程，對(duì)Java 的TreeMap聊的比較少，但是我認(rèn)為如果理解了紅黑樹(shù)的實(shí)現(xiàn)過(guò)程，對(duì)TreeMap那是手到擒來(lái)，小菜一碟。
** **同時(shí)這篇博文我寫了四天，看了、參考了大量的博文。同時(shí)不免會(huì)有些地方存在借鑒之處，在這里對(duì)其表示感謝。LZ大二開(kāi)始學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，自認(rèn)為學(xué)的不錯(cuò)，現(xiàn)在發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)我還有太多的地方需要學(xué)習(xí)了，同時(shí)也再一次體味了算法的魅力?。。?！
