Java工程師知識樹 / Java基礎(chǔ)

TreeSet的底層是基于TreeMap，所以TreeSet的數(shù)據(jù)結(jié)構(gòu)就是TreeMap的數(shù)據(jù)結(jié)構(gòu)系馆，只是TreeSet的每個(gè)key對應(yīng)的value值都為TreeSet的成員變量private static final Object PRESENT = new Object();送漠。

不過TreeMap 和TreeSet 實(shí)現(xiàn)的接口規(guī)范不同。

TreeMap特點(diǎn)

TreeMap是Map集合的有序?qū)崿F(xiàn)由蘑，其底層是基于紅黑樹的實(shí)現(xiàn)闽寡，能夠在log(n) 時(shí)間內(nèi)完成 get、put 和 remove 操作尼酿，每個(gè)key-value都作為一個(gè)紅黑樹的節(jié)點(diǎn)爷狈。如果在調(diào)用TreeMap的構(gòu)造函數(shù)時(shí)沒有指定比較器，則根據(jù)key執(zhí)行自然排序裳擎，如果指定了比較器則按照比較器來進(jìn)行排序涎永。

TreeMap結(jié)構(gòu)

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

• Map：用來存儲鍵值對的，它是一個(gè)雙列數(shù)據(jù)結(jié)構(gòu)

• NavigableMap：擴(kuò)展的 SortedMap鹿响，具有了針對給定搜索目標(biāo)返回最接近匹配項(xiàng)的導(dǎo)航方法羡微。可以按照鍵的升序或降序訪問和遍歷 NavigableMap抢野。詳情請參考NavigableMap拷淘。

• AbstractMap：是個(gè)抽象類，抽象類一般用來提取一些共有的屬性指孤，AbstractMap包含了HashMap启涯，TreeMap，ConcurrentHashMap等Map集合類共同的屬性恃轩。AbstractMap有containsValue()结洼，containsKey()，get()叉跛，put()松忍，remove()，putAll()等方法筷厘。

• Cloneable：ArrayList 實(shí)現(xiàn)了Cloneable接口鸣峭，并覆蓋了函數(shù)clone()，能被克隆酥艳。

• Serializable：實(shí)現(xiàn)java.io.Serializable 接口后ArrayList支持序列化摊溶，能通過序列化去傳輸。

結(jié)構(gòu)示意圖:

TreeMap屬性

/**
 * TreeMap是可以自動(dòng)排序的充石，默認(rèn)情況下comparator為null莫换，
 * 這個(gè)時(shí)候按照key的自然順序進(jìn)行排序，然而并不是所有情況下都可以直接使用key的 
 * 自然順序，有時(shí)候我們想讓Map的自動(dòng)排序按照我們自己的規(guī)則拉岁，
 * 這個(gè)時(shí)候你就需要傳遞Comparator的實(shí)現(xiàn)類
 */
private final Comparator<? super K> comparator;

/**
 * TreeMap的存儲結(jié)構(gòu)既然是紅黑樹坷剧，那么必然會有唯一的根節(jié)點(diǎn)。
 */
private transient Entry<K,V> root;

/**
 * Map中key-val對的數(shù)量喊暖，也即是紅黑樹中節(jié)點(diǎn)Entry的數(shù)量
 */
private transient int size = 0;

/**
 * 紅黑樹結(jié)構(gòu)的調(diào)整次數(shù)
 */
private transient int modCount = 0;

主要成員變量為根節(jié)點(diǎn)root是Entry 類的實(shí)體惫企。

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;    //鍵
    V value;    //值
    Entry<K,V> left = null;     //左孩子節(jié)點(diǎn)
    Entry<K,V> right = null;    //右孩子節(jié)點(diǎn)
    Entry<K,V> parent;          //父節(jié)點(diǎn)
    boolean color = BLACK;      //節(jié)點(diǎn)的顏色，在紅黑樹種哄啄，只有兩種顏色雅任，紅色和黑色

    //構(gòu)造方法风范，用指定的key,value ,parent初始化，color默認(rèn)為黑色
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }

    //返回key
    public K getKey() {
        return key;
    }

    //返回該節(jié)點(diǎn)對應(yīng)的value
    public V getValue() {
        return value;
    }

    //替換節(jié)點(diǎn)的值，并返回舊值
    public V setValue(V value) {
        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }
    //重寫equals()方法
    public boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>)o;
        //兩個(gè)節(jié)點(diǎn)的key相等腔召，value相等俗慈，這兩個(gè)節(jié)點(diǎn)才相等
        return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
    }
    //重寫hashCode()方法
    public int hashCode() {
        int keyHash = (key==null ? 0 : key.hashCode());
        int valueHash = (value==null ? 0 : value.hashCode());
        //key和vale hash值得異或運(yùn)算，相同則為零寇漫，不同則為1 
        return keyHash ^ valueHash;
    }
    //重寫toString()方法
    public String toString() {
        return key + "=" + value;
    }
}

解釋說明：

Entry靜態(tài)內(nèi)部類實(shí)現(xiàn)了Map的內(nèi)部接口Entry刊殉，提供了紅黑樹存儲結(jié)構(gòu)的java實(shí)現(xiàn)，通過left屬性可以建立左子樹州胳，通過right屬性可以建立右子樹，通過parent可以往上找到父節(jié)點(diǎn)。

大體的實(shí)現(xiàn)結(jié)構(gòu)圖如下：

TreeMap構(gòu)造方法

//默認(rèn)構(gòu)造函數(shù)瓢颅，按照key的自然順序排列
public TreeMap() {comparator = null;}
//傳遞Comparator具體實(shí)現(xiàn)，按照該實(shí)現(xiàn)規(guī)則進(jìn)行排序
public TreeMap(Comparator<? super K> comparator) {this.comparator = comparator;}
//傳遞一個(gè)map實(shí)體構(gòu)建TreeMap,按照默認(rèn)規(guī)則排序
public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}
//傳遞一個(gè)map實(shí)體構(gòu)建TreeMap,按照傳遞的map的排序規(guī)則進(jìn)行排序
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) {
    }
}

TreeMap提供了四個(gè)構(gòu)造方法，實(shí)現(xiàn)了方法的重載渔嚷。無參構(gòu)造方法中比較器的值為null,采用自然排序的方法圃伶，如果指定了比較器則稱之為定制排序。

TreeMap方法分析

類源碼方法層面的分析最好的方法是使用Debug一步步走一遍該方法搀罢。

get(Object key)方法

public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}
/**
 * 從root節(jié)點(diǎn)開始遍歷榔至，通過二分查找逐步向下找
 * 第一次循環(huán)：從根節(jié)點(diǎn)開始，這個(gè)時(shí)候parent就是根節(jié)點(diǎn)枫弟，然后通過k.compareTo(p.key)比較傳入的key和
 * 根節(jié)點(diǎn)的key值；
 * 如果傳入的key<root.key, 那么繼續(xù)在root的左子樹中找韩容，從root的左孩子節(jié)點(diǎn)（root.left）開始；
 * 如果傳入的key>root.key, 那么繼續(xù)在root的右子樹中找请梢，從root的右孩子節(jié)點(diǎn)（root.right）開始;
 * 如果恰好key==root.key，那么直接根據(jù)root節(jié)點(diǎn)的value值即可。
 * 后面的循環(huán)規(guī)則一樣咆霜，當(dāng)遍歷到的當(dāng)前節(jié)點(diǎn)作為起始節(jié)點(diǎn)，逐步往下找
 */
//默認(rèn)排序情況下的查找
final Entry<K,V> getEntry(Object key) {
    
    if (comparator != null)
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
    Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}
/**
 * 從root節(jié)點(diǎn)開始遍歷脉课，通過二分查找逐步向下找
 * 第一次循環(huán)：從根節(jié)點(diǎn)開始唱遭，這個(gè)時(shí)候parent就是根節(jié)點(diǎn)呈驶，然后通過自定義的排序算法
 * cpr.compare(key, t.key)比較傳入的key和根節(jié)點(diǎn)的key值司致，如果傳入的key<root.key脂矫，那么
 * 繼續(xù)在root的左子樹中找，從root的左孩子節(jié)點(diǎn)（root.left）開始：如果傳入的key>root.key,
 * 那么繼續(xù)在root的右子樹中找，從root的右孩子節(jié)點(diǎn)（root.right）開始;如果恰好key==root.key，
 * 那么直接根據(jù)root節(jié)點(diǎn)的value值即可谷浅。
 * 后面的循環(huán)規(guī)則一樣，當(dāng)遍歷到的當(dāng)前節(jié)點(diǎn)作為起始節(jié)點(diǎn)掌猛，逐步往下找
 */
//自定義排序規(guī)則下的查找
final Entry<K,V> getEntryUsingComparator(Object key) {
    @SuppressWarnings("unchecked")
    K k = (K) key;
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = cpr.compare(k, p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
    }
    return null;
}

方法思路：二分查找的思想

put(K key, V value)方法

public V put(K key, V value) {
    Entry<K,V> t = root;//紅黑樹的根節(jié)點(diǎn)
    /**
     * 如果根節(jié)點(diǎn)都為null眉睹，還沒建立起來紅黑樹竹海，我們先new Entry并賦值給root把紅黑樹建立起來孔飒，這個(gè)時(shí)候紅
     * 黑樹中已經(jīng)有一個(gè)節(jié)點(diǎn)了坏瞄，同時(shí)修改操作+1惦积。
     */
    if (t == null) {//紅黑樹是否為空
        compare(key, key); 
        root = new Entry<>(key, value, null);//構(gòu)造根節(jié)點(diǎn)蛛勉，因?yàn)楦?jié)點(diǎn)沒有父節(jié)點(diǎn)，傳入null值侣诵。 
        size = 1;//size值加1
        modCount++;//改變修改的次數(shù)
        return null;//返回null 
    }
    /**
     * 如果節(jié)點(diǎn)不為null,定義一個(gè)cmp躬络，這個(gè)變量用來進(jìn)行二分查找時(shí)的比較淹禾；定義parent，是new Entry時(shí)必須
     * 要的參數(shù)
     */
    int cmp;
    Entry<K,V> parent;//定義節(jié)點(diǎn)
    // cpr表示有無自己定義的排序規(guī)則蜓洪，分兩種情況遍歷執(zhí)行
    Comparator<? super K> cpr = comparator;//獲取比較器
    if (cpr != null) {//如果定義了比較器纤勒，采用自定義比較器進(jìn)行比較
        /**
         * 從root節(jié)點(diǎn)開始遍歷隆檀，通過二分查找逐步向下找
         * 第一次循環(huán)：從根節(jié)點(diǎn)開始腕让，這個(gè)時(shí)候parent就是根節(jié)點(diǎn)，然后通過自定義的排序算法
         * cpr.compare(key, t.key)比較傳入的key和根節(jié)點(diǎn)的key值庸蔼，如果傳入的key<root.key隙疚，那么
         * 繼續(xù)在root的左子樹中找，從root的左孩子節(jié)點(diǎn)（root.left）開始：如果傳入的key>root.key,
         * 那么繼續(xù)在root的右子樹中找磕道，從root的右孩子節(jié)點(diǎn)（root.right）開始;如果恰好key==root.key供屉，
         * 那么直接根據(jù)root節(jié)點(diǎn)的value值即可。
         * 后面的循環(huán)規(guī)則一樣溺蕉，當(dāng)遍歷到的當(dāng)前節(jié)點(diǎn)作為起始節(jié)點(diǎn)伶丐，逐步往下找
         *
         * 需要注意的是：這里并沒有對key是否為null進(jìn)行判斷，建議自己的實(shí)現(xiàn)Comparator時(shí)應(yīng)該要考慮在內(nèi)
         */
        do {
            parent = t; //將紅黑樹根節(jié)點(diǎn)賦值給parent
            cmp = cpr.compare(key, t.key);  //比較key, 與根節(jié)點(diǎn)的大小
            if (cmp < 0)    //如果key < t.key , 指向左子樹
                t = t.left; //t = t.left  , t == 它的做孩子節(jié)點(diǎn)
            else if (cmp > 0)
                t = t.right;    //如果key > t.key , 指向它的右孩子節(jié)點(diǎn)
            else
                return t.setValue(value);    //如果它們相等疯特，替換key的值
        } while (t != null);    //循環(huán)遍歷
    }
    else {
        //從這里看出哗魂，當(dāng)默認(rèn)排序時(shí)，key值是不能為null的 也就是說漓雅，treeMap的Key值不能為null
        if (key == null)
            throw new NullPointerException();
       
        Comparable<? super K> k = (Comparable<? super K>) key;//類型轉(zhuǎn)換
        //這里的實(shí)現(xiàn)邏輯和上面一樣录别，都是通過二分查找
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)    // key < t.key 
                t = t.left; //左孩子
            else if (cmp > 0)   // key > t.key 
                t = t.right;    //右孩子
            else
                return t.setValue(value);    //t == t.key , 替換value值
        } while (t != null);
    }
    /**
     * 能執(zhí)行到這里朽色，說明前面并沒有找到相同的key,節(jié)點(diǎn)已經(jīng)遍歷到最后了，只需要new一個(gè)Entry放到
     * parent下面即可组题，但放到左子節(jié)點(diǎn)上還是右子節(jié)點(diǎn)上葫男，就需要按照紅黑樹的規(guī)則來。
     */
    Entry<K,V> e = new Entry<>(key, value, parent); //創(chuàng)建新節(jié)點(diǎn)崔列，并制定父節(jié)點(diǎn)
    //根據(jù)比較結(jié)果梢褐，決定新節(jié)點(diǎn)為父節(jié)點(diǎn)的左孩子或者右孩子
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    /**
     * 節(jié)點(diǎn)加進(jìn)去了，并不算完赵讯，一般情況下加入節(jié)點(diǎn)都會對紅黑樹的結(jié)構(gòu)造成
     * 破壞盈咳，需要通過一些操作來進(jìn)行自動(dòng)平衡處置，如【變色】【左旋】【右旋】
     */
    fixAfterInsertion(e);//新插入節(jié)點(diǎn)后重新調(diào)整紅黑樹 
    size++;
    modCount++;
    return null;
}

---------------------------------------

//比較方法瘦癌，如果comparator==null ,采用comparable.compartTo進(jìn)行比較猪贪，否則采用指定比較器比較大小
final int compare(Object k1, Object k2) {
    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}

put方法源碼中通過fixAfterInsertion(e)方法來進(jìn)行自平衡處理,插入時(shí)自平衡調(diào)整的邏輯:

private void fixAfterInsertion(Entry<K,V> x) {
    //新插入的節(jié)點(diǎn)為紅色節(jié)點(diǎn)
    x.color = RED;
    //我們知道父節(jié)點(diǎn)為黑色時(shí)镊屎，并不需要進(jìn)行樹結(jié)構(gòu)調(diào)整惹挟，只有當(dāng)父節(jié)點(diǎn)為紅色時(shí)，才需要調(diào)整
    while (x != null && x != root && x.parent.color == RED) {
        //如果父節(jié)點(diǎn)是左節(jié)點(diǎn)缝驳，對應(yīng)上表中情況1和情況2
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            //如果叔父節(jié)點(diǎn)為紅色连锯，對應(yīng)于“父節(jié)點(diǎn)和叔父節(jié)點(diǎn)都為紅色”，此時(shí)通過變色即可實(shí)現(xiàn)平衡
            //此時(shí)父節(jié)點(diǎn)和叔父節(jié)點(diǎn)都設(shè)置為黑色用狱，祖父節(jié)點(diǎn)設(shè)置為紅色
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                //如果插入節(jié)點(diǎn)是黑色运怖，插入的是右子節(jié)點(diǎn)，通過【左右節(jié)點(diǎn)旋轉(zhuǎn)】（這里先進(jìn)行父節(jié)點(diǎn)左旋）
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                //設(shè)置父節(jié)點(diǎn)和祖父節(jié)點(diǎn)顏色
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                //進(jìn)行祖父節(jié)點(diǎn)右旋（這里【變色】和【旋轉(zhuǎn)】并沒有嚴(yán)格的先后順序夏伊，達(dá)成目的就行）
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            //父節(jié)點(diǎn)是右節(jié)點(diǎn)的情況
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            //對應(yīng)于“父節(jié)點(diǎn)和叔父節(jié)點(diǎn)都為紅色”摇展，此時(shí)通過變色即可實(shí)現(xiàn)平衡
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                //如果插入節(jié)點(diǎn)是黑色，插入的是左子節(jié)點(diǎn)署海，通過【右左節(jié)點(diǎn)旋轉(zhuǎn)】（這里先進(jìn)行父節(jié)點(diǎn)右旋）
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                //進(jìn)行祖父節(jié)點(diǎn)左旋（這里【變色】和【旋轉(zhuǎn)】并沒有嚴(yán)格的先后順序吗购，達(dá)成目的就行）
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    //根節(jié)點(diǎn)必須為黑色
    root.color = BLACK;
}

源碼中通過 rotateLeft 進(jìn)行【左旋】医男，通過 rotateRight 進(jìn)行【右旋】。都非常類似捻勉，我們就看一下【左旋】的代碼镀梭，【左旋】規(guī)則如下：“逆時(shí)針旋轉(zhuǎn)兩個(gè)節(jié)點(diǎn)，讓一個(gè)節(jié)點(diǎn)被其右子節(jié)點(diǎn)取代踱启，而該節(jié)點(diǎn)成為右子節(jié)點(diǎn)的左子節(jié)點(diǎn)”报账。

private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        /**
         * 斷開當(dāng)前節(jié)點(diǎn)p與其右子節(jié)點(diǎn)的關(guān)聯(lián)，重新將節(jié)點(diǎn)p的右子節(jié)點(diǎn)的地址指向節(jié)點(diǎn)p的右子節(jié)點(diǎn)的左子節(jié)點(diǎn)
         * 這個(gè)時(shí)候節(jié)點(diǎn)r沒有父節(jié)點(diǎn)
         */
        Entry<K,V> r = p.right;
        p.right = r.left;
        //將節(jié)點(diǎn)p作為節(jié)點(diǎn)r的父節(jié)點(diǎn)
        if (r.left != null)
            r.left.parent = p;
        //將節(jié)點(diǎn)p的父節(jié)點(diǎn)和r的父節(jié)點(diǎn)指向同一處
        r.parent = p.parent;
        //p的父節(jié)點(diǎn)為null埠偿，則將節(jié)點(diǎn)r設(shè)置為root
        if (p.parent == null)
            root = r;
        //如果節(jié)點(diǎn)p是左子節(jié)點(diǎn)透罢，則將該左子節(jié)點(diǎn)替換為節(jié)點(diǎn)r
        else if (p.parent.left == p)
            p.parent.left = r;
        //如果節(jié)點(diǎn)p為右子節(jié)點(diǎn)，則將該右子節(jié)點(diǎn)替換為節(jié)點(diǎn)r
        else
            p.parent.right = r;
        //重新建立p與r的關(guān)系
        r.left = p;
        p.parent = r;
    }
}

如圖：

remove(Object key)方法

remove方法可以分為兩個(gè)步驟冠蒋，先是找到這個(gè)節(jié)點(diǎn)羽圃，直接調(diào)用了getEntry(Object key)，然后進(jìn)行刪除操作抖剿。

public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}

方法deleteEntry(Entry<K,V> p)內(nèi)的邏輯：

1. 刪除的是根節(jié)點(diǎn)朽寞，則直接將根節(jié)點(diǎn)置為null
2. 待刪除節(jié)點(diǎn)的左右子節(jié)點(diǎn)都為null，刪除時(shí)將該節(jié)點(diǎn)置為null
3. 待刪除節(jié)點(diǎn)的左右子節(jié)點(diǎn)有一個(gè)有值斩郎，則用有值的節(jié)點(diǎn)替換該節(jié)點(diǎn)即可
4. 待刪除節(jié)點(diǎn)的左右子節(jié)點(diǎn)都不為null脑融，則找前驅(qū)或者后繼，將前驅(qū)或者后繼的值復(fù)制到該節(jié)點(diǎn)中缩宜，然后刪除前驅(qū)或者后繼（前驅(qū)：左子樹中值最大的節(jié)點(diǎn)肘迎，后繼：右子樹中值最小的節(jié)點(diǎn)）

private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;
    //當(dāng)左右子節(jié)點(diǎn)都不為null時(shí)，通過successor(p)遍歷紅黑樹找到前驅(qū)或者后繼
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p);
        //將前驅(qū)或者后繼的key和value復(fù)制到當(dāng)前節(jié)點(diǎn)p中锻煌，然后刪除節(jié)點(diǎn)s(通過將節(jié)點(diǎn)p引用指向s)
        p.key = s.key;
        p.value = s.value;
        p = s;
    } 
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    /**
     * 至少有一個(gè)子節(jié)點(diǎn)不為null妓布，直接用這個(gè)有值的節(jié)點(diǎn)替換掉當(dāng)前節(jié)點(diǎn)，給replacement的parent屬性賦值,給
     * parent節(jié)點(diǎn)的left屬性和right屬性賦值宋梧，同時(shí)要記住葉子節(jié)點(diǎn)必須為null,然后用fixAfterDeletion方法
     * 進(jìn)行自平衡處理
     */
    if (replacement != null) {
        //將待刪除節(jié)點(diǎn)的子節(jié)點(diǎn)掛到待刪除節(jié)點(diǎn)的父節(jié)點(diǎn)上秋茫。
        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;
        p.left = p.right = p.parent = null;
        /**
         * p如果是紅色節(jié)點(diǎn)的話，那么其子節(jié)點(diǎn)replacement必然為紅色的乃秀，并不影響紅黑樹的結(jié)構(gòu)
         * 但如果p為黑色節(jié)點(diǎn)的話，那么其父節(jié)點(diǎn)以及子節(jié)點(diǎn)都可能是紅色的圆兵，那么很明顯可能會存在紅色相連的情
         * 況跺讯，因此需要進(jìn)行自平衡的調(diào)整
         */
        if (p.color == BLACK)
            fixAfterDeletion(replacement);// 恢復(fù)顏色分配
    } else if (p.parent == null) {//紅黑書中父節(jié)點(diǎn)為空的只能是根節(jié)點(diǎn)。
        root = null;
    } else { 
        /**
         * 如果p節(jié)點(diǎn)為黑色殉农，那么p節(jié)點(diǎn)刪除后刀脏，就可能違背每個(gè)節(jié)點(diǎn)到其葉子節(jié)點(diǎn)路徑上黑色節(jié)點(diǎn)數(shù)量一致的規(guī)則，
         * 因此需要進(jìn)行自平衡的調(diào)整
         */ 
        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;
        }
    }
}
// 刪除后的自平衡操作方法fixAfterDeletion
private void fixAfterDeletion(Entry<K,V> x) {
    /**
     * 當(dāng)x不是root節(jié)點(diǎn)且顏色為黑色時(shí)
     */
    while (x != root && colorOf(x) == BLACK) {
        /**
         * 首先分為兩種情況超凳，當(dāng)前節(jié)點(diǎn)x是左節(jié)點(diǎn)或者當(dāng)前節(jié)點(diǎn)x是右節(jié)點(diǎn)愈污，這兩種情況下面都是四種場景,這里通過
         * 代碼分析一下x為左節(jié)點(diǎn)的情況耀态，右節(jié)點(diǎn)可參考左節(jié)點(diǎn)理解，因?yàn)樗鼈兎浅ｎ愃?         */
        if (x == leftOf(parentOf(x))) {
            Entry<K,V> sib = rightOf(parentOf(x));

            /**
             * 場景1：當(dāng)x是左黑色節(jié)點(diǎn)暂雹，兄弟節(jié)點(diǎn)sib是紅色節(jié)點(diǎn)
             * 兄弟節(jié)點(diǎn)由紅轉(zhuǎn)黑首装，父節(jié)點(diǎn)由黑轉(zhuǎn)紅，按父節(jié)點(diǎn)左旋系奉，
             * 左旋后樹的結(jié)構(gòu)變化了，這時(shí)重新賦值sib萌踱，這個(gè)時(shí)候sib指向了x的兄弟節(jié)點(diǎn)
             */
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateLeft(parentOf(x));
                sib = rightOf(parentOf(x));
            }

            /**
             * 場景2：節(jié)點(diǎn)x虫蝶、x的兄弟節(jié)點(diǎn)sib倦西、sib的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)都為黑色時(shí)能真，需要將該節(jié)點(diǎn)sib由黑變
             * 紅，同時(shí)將x指向當(dāng)前x的父節(jié)點(diǎn)
             */
            if (colorOf(leftOf(sib))  == BLACK &&
                colorOf(rightOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                /**
                 * 場景3：節(jié)點(diǎn)x扰柠、x的兄弟節(jié)點(diǎn)sib、sib的右子節(jié)點(diǎn)都為黑色卤档，sib的左子節(jié)點(diǎn)為紅色時(shí)蝙泼，
                 * 需要將sib左子節(jié)點(diǎn)設(shè)置為黑色，sib節(jié)點(diǎn)設(shè)置為紅色，同時(shí)按sib右旋，再將sib指向x的
                 * 兄弟節(jié)點(diǎn)
                 */
                if (colorOf(rightOf(sib)) == BLACK) {
                    setColor(leftOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateRight(sib);
                    sib = rightOf(parentOf(x));
                }
                /**
                 * 場景4：節(jié)點(diǎn)x、x的兄弟節(jié)點(diǎn)sib都為黑色，而sib的左右子節(jié)點(diǎn)都為紅色或者右子節(jié)點(diǎn)為紅色橱健、
                 * 左子節(jié)點(diǎn)為黑色珊皿，此時(shí)需要將sib節(jié)點(diǎn)的顏色設(shè)置成和x的父節(jié)點(diǎn)p相同的顏色驶兜，
                 * 設(shè)置x的父節(jié)點(diǎn)為黑色扼仲，設(shè)置sib右子節(jié)點(diǎn)為黑色，左旋x的父節(jié)點(diǎn)p抄淑，然后將x賦值為root
                 */
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(rightOf(sib), BLACK);
                rotateLeft(parentOf(x));
                x = root;
            }
        } else {//x是右節(jié)點(diǎn)的情況
            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);
}

場景1：

當(dāng)x是左黑色節(jié)點(diǎn)唉韭，兄弟節(jié)點(diǎn)sib是紅色節(jié)點(diǎn)，需要兄弟節(jié)點(diǎn)由紅轉(zhuǎn)黑，父節(jié)點(diǎn)由黑轉(zhuǎn)紅栖秕，按父節(jié)點(diǎn)左旋，左旋后樹的結(jié)構(gòu)變化了簇捍，這時(shí)重新賦值sib只壳，這個(gè)時(shí)候sib指向了x的兄弟節(jié)點(diǎn)。

但經(jīng)過這一系列操作后，并沒有結(jié)束驹愚，而是可能到了場景2远搪，或者場景3和4

場景2：

節(jié)點(diǎn)x、x的兄弟節(jié)點(diǎn)sib逢捺、sib的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)都為黑色時(shí)谁鳍，需要將該節(jié)點(diǎn)sib由黑變紅，同時(shí)將x指向當(dāng)前x的父節(jié)點(diǎn)

經(jīng)過場景2的一系列操作后劫瞳，循環(huán)就結(jié)束了倘潜，我們跳出循環(huán)，將節(jié)點(diǎn)x設(shè)置為黑色志于，自平衡調(diào)整完成涮因。

場景3：

節(jié)點(diǎn)x、x的兄弟節(jié)點(diǎn)sib伺绽、sib的右子節(jié)點(diǎn)都為黑色养泡，sib的左子節(jié)點(diǎn)為紅色時(shí)，需要將sib左子節(jié)點(diǎn)設(shè)置為黑色憔恳，sib節(jié)點(diǎn)設(shè)置為紅色瓤荔，同時(shí)按sib右旋，再將sib指向x的兄弟節(jié)點(diǎn)

并沒有完钥组，場景3的一系列操作后输硝，會進(jìn)入到場景4

場景4：

節(jié)點(diǎn)x、x的兄弟節(jié)點(diǎn)sib都為黑色程梦，而sib的左右子節(jié)點(diǎn)都為紅色或者右子節(jié)點(diǎn)為紅色点把、左子節(jié)點(diǎn)為黑色，此時(shí)需要將sib節(jié)點(diǎn)的顏色設(shè)置成和x的父節(jié)點(diǎn)p相同的顏色屿附，設(shè)置x的父節(jié)點(diǎn)顏色為黑色郎逃，設(shè)置sib右孩子的顏色為黑色，左旋x的父節(jié)點(diǎn)p挺份，然后將x賦值為root