TreeMap原理實(shí)現(xiàn)及常用方法

一. TreeMap概述

TreeMap存儲(chǔ)K-V鍵值對(duì)，通過(guò)紅黑樹（R-B tree）實(shí)現(xiàn)；
TreeMap繼承了NavigableMap接口，NavigableMap接口繼承了SortedMap接口，可支持一系列的導(dǎo)航定位以及導(dǎo)航操作的方法，當(dāng)然只是提供了接口，需要TreeMap自己去實(shí)現(xiàn)；
TreeMap實(shí)現(xiàn)了Cloneable接口，可被克隆，實(shí)現(xiàn)了Serializable接口，可序列化；
TreeMap因?yàn)槭峭ㄟ^(guò)紅黑樹實(shí)現(xiàn)，紅黑樹結(jié)構(gòu)天然支持排序，默認(rèn)情況下通過(guò)Key值的自然順序進(jìn)行排序；

二. 紅黑樹回顧

因?yàn)門reeMap的存儲(chǔ)結(jié)構(gòu)是紅黑樹，我們回顧一下紅黑樹的特點(diǎn)以及基本操作。下圖為典型的紅黑樹：
TreeMap原理實(shí)現(xiàn)及常用方法

站在用戶的角度思考問(wèn)題，與客戶深入溝通，找到哈巴河網(wǎng)站設(shè)計(jì)與哈巴河網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶體驗(yàn)好的作品，建站類型包括：網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、主機(jī)域名、雅安服務(wù)器托管、企業(yè)郵箱。業(yè)務(wù)覆蓋哈巴河地區(qū)。

紅黑樹規(guī)則特點(diǎn)：

節(jié)點(diǎn)分為紅色或者黑色；
根節(jié)點(diǎn)必為黑色；
葉子節(jié)點(diǎn)都為黑色，且為null；
連接紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都為黑色（紅黑樹不會(huì)出現(xiàn)相鄰的紅色節(jié)點(diǎn)）；
從任意節(jié)點(diǎn)出發(fā)，到其每個(gè)葉子節(jié)點(diǎn)的路徑中包含相同數(shù)量的黑色節(jié)點(diǎn)；
新加入到紅黑樹的節(jié)點(diǎn)為紅色節(jié)點(diǎn)；

紅黑樹自平衡基本操作：

變色：在不違反上述紅黑樹規(guī)則特點(diǎn)情況下，將紅黑樹某個(gè)node節(jié)點(diǎn)顏色由紅變黑，或者由黑變紅；
左旋：逆時(shí)針旋轉(zhuǎn)兩個(gè)節(jié)點(diǎn)，讓一個(gè)節(jié)點(diǎn)被其右子節(jié)點(diǎn)取代，而該節(jié)點(diǎn)成為右子節(jié)點(diǎn)的左子節(jié)點(diǎn)
右旋：順時(shí)針旋轉(zhuǎn)兩個(gè)節(jié)點(diǎn)，讓一個(gè)節(jié)點(diǎn)被其左子節(jié)點(diǎn)取代，而該節(jié)點(diǎn)成為左子節(jié)點(diǎn)的右子節(jié)點(diǎn)

三. TreeMap構(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的存儲(chǔ)結(jié)構(gòu)既然是紅黑樹，那么必然會(huì)有唯一的根節(jié)點(diǎn)。
 */
private transient Entry<K,V> root;

/**
 * Map中key-val對(duì)的數(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í)體，我們來(lái)看一下Entry類的源碼

static final class Entry<K,V> implements Map.Entry<K,V> {
    //key,val是存儲(chǔ)的原始數(shù)據(jù)
    K key;
    V value;
    //定義了節(jié)點(diǎn)的左孩子
    Entry<K,V> left;
    //定義了節(jié)點(diǎn)的右孩子
    Entry<K,V> right;
    //通過(guò)該節(jié)點(diǎn)可以反過(guò)來(lái)往上找到自己的父親
    Entry<K,V> parent;
    //默認(rèn)情況下為黑色節(jié)點(diǎn)，可調(diào)整
    boolean color = BLACK;

    /**
     * 構(gòu)造器
     */
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }

    /**
     * 獲取節(jié)點(diǎn)的key值
     */
    public K getKey() {return key;}

    /**
     * 獲取節(jié)點(diǎn)的value值
     */
    public V getValue() {return value;}

    /**
     * 用新值替換當(dāng)前值，并返回當(dāng)前值
     */
    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;
    }
}

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

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

TreeMap原理實(shí)現(xiàn)及常用方法

TreeMap構(gòu)造函數(shù)：

//默認(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) {
    }
}

四. put方法

put方法為Map的核心方法，TreeMap的put方法大概流程如下：

TreeMap原理實(shí)現(xiàn)及常用方法
我們來(lái)分析一下源碼

public V put(K key, V value) {
    Entry<K,V> t = root;
    /**
     * 如果根節(jié)點(diǎn)都為null，還沒(méi)建立起來(lái)紅黑樹，我們先new Entry并賦值給root把紅黑樹建立起來(lái)，這個(gè)時(shí)候紅
     * 黑樹中已經(jīng)有一個(gè)節(jié)點(diǎn)了，同時(shí)修改操作+1。
     */
    if (t == null) {
        compare(key, key); 
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    /**
     * 如果節(jié)點(diǎn)不為null,定義一個(gè)cmp，這個(gè)變量用來(lái)進(jìn)行二分查找時(shí)的比較；定義parent，是new Entry時(shí)必須
     * 要的參數(shù)
     */
    int cmp;
    Entry<K,V> parent;
    // cpr表示有無(wú)自己定義的排序規(guī)則，分兩種情況遍歷執(zhí)行
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        /**
         * 從root節(jié)點(diǎn)開始遍歷，通過(guò)二分查找逐步向下找
         * 第一次循環(huán)：從根節(jié)點(diǎn)開始，這個(gè)時(shí)候parent就是根節(jié)點(diǎn)，然后通過(guò)自定義的排序算法
         * 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)，逐步往下找
         *
         * 需要注意的是：這里并沒(méi)有對(duì)key是否為null進(jìn)行判斷，建議自己的實(shí)現(xiàn)Comparator時(shí)應(yīng)該要考慮在內(nèi)
         */
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {
        //從這里看出，當(dāng)默認(rèn)排序時(shí)，key值是不能為null的
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        //這里的實(shí)現(xiàn)邏輯和上面一樣，都是通過(guò)二分查找，就不再多說(shuō)了
        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);
    }
    /**
     * 能執(zhí)行到這里，說(shuō)明前面并沒(méi)有找到相同的key,節(jié)點(diǎn)已經(jīng)遍歷到最后了，我們只需要new一個(gè)Entry放到
     * parent下面即可，但放到左子節(jié)點(diǎn)上還是右子節(jié)點(diǎn)上，就需要按照紅黑樹的規(guī)則來(lái)。
     */
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    /**
     * 節(jié)點(diǎn)加進(jìn)去了，并不算完，我們?cè)谇懊婕t黑樹原理章節(jié)提到過(guò)，一般情況下加入節(jié)點(diǎn)都會(huì)對(duì)紅黑樹的結(jié)構(gòu)造成
     * 破壞，我們需要通過(guò)一些操作來(lái)進(jìn)行自動(dòng)平衡處置，如【變色】【左旋】【右旋】
     */
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

put方法源碼中通過(guò)fixAfterInsertion(e)方法來(lái)進(jìn)行自平衡處理，我們回顧一下插入時(shí)自平衡調(diào)整的邏輯

	無(wú)需調(diào)整	【變色】即可實(shí)現(xiàn)平衡	【旋轉(zhuǎn)+變色】才可實(shí)現(xiàn)平衡
情況1：	當(dāng)父節(jié)點(diǎn)為黑色時(shí)插入子節(jié)點(diǎn)	空樹插入根節(jié)點(diǎn)，將根節(jié)點(diǎn)紅色變?yōu)楹谏?/td>	父節(jié)點(diǎn)為紅色左節(jié)點(diǎn)，叔父節(jié)點(diǎn)為黑色，插入左子節(jié)點(diǎn)，那么通過(guò)【左左節(jié)點(diǎn)旋轉(zhuǎn)】
情況2：	-	父節(jié)點(diǎn)和叔父節(jié)點(diǎn)都為紅色	父節(jié)點(diǎn)為紅色左節(jié)點(diǎn)，叔父節(jié)點(diǎn)為黑色，插入右子節(jié)點(diǎn)，那么通過(guò)【左右節(jié)點(diǎn)旋轉(zhuǎn)】
情況3：	-	-	父節(jié)點(diǎn)為紅色右節(jié)點(diǎn)，叔父節(jié)點(diǎn)為黑色，插入左子節(jié)點(diǎn)，那么通過(guò)【右左節(jié)點(diǎn)旋轉(zhuǎn)】
情況4：	-	-	父節(jié)點(diǎn)為紅色右節(jié)點(diǎn)，叔父節(jié)點(diǎn)為黑色，插入右子節(jié)點(diǎn)，那么通過(guò)【右右節(jié)點(diǎn)旋轉(zhuǎn)】

接下來(lái)我們看一看這個(gè)方法

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)，對(duì)應(yīng)上表中情況1和情況2
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            //如果叔父節(jié)點(diǎn)為紅色，對(duì)應(yīng)于“父節(jié)點(diǎn)和叔父節(jié)點(diǎn)都為紅色”，此時(shí)通過(guò)變色即可實(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)，通過(guò)【左右節(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)】并沒(méi)有嚴(yán)格的先后順序，達(dá)成目的就行）
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            //父節(jié)點(diǎn)是右節(jié)點(diǎn)的情況
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            //對(duì)應(yīng)于“父節(jié)點(diǎn)和叔父節(jié)點(diǎn)都為紅色”，此時(shí)通過(guò)變色即可實(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)，通過(guò)【右左節(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)】并沒(méi)有嚴(yán)格的先后順序，達(dá)成目的就行）
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    //根節(jié)點(diǎn)必須為黑色
    root.color = BLACK;
}

源碼中通過(guò) rotateLeft 進(jìn)行【左旋】，通過(guò) 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沒(méi)有父節(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;
    }
}

就算是看了上面的注釋還是并不清晰，看下圖你就懂了

TreeMap原理實(shí)現(xiàn)及常用方法

五. get 方法

get方法是通過(guò)二分查找的思想，我們看一下源碼

public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}
/**
 * 從root節(jié)點(diǎn)開始遍歷，通過(guò)二分查找逐步向下找
 * 第一次循環(huán)：從根節(jié)點(diǎn)開始，這個(gè)時(shí)候parent就是根節(jié)點(diǎn)，然后通過(guò)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)開始遍歷，通過(guò)二分查找逐步向下找
 * 第一次循環(huán)：從根節(jié)點(diǎn)開始，這個(gè)時(shí)候parent就是根節(jié)點(diǎn)，然后通過(guò)自定義的排序算法
 * 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;
}

六. remove方法

remove方法可以分為兩個(gè)步驟，先是找到這個(gè)節(jié)點(diǎn)，直接調(diào)用了上面介紹的getEntry(Object key)，這個(gè)步驟我們就不說(shuō)了，直接說(shuō)第二個(gè)步驟，找到后的刪除操作。

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

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

通過(guò)deleteEntry(p)進(jìn)行刪除操作，刪除操作的原理我們?cè)谇懊嬉呀?jīng)講過(guò)

刪除的是根節(jié)點(diǎn)，則直接將根節(jié)點(diǎn)置為null;
待刪除節(jié)點(diǎn)的左右子節(jié)點(diǎn)都為null，刪除時(shí)將該節(jié)點(diǎn)置為null;
待刪除節(jié)點(diǎn)的左右子節(jié)點(diǎn)有一個(gè)有值，則用有值的節(jié)點(diǎn)替換該節(jié)點(diǎn)即可；
待刪除節(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í)，通過(guò)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(通過(guò)將節(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)都可能是紅色的，那么很明顯可能會(huì)存在紅色相連的情
         * 況，因此需要進(jìn)行自平衡的調(diào)整
         */
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) {//這種情況就不用多說(shuō)了吧
        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;
        }
    }
}

操作的操作其實(shí)很簡(jiǎn)單，場(chǎng)景也不多，我們看一下刪除后的自平衡操作方法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)，這兩種情況下面都是四種場(chǎng)景,這里通過(guò)
         * 代碼分析一下x為左節(jié)點(diǎn)的情況，右節(jié)點(diǎn)可參考左節(jié)點(diǎn)理解，因?yàn)樗鼈兎浅ｎ愃?         */
        if (x == leftOf(parentOf(x))) {
            Entry<K,V> sib = rightOf(parentOf(x));

            /**
             * 場(chǎng)景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));
            }

            /**
             * 場(chǎng)景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 {
                /**
                 * 場(chǎng)景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));
                }
                /**
                 * 場(chǎng)景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);
}

當(dāng)待操作節(jié)點(diǎn)為左節(jié)點(diǎn)時(shí)，上面描述了四種場(chǎng)景，而且場(chǎng)景之間可以相互轉(zhuǎn)換，如deleteEntry后進(jìn)入了場(chǎng)景1，經(jīng)過(guò)場(chǎng)景1的一些列操作后，紅黑樹的結(jié)構(gòu)并沒(méi)有調(diào)整完成，而是進(jìn)入了場(chǎng)景2，場(chǎng)景2執(zhí)行完成后跳出循環(huán)，將待操作節(jié)點(diǎn)設(shè)置為黑色，完成。我們下面用圖來(lái)說(shuō)明一下四種場(chǎng)景幫助理解，當(dāng)然大家最好自己手動(dòng)畫一下。

場(chǎng)景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)。

TreeMap原理實(shí)現(xiàn)及常用方法

但經(jīng)過(guò)這一系列操作后，并沒(méi)有結(jié)束，而是可能到了場(chǎng)景2，或者場(chǎng)景3和4

場(chǎng)景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)
TreeMap原理實(shí)現(xiàn)及常用方法

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

場(chǎng)景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)

TreeMap原理實(shí)現(xiàn)及常用方法

并沒(méi)有完，場(chǎng)景3的一系列操作后，會(huì)進(jìn)入到場(chǎng)景4

場(chǎng)景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

TreeMap原理實(shí)現(xiàn)及常用方法

四種場(chǎng)景講完了，刪除后的自平衡操作不太好理解，代碼層面的已經(jīng)弄明白了，但如果讓我自己去實(shí)現(xiàn)的話，還是差了一些，還需要再研究。

七. 遍歷

遍歷比較簡(jiǎn)單，TreeMap的遍歷可以使用map.values(), map.keySet()，map.entrySet()，map.forEach()，這里不再多說(shuō)。

八. 總結(jié)

本文詳細(xì)介紹了TreeMap的基本特點(diǎn)，并對(duì)其底層數(shù)據(jù)結(jié)構(gòu)紅黑樹進(jìn)行了回顧，同時(shí)講述了其自動(dòng)排序的原理，并從源碼的角度結(jié)合紅黑樹圖形對(duì)put方法、get方法、remove方法進(jìn)行了講解，最后簡(jiǎn)單提了一下遍歷操作，若有不對(duì)之處，請(qǐng)批評(píng)指正，望共同進(jìn)步，謝謝！

當(dāng)前文章：TreeMap原理實(shí)現(xiàn)及常用方法
路徑分享：http://www.muchs.cn/article26/phohcg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁(yè)設(shè)計(jì)公司、面包屑導(dǎo)航、網(wǎng)站改版、、網(wǎng)站策劃、外貿(mào)建站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容