TreeMap的實(shí)現(xiàn)是紅黑樹算法的實(shí)現(xiàn)捎稚，所以要了解TreeMap就必須對紅黑樹有一定的了解,其實(shí)這篇博文的名字叫做：根據(jù)紅黑樹的算法來分析TreeMap的實(shí)現(xiàn)乐横，但是為了與Java提高篇系列博文保持一致還是叫做TreeMap比較好。通過這篇博文你可以獲得如下知識點(diǎn)：
1今野、紅黑樹的基本概念葡公。
2、紅黑樹增加節(jié)點(diǎn)条霜、刪除節(jié)點(diǎn)的實(shí)現(xiàn)過程催什。
3、紅黑樹左旋轉(zhuǎn)宰睡、右旋轉(zhuǎn)的復(fù)雜過程蒲凶。
4气筋、Java 中TreeMap是如何通過put、deleteEntry兩個(gè)來實(shí)現(xiàn)紅黑樹增加旋圆、刪除節(jié)點(diǎn)的宠默。
我想通過這篇博文你對TreeMap一定有了更深的認(rèn)識。好了灵巧，下面先簡單普及紅黑樹知識搀矫。

一、紅黑樹簡介

紅黑樹又稱紅-黑二叉樹刻肄，它首先是一顆二叉樹瓤球，它具體二叉樹所有的特性。同時(shí)紅黑樹更是一顆自平衡的排序二叉樹敏弃。
我們知道一顆基本的二叉樹他們都需要滿足一個(gè)基本性質(zhì)--即樹中的任何節(jié)點(diǎn)的值大于它的左子節(jié)點(diǎn)冰垄，且小于它的右子節(jié)點(diǎn)。按照這個(gè)基本性質(zhì)使得樹的檢索效率大大提高权她。我們知道在生成二叉樹的過程是非常容易失衡的虹茶，最壞的情況就是一邊倒（只有右/左子樹），這樣勢必會導(dǎo)致二叉樹的檢索效率大大降低（O(n)）隅要，所以為了維持二叉樹的平衡蝴罪，大牛們提出了各種實(shí)現(xiàn)的算法，如：AVL步清，SBT要门，伸展樹，TREAP 廓啊，紅黑樹等等欢搜。
平衡二叉樹必須具備如下特性：它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對值不超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹谴轮。也就是說該二叉樹的任何一個(gè)等等子節(jié)點(diǎn)炒瘟，其左右子樹的高度都相近。

普通二叉樹和平衡二叉樹

這些約束強(qiáng)制了紅黑樹的關(guān)鍵性質(zhì): 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長藤肢。結(jié)果是這棵樹大致上是平衡的太闺。因?yàn)椴僮鞅热绮迦肱淳啊h除和查找某個(gè)值的最壞情況時(shí)間都要求與樹的高度成比例嘁圈，這個(gè)在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹最住。所以紅黑樹它是復(fù)雜而高效的，其檢索效率O(log n)履腋。下圖為一顆典型的紅黑二叉樹延旧。

對于紅黑二叉樹而言它主要包括三大基本操作：左旋旅急、右旋、著色躯嫉。

二、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)航方法，具備針對給定搜索目標(biāo)返回最接近匹配項(xiàng)的導(dǎo)航方法 筑悴。
** **TreeMap中同時(shí)也包含了如下幾個(gè)重要的屬性：

//比較器们拙，因?yàn)門reeMap是有序的，通過comparator接口我們可以對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;
        //紅黑樹的節(jié)點(diǎn)顏色--紅色
        private static final boolean RED = false;
        //紅黑樹的節(jié)點(diǎn)顏色--黑色
        private static final boolean BLACK = true;

對于葉子節(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;

注：前面只是開胃菜，下面是本篇博文的重中之重突勇，在下面兩節(jié)我將重點(diǎn)講解treeMap的put()装盯、delete()方法。通過這兩個(gè)方法我們會了解紅黑樹增加甲馋、刪除節(jié)點(diǎn)的核心算法埂奈。

** **三、TreeMap put()方法

** **在了解TreeMap的put()方法之前定躏，我們先了解紅黑樹增加節(jié)點(diǎn)的算法账磺。
** **紅黑樹增加節(jié)點(diǎn)
** **紅黑樹在新增節(jié)點(diǎn)過程中比較復(fù)雜海蔽，復(fù)雜歸復(fù)雜它同樣必須要依據(jù)上面提到的五點(diǎn)規(guī)范，同時(shí)由于規(guī)則1绑谣、2党窜、3基本都會滿足，下面我們主要討論規(guī)則4借宵、5幌衣。假設(shè)我們這里有一棵最簡單的樹，我們規(guī)定新增的節(jié)點(diǎn)為N壤玫、它的父節(jié)點(diǎn)為P豁护、P的兄弟節(jié)點(diǎn)為U、P的父節(jié)點(diǎn)為G欲间。

對于新節(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ì). 故插入算法就是通過重新著色或旋轉(zhuǎn), 來維持性質(zhì) 她渴。
為了保證下面的闡述更加清晰和根據(jù)便于參考达址，我這里將紅黑樹的五點(diǎn)規(guī)定再貼一遍：
![Uploading image_935926.png . . .]

一、為跟節(jié)點(diǎn)

若新插入的節(jié)點(diǎn)N沒有父節(jié)點(diǎn)趁耗，則直接當(dāng)做根據(jù)節(jié)點(diǎn)插入即可沉唠，同時(shí)將顏色設(shè)置為黑色。（如圖一（1））

二苛败、父節(jié)點(diǎn)為黑色

這種情況新節(jié)點(diǎn)N同樣是直接插入满葛，同時(shí)顏色為紅色，由于根據(jù)規(guī)則四它會存在兩個(gè)黑色的葉子節(jié)點(diǎn)罢屈，值為null嘀韧。同時(shí)由于新增節(jié)點(diǎn)N為紅色，所以通過它的子節(jié)點(diǎn)的路徑依然會保存著相同的黑色節(jié)點(diǎn)數(shù)儡遮，同樣滿足規(guī)則5乳蛾。（如圖一（2））

三、若父節(jié)點(diǎn)P和P的兄弟節(jié)點(diǎn)U都為紅色

對于這種情況若直接插入肯定會出現(xiàn)不平衡現(xiàn)象鄙币。怎么處理肃叶？P、U節(jié)點(diǎn)變黑十嘿、G節(jié)點(diǎn)變紅因惭。這時(shí)由于經(jīng)過節(jié)點(diǎn)P、U的路徑都必須經(jīng)過G所以在這些路徑上面的黑節(jié)點(diǎn)數(shù)目還是相同的绩衷。但是經(jīng)過上面的處理蹦魔，可能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)的右孩子

對于這種情況我們對新增節(jié)點(diǎn)N低缩、P進(jìn)行一次左旋轉(zhuǎn)嘉冒。這里所產(chǎn)生的結(jié)果其實(shí)并沒有完成，還不是平衡的（違反了規(guī)則四）咆繁，這是我們需要進(jìn)行情況5的操作讳推。

五、父節(jié)點(diǎn)P為紅色玩般，叔父節(jié)點(diǎn)U為黑色或者缺少银觅，新增節(jié)點(diǎn)N為父節(jié)點(diǎn)P左孩子

這種情況有可能是由于情況四而產(chǎn)生的，也有可能不是坏为。對于這種情況先已P節(jié)點(diǎn)為中心進(jìn)行右旋轉(zhuǎn)究驴，在旋轉(zhuǎn)后產(chǎn)生的樹中，節(jié)點(diǎn)P是節(jié)點(diǎn)N久脯、G的父節(jié)點(diǎn)纳胧。但是這棵樹并不規(guī)范镰吆，它違反了規(guī)則4帘撰，所以我們將P、G節(jié)點(diǎn)的顏色進(jìn)行交換万皿，使之其滿足規(guī)范摧找。開始時(shí)所有的路徑都需要經(jīng)過G其他們的黑色節(jié)點(diǎn)數(shù)一樣，但是現(xiàn)在所有的路徑改為經(jīng)過P牢硅，且P為整棵樹的唯一黑色節(jié)點(diǎn)蹬耘，所以調(diào)整后的樹同樣滿足規(guī)范5。

上面展示了紅黑樹新增節(jié)點(diǎn)的五種情況减余，這五種情況涵蓋了所有的新增可能综苔，不管這棵紅黑樹多么復(fù)雜，都可以根據(jù)這五種情況來進(jìn)行生成位岔。下面就來分析Java中的TreeMap是如何來實(shí)現(xiàn)紅黑樹的如筛。
TreeMap put()方法實(shí)現(xiàn)分析
在TreeMap的put()的實(shí)現(xiàn)方法中主要分為兩個(gè)步驟，第一：構(gòu)建排序二叉樹抒抬，第二：平衡二叉樹杨刨。
對于排序二叉樹的創(chuàng)建，其添加節(jié)點(diǎn)的過程如下：
1擦剑、以根節(jié)點(diǎn)為初始節(jié)點(diǎn)進(jìn)行檢索妖胀。
2芥颈、與當(dāng)前節(jié)點(diǎn)進(jìn)行比對，若新增節(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)行比對肉康，如果新增節(jié)點(diǎn)較大闯估，則添加為右子節(jié)點(diǎn)；否則添加為左子節(jié)點(diǎn)吼和。
按照這個(gè)步驟我們就可以將一個(gè)新增節(jié)點(diǎn)添加到排序二叉樹中合適的位置涨薪。如下：

public V put(K key, V value) {  
           //用t表示二叉樹的當(dāng)前節(jié)點(diǎn)  
            Entry<K,V> t = root;  
            //t為null表示一個(gè)空樹，即TreeMap中沒有任何元素炫乓，直接插入  
            if (t == null) {  
                //比較key值刚夺，個(gè)人覺得這句代碼沒有任何意義，空樹還需要比較末捣、排序侠姑？  
                compare(key, key); // type (and possibly null) check  
                //將新的key-value鍵值對創(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();  
                /* 下面處理過程和上面一樣 */  
                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)完成了排序二叉樹的的構(gòu)建氏身，將新增節(jié)點(diǎn)插入該樹中的合適位置  
             *  下面fixAfterInsertion()方法就是對這棵樹進(jìn)行調(diào)整巍棱、平衡，具體過程參考上面的五種情況  
             */  
            fixAfterInsertion(e);  
            //TreeMap元素?cái)?shù)量 + 1  
            size++;  
            //TreeMap容器修改次數(shù) + 1  
            modCount++;  
            return null;  
        }  

上面代碼中do{}代碼塊是實(shí)現(xiàn)排序二叉樹的核心算法观谦，通過該算法我們可以確認(rèn)新增節(jié)點(diǎn)在該樹的正確位置拉盾。找到正確位置后將插入即可，這樣做了其實(shí)還沒有完成豁状，因?yàn)槲抑繲reeMap的底層實(shí)現(xiàn)是紅黑樹捉偏，紅黑樹是一棵平衡排序二叉樹倒得，普通的排序二叉樹可能會出現(xiàn)失衡的情況，所以下一步就是要進(jìn)行調(diào)整夭禽。fixAfterInsertion(e); 調(diào)整的過程務(wù)必會涉及到紅黑樹的左旋霞掺、右旋、著色三個(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為黑色）；這里會存在兩種情況（情況四潮梯、情況五）  
                    else {     
                        //如果X節(jié)點(diǎn)為其父節(jié)點(diǎn)（P）的右子樹骗灶，則進(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為黑色）；這里會存在兩種情況（情況四秉馏、情況五）  
                    else {  
                        //如果X節(jié)點(diǎn)為其父節(jié)點(diǎn)（P）的右子樹耙旦，則進(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;  
        }  

對這段代碼的研究我們發(fā)現(xiàn),其處理過程完全符合紅黑樹新增節(jié)點(diǎn)的處理過程。所以在看這段代碼的過程一定要對紅黑樹的新增節(jié)點(diǎn)過程有了解萝究。在這個(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è)置為P的右子樹  
            p.right = r.left;  
            //若R的左子樹不為空舷暮，則將P設(shè)置為R左子樹的父親  
            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）的左子樹噩茄，則將R設(shè)置為P父節(jié)點(diǎn)(G)左子樹  
            else if (p.parent.left == p)  
                p.parent.left = r;  
            //否則R設(shè)置為P的父節(jié)點(diǎn)（G）的右子樹  
            else  
                p.parent.right = r;  
            //將P設(shè)置為R的左子樹  
            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的左子樹  
            Entry<K,V> l = p.left;  
            //將L的右子樹設(shè)置為P的左子樹  
            p.left = l.right;  
            //若L的右子樹不為空，則將P設(shè)置L的右子樹的父節(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é)點(diǎn)  
            if (p.parent == null)  
                root = l;  
            //若P為其父節(jié)點(diǎn)的右子樹凿菩，則將L設(shè)置為P的父節(jié)點(diǎn)的右子樹  
            else if (p.parent.right == p)  
                p.parent.right = l;  
            //否則將L設(shè)置為P的父節(jié)點(diǎn)的左子樹  
            else   
                p.parent.left = l;  
            //將P設(shè)置為L的右子樹  
            l.right = p;  
            //將L設(shè)置為P的父節(jié)點(diǎn)  
            p.parent = l;  
        }  
    }  

著色：setColor()
著色就是改變該節(jié)點(diǎn)的顏色，在紅黑樹中帜讲，它是依靠節(jié)點(diǎn)的顏色來維持平衡的衅谷。

private static <K,V> void setColor(Entry<K,V> p, boolean c) {  
        if (p != null)  
            p.color = c;  
    }  

** **四、TreeMap delete()方法

** 紅黑樹刪除節(jié)點(diǎn)
** 針對于紅黑樹的增加節(jié)點(diǎn)而言似将，刪除顯得更加復(fù)雜获黔，使原本就復(fù)雜的紅黑樹變得更加復(fù)雜蚀苛。同時(shí)刪除節(jié)點(diǎn)和增加節(jié)點(diǎn)一樣，同樣是找到刪除的節(jié)點(diǎn)玷氏，刪除之后調(diào)整紅黑樹堵未。但是這里的刪除節(jié)點(diǎn)并不是直接刪除，而是通過走了“彎路”通過一種捷徑來刪除的：找到被刪除的節(jié)點(diǎn)D的子節(jié)點(diǎn)C盏触，用C來替代D渗蟹，不是直接刪除D，因?yàn)镈被C替代了赞辩，直接刪除C即可雌芽。所以這里就將刪除父節(jié)點(diǎn)D的事情轉(zhuǎn)變?yōu)榱藙h除子節(jié)點(diǎn)C的事情，這樣處理就將復(fù)雜的刪除事件簡單化了辨嗽。子節(jié)點(diǎn)C的規(guī)則是：右分支最左邊膘怕，或者 左分支最右邊的。

紅-黑二叉樹刪除節(jié)點(diǎn)召庞，最大的麻煩是要保持 各分支黑色節(jié)點(diǎn)數(shù)目相等岛心。 因?yàn)槭莿h除，所以不用擔(dān)心存在顏色沖突問題——插入才會引起顏色沖突篮灼。
紅黑樹刪除節(jié)點(diǎn)同樣會分成幾種情況忘古，這里是按照待刪除節(jié)點(diǎn)有幾個(gè)兒子的情況來進(jìn)行分類：
1河闰、沒有兒子睬捶，即為葉結(jié)點(diǎn)。直接把父結(jié)點(diǎn)的對應(yīng)兒子指針設(shè)為NULL搞坝，刪除兒子結(jié)點(diǎn)就OK了娘荡。
2干旁、只有一個(gè)兒子。那么把父結(jié)點(diǎn)的相應(yīng)兒子指針指向兒子的獨(dú)生子炮沐，刪除兒子結(jié)點(diǎn)也OK了争群。
3、有兩個(gè)兒子大年。這種情況比較復(fù)雜换薄，但還是比較簡單。上面提到過用子節(jié)點(diǎn)C替代代替待刪除節(jié)點(diǎn)D翔试，然后刪除子節(jié)點(diǎn)C即可轻要。
下面就論各種刪除情況來進(jìn)行圖例講解，但是在講解之前請?jiān)试S我再次啰嗦一句垦缅，請時(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)都是黑的洽损。也就是說在一條路徑上不能出現(xiàn)相鄰的兩個(gè)紅色結(jié)點(diǎn)。
5革半、從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)碑定。
（注：已經(jīng)講三遍了，再不記住我就懷疑你是否適合搞IT了 O(∩_∩)O~）
誠然又官，既然刪除節(jié)點(diǎn)比較復(fù)雜延刘，那么在這里我們就約定一下規(guī)則：
1、下面要講解的刪除節(jié)點(diǎn)一定是實(shí)際要刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)（N）六敬，如前面提到的C。
2、下面提到的刪除節(jié)點(diǎn)的樹都是如下結(jié)構(gòu)垒酬，該結(jié)構(gòu)所選取的節(jié)點(diǎn)是待刪除節(jié)點(diǎn)的右樹的最左邊子節(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)行分析逞泄、處理到千。
情況一加矛、無子節(jié)點(diǎn)（紅色節(jié)點(diǎn)）
這種情況對該節(jié)點(diǎn)直接刪除即可辑奈，不會影響樹的結(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é)點(diǎn)替代待刪除節(jié)點(diǎn)乍迄，然后刪除子節(jié)點(diǎn)即可管引。如上圖（2.3）
情況三、有兩個(gè)子節(jié)點(diǎn)
這種情況可能會稍微有點(diǎn)兒復(fù)雜闯两。它需要找到一個(gè)替代待刪除節(jié)點(diǎn)（N）來替代它褥伴，然后刪除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子樹相對于其兄弟W子樹少一個(gè)黑色節(jié)點(diǎn)，這時(shí)我們可以將W置為紅色站宗。這樣闸准，N子樹與W子樹黑色節(jié)點(diǎn)一致，保持了平衡梢灭。如下

將W由黑轉(zhuǎn)變?yōu)榧t夷家，這樣就會導(dǎo)致新節(jié)點(diǎn)new N相對于它的兄弟節(jié)點(diǎn)會少一個(gè)黑色節(jié)點(diǎn)。但是如果new x為紅色敏释，我們直接將new x轉(zhuǎn)變?yōu)楹谏饪欤３终脴涞钠胶狻７駝t情況3.2 會轉(zhuǎn)變?yōu)榍闆r3.1颂暇、3.3缺谴、3.4中的一種。
情況3.3耳鸯、N的兄弟w是黑色的湿蛔，w的左孩子是紅色，w的右孩子是黑色县爬。
針對這種情況是將節(jié)點(diǎn)W和其左子節(jié)點(diǎn)進(jìn)行顏色交換阳啥，然后對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í)對P進(jìn)行左旋轉(zhuǎn)操作所踊。這樣就把左邊缺失的黑色節(jié)點(diǎn)給補(bǔ)回來了。同時(shí)將W的右子節(jié)點(diǎn)X2置黑概荷。這樣左右都達(dá)到了平衡秕岛。

** **個(gè)人認(rèn)為這四種情況比較難理解，首先他們都不是單一的某種情況误证，他們之間是可以進(jìn)行互轉(zhuǎn)的继薛。相對于其他的幾種情況，情況3.2比較好理解愈捅，僅僅只是一個(gè)顏色的轉(zhuǎn)變遏考，通過減少右子樹的一個(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通過轉(zhuǎn)變后可以化成情況3.4來進(jìn)行處理缕题，從這里可以看出情況3.4應(yīng)該最終結(jié)截歉。情況3.4、右子節(jié)點(diǎn)為紅色節(jié)點(diǎn)烟零，那么將缺失的黑色節(jié)點(diǎn)交由給右子節(jié)點(diǎn)瘪松，通過旋轉(zhuǎn)達(dá)到平衡。

** **通過上面的分析锨阿，我們已經(jīng)初步了解了紅黑樹的刪除節(jié)點(diǎn)情況宵睦，相對于增加節(jié)點(diǎn)而言它確實(shí)是選的較為復(fù)雜。下面我將看到在Java TreeMap中是如何實(shí)現(xiàn)紅黑樹刪除的墅诡。

TreeMap deleteEntry()方法實(shí)現(xiàn)分析

通過上面的分析我們確認(rèn)刪除節(jié)點(diǎn)的步驟是：找到一個(gè)替代子節(jié)點(diǎn)C來替代P壳嚎，然后直接刪除C，最后調(diào)整這棵紅黑樹末早。下面代碼是尋找替代節(jié)點(diǎn)烟馅、刪除替代節(jié)點(diǎn)。

private void deleteEntry(Entry<K,V> p) {  
        modCount++;      //修改次數(shù) +1  
        size--;          //元素個(gè)數(shù) -1  
  
        /* 
         * 被刪除節(jié)點(diǎn)的左子樹和右子樹都不為空然磷，那么就用 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的左子樹存在那么就用左子樹替代寡润，否則用右子樹替代  
        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來替代P節(jié)點(diǎn) 
             */  
            //若P沒有父節(jié)點(diǎn)，則跟節(jié)點(diǎn)直接變成replacement  
            if (p.parent == null)  
                root = replacement;  
            //如果P為左節(jié)點(diǎn)梭纹，則用replacement來替代為左節(jié)點(diǎn)  
            else if (p == p.parent.left)  
                p.parent.left  = replacement;  
          //如果P為右節(jié)點(diǎn)躲惰，則用replacement來替代為右節(jié)點(diǎn)  
            else  
                p.parent.right = replacement;  
  
            //同時(shí)將P節(jié)點(diǎn)從這棵樹中剔除掉  
            p.left = p.right = p.parent = null;  
  
            /* 
             * 若P為紅色直接刪除，紅黑樹保持平衡 
             * 但是若P為黑色栗柒，則需要調(diào)整紅黑樹使其保持平衡 
             */  
            if (p.color == BLACK)  
                fixAfterDeletion(replacement);  
        } else if (p.parent == null) {     //p沒有父節(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)的顏色為黑色，對紅黑樹進(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;  
        /* 
         * 尋找右子樹的最左子樹 
         */  
        else if (t.right != null) {  
            Entry<K,V> p = t.right;  
            while (p.left != null)  
                p = p.left;  
            return p;  
        }   
        /* 
         * 選擇左子樹的最右子樹 
         */  
        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)過程。它主要分為上面提到的三種情況锰提，它與上面的if…else if… else一一對應(yīng) 曙痘。如下：
1、有兩個(gè)兒子立肘。這種情況比較復(fù)雜边坤，但還是比較簡單。上面提到過用子節(jié)點(diǎn)C替代代替待刪除節(jié)點(diǎn)D谅年，然后刪除子節(jié)點(diǎn)C即可茧痒。
2、沒有兒子融蹂，即為葉結(jié)點(diǎn)旺订。直接把父結(jié)點(diǎn)的對應(yīng)兒子指針設(shè)為NULL，刪除兒子結(jié)點(diǎn)就OK了超燃。
3区拳、只有一個(gè)兒子。那么把父結(jié)點(diǎn)的相應(yīng)兒子指針指向兒子的獨(dú)生子意乓，刪除兒子結(jié)點(diǎn)也OK了樱调。
刪除完節(jié)點(diǎn)后，就要根據(jù)情況來對紅黑樹進(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)只有右子樹為黑色----（情況3.3） 
                     * 策略：將兄弟節(jié)點(diǎn)與其左子樹進(jìn)行顏色互換然后進(jìn)行右轉(zhuǎn) 
                     * 這時(shí)情況會轉(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è)置為黑色为障，最后左旋轉(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)處理過程差不多晦闰，這里就不在累述了 
             */  
            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);  
    }  

這是紅黑樹在刪除節(jié)點(diǎn)后放祟，對樹的平衡性進(jìn)行調(diào)整的過程，其實(shí)現(xiàn)過程與上面四種復(fù)雜的情況一一對應(yīng)呻右，所以在這個(gè)源碼的時(shí)候一定要對著上面提到的四種情況看跪妥。

五、寫在最后

** **這篇博文確實(shí)是有點(diǎn)兒長声滥，在這里非常感謝各位看客能夠靜下心來讀完眉撵，我想你通過讀完這篇博文一定收獲不小。同時(shí)這篇博文很大篇幅都在闡述紅黑樹的實(shí)現(xiàn)過程落塑，對Java 的TreeMap聊的比較少纽疟，但是我認(rèn)為如果理解了紅黑樹的實(shí)現(xiàn)過程，對TreeMap那是手到擒來憾赁，小菜一碟污朽。
** **同時(shí)這篇博文我寫了四天，看了龙考、參考了大量的博文蟆肆。同時(shí)不免會有些地方存在借鑒之處，在這里對其表示感謝晦款。LZ大二開始學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)炎功，自認(rèn)為學(xué)的不錯(cuò)，現(xiàn)在發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)我還有太多的地方需要學(xué)習(xí)了缓溅，同時(shí)也再一次體味了算法的魅力Ｉ咚稹！８厮巍州藕！