腳本之家服務器常用軟件

快捷導航

JDK集合源碼之解析TreeMap(二)

更新時間：2021年07月06日 17:25:22 作者：興趣使然的草帽路飛

下面小編就為大家?guī)硪黄獪\談java中的TreeMap 排序與TreeSet 排序。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧

刪除元素

刪除元素本身比較簡單，就是采用二叉樹的刪除規(guī)則。

如果刪除的位置有兩個葉子節(jié)點，則從其右子樹中取最小的元素放到刪除的位置，然后把刪除位置移到替代元素的位置，進入下一步。
如果刪除的位置只有一個葉子節(jié)點（有可能是經(jīng)過第一步轉(zhuǎn)換后的刪除位置），則把那個葉子節(jié)點作為替代元素，放到刪除的位置，然后把這個葉子節(jié)點刪除。
如果刪除的位置沒有葉子節(jié)點，則直接把這個刪除位置的元素刪除即可。
針對紅黑樹，如果刪除位置是黑色節(jié)點，還需要做再平衡。
如果有替代元素，則以替代元素作為當前節(jié)點進入再平衡。
如果沒有替代元素，則以刪除的位置的元素作為當前節(jié)點進入再平衡，平衡之后再刪除這個節(jié)點。

public V remove(Object key) {
    // 獲取節(jié)點
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;
    V oldValue = p.value;
    // 刪除節(jié)點
    deleteEntry(p);
    // 返回刪除的value
    return oldValue;
}
private void deleteEntry(Entry<K,V> p) {
    // 修改次數(shù)加1
    modCount++;
    // 元素個數(shù)減1
    size--;
    if (p.left != null && p.right != null) {
        // 如果當前節(jié)點既有左子節(jié)點，又有右子節(jié)點
        // 取其右子樹中最小的節(jié)點
        Entry<K,V> s = successor(p);
        // 用右子樹中最小節(jié)點的值替換當前節(jié)點的值
        p.key = s.key;
        p.value = s.value;
        // 把右子樹中最小節(jié)點設為當前節(jié)點
        p = s;
        // 這種情況實際上并沒有刪除p節(jié)點，而是把p節(jié)點的值改了，實際刪除的是p的后繼節(jié)點
    }
    // 如果原來的當前節(jié)點（p）有2個子節(jié)點，則當前節(jié)點已經(jīng)變成原來p的右子樹中的最小節(jié)點了，也就是說其沒有左子節(jié)點了
    // 到這一步，p肯定只有一個子節(jié)點了
    // 如果當前節(jié)點有子節(jié)點，則用子節(jié)點替換當前節(jié)點
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    if (replacement != null) {
        // 把替換節(jié)點直接放到當前節(jié)點的位置上（相當于刪除了p，并把替換節(jié)點移動過來了）
        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的各項屬性都設為空
        p.left = p.right = p.parent = null;
        // 如果p是黑節(jié)點，則需要再平衡
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) {
        // 如果當前節(jié)點就是根節(jié)點，則直接將根節(jié)點設為空即可
        root = null;
    } else {
        // 如果當前節(jié)點沒有子節(jié)點且其為黑節(jié)點，則把自己當作虛擬的替換節(jié)點進行再平衡
        if (p.color == BLACK)
            fixAfterDeletion(p);
        // 平衡完成后刪除當前節(jié)點（與父節(jié)點斷絕關系）
        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;
        }
    }
}

刪除再平衡

經(jīng)過上面的處理，真正刪除的肯定是黑色節(jié)點才會進入到再平衡階段。

因為刪除的是黑色節(jié)點，導致整顆樹不平衡了，所以這里我們假設把刪除的黑色賦予當前節(jié)點，這樣當前節(jié)點除了它自已的顏色還多了一個黑色，那么：

（1）如果當前節(jié)點是根節(jié)點，則直接涂黑即可，不需要再平衡；

（2）如果當前節(jié)點是紅+黑節(jié)點，則直接涂黑即可，不需要平衡；

（3）如果當前節(jié)點是黑+黑節(jié)點，則我們只要通過旋轉(zhuǎn)把這個多出來的黑色不斷的向上傳遞到一個紅色節(jié)點即可，這又可能會出現(xiàn)以下四種情況：

（假設當前節(jié)點為父節(jié)點的左子節(jié)點）

情況	策略
1）x是黑+黑節(jié)點，x的兄弟是紅節(jié)點	（1）將兄弟節(jié)點設為黑色；（2）將父節(jié)點設為紅色；（3）以父節(jié)點為支點進行左旋；（4）重新設置x的兄弟節(jié)點，進入下一步；
2）x是黑+黑節(jié)點，x的兄弟是黑節(jié)點，且兄弟節(jié)點的兩個子節(jié)點都是黑色	（1）將兄弟節(jié)點設置為紅色；（2）將x的父節(jié)點作為新的當前節(jié)點，進入下一次循環(huán)；
3）x是黑+黑節(jié)點，x的兄弟是黑節(jié)點，且兄弟節(jié)點的右子節(jié)點為黑色，左子節(jié)點為紅色	（1）將兄弟節(jié)點的左子節(jié)點設為黑色；（2）將兄弟節(jié)點設為紅色；（3）以兄弟節(jié)點為支點進行右旋；（4）重新設置x的兄弟節(jié)點，進入下一步；
3）x是黑+黑節(jié)點，x的兄弟是黑節(jié)點，且兄弟節(jié)點的右子節(jié)點為紅色，左子節(jié)點任意顏色	（1）將兄弟節(jié)點的顏色設為父節(jié)點的顏色；（2）將父節(jié)點設為黑色；（3）將兄弟節(jié)點的右子節(jié)點設為黑色；（4）以父節(jié)點為支點進行左旋；（5）將root作為新的當前節(jié)點（退出循環(huán)）；

（假設當前節(jié)點為父節(jié)點的右子節(jié)點，正好反過來）

情況	策略
1）x是黑+黑節(jié)點，x的兄弟是紅節(jié)點	（1）將兄弟節(jié)點設為黑色；（2）將父節(jié)點設為紅色；（3）以父節(jié)點為支點進行右旋；（4）重新設置x的兄弟節(jié)點，進入下一步；
2）x是黑+黑節(jié)點，x的兄弟是黑節(jié)點，且兄弟節(jié)點的兩個子節(jié)點都是黑色	（1）將兄弟節(jié)點設置為紅色；（2）將x的父節(jié)點作為新的當前節(jié)點，進入下一次循環(huán)；
3）x是黑+黑節(jié)點，x的兄弟是黑節(jié)點，且兄弟節(jié)點的左子節(jié)點為黑色，右子節(jié)點為紅色	（1）將兄弟節(jié)點的右子節(jié)點設為黑色；（2）將兄弟節(jié)點設為紅色；（3）以兄弟節(jié)點為支點進行左旋；（4）重新設置x的兄弟節(jié)點，進入下一步；
3）x是黑+黑節(jié)點，x的兄弟是黑節(jié)點，且兄弟節(jié)點的左子節(jié)點為紅色，右子節(jié)點任意顏色	（1）將兄弟節(jié)點的顏色設為父節(jié)點的顏色；（2）將父節(jié)點設為黑色；（3）將兄弟節(jié)點的左子節(jié)點設為黑色；（4）以父節(jié)點為支點進行右旋；（5）將root作為新的當前節(jié)點（退出循環(huán)）；

讓我們來看看TreeMap中的實現(xiàn)：

/**
 * 刪除再平衡
 *（1）每個節(jié)點或者是黑色，或者是紅色。
 *（2）根節(jié)點是黑色。
 *（3）每個葉子節(jié)點（NIL）是黑色。（注意：這里葉子節(jié)點，是指為空(NIL或NULL)的葉子節(jié)點?。?
 *（4）如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的。
 *（5）從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點。
 */
private void fixAfterDeletion(Entry<K,V> x) {
    // 只有當前節(jié)點不是根節(jié)點且當前節(jié)點是黑色時才進入循環(huán)
    while (x != root && colorOf(x) == BLACK) {
        if (x == leftOf(parentOf(x))) {
            // 如果當前節(jié)點是其父節(jié)點的左子節(jié)點
            // sib是當前節(jié)點的兄弟節(jié)點
            Entry<K,V> sib = rightOf(parentOf(x));
            // 情況1）如果兄弟節(jié)點是紅色
            if (colorOf(sib) == RED) {
                // （1）將兄弟節(jié)點設為黑色
                setColor(sib, BLACK);
                // （2）將父節(jié)點設為紅色
                setColor(parentOf(x), RED);
                // （3）以父節(jié)點為支點進行左旋
                rotateLeft(parentOf(x));
                // （4）重新設置x的兄弟節(jié)點，進入下一步
                sib = rightOf(parentOf(x));
            }
            if (colorOf(leftOf(sib))  == BLACK &&
                    colorOf(rightOf(sib)) == BLACK) {
                // 情況2）如果兄弟節(jié)點的兩個子節(jié)點都是黑色
                // （1）將兄弟節(jié)點設置為紅色
                setColor(sib, RED);
                // （2）將x的父節(jié)點作為新的當前節(jié)點，進入下一次循環(huán)
                x = parentOf(x);
            } else {
                if (colorOf(rightOf(sib)) == BLACK) {
                    // 情況3）如果兄弟節(jié)點的右子節(jié)點為黑色
                    // （1）將兄弟節(jié)點的左子節(jié)點設為黑色
                    setColor(leftOf(sib), BLACK);
                    // （2）將兄弟節(jié)點設為紅色
                    setColor(sib, RED);
                    // （3）以兄弟節(jié)點為支點進行右旋
                    rotateRight(sib);
                    // （4）重新設置x的兄弟節(jié)點
                    sib = rightOf(parentOf(x));
                }
                // 情況4）
                // （1）將兄弟節(jié)點的顏色設為父節(jié)點的顏色
                setColor(sib, colorOf(parentOf(x)));
                // （2）將父節(jié)點設為黑色
                setColor(parentOf(x), BLACK);
                // （3）將兄弟節(jié)點的右子節(jié)點設為黑色
                setColor(rightOf(sib), BLACK);
                // （4）以父節(jié)點為支點進行左旋
                rotateLeft(parentOf(x));
                // （5）將root作為新的當前節(jié)點（退出循環(huán)）
                x = root;
            }
        } else { // symmetric
            // 如果當前節(jié)點是其父節(jié)點的右子節(jié)點
            // sib是當前節(jié)點的兄弟節(jié)點
            Entry<K,V> sib = leftOf(parentOf(x));
            // 情況1）如果兄弟節(jié)點是紅色
            if (colorOf(sib) == RED) {
                // （1）將兄弟節(jié)點設為黑色
                setColor(sib, BLACK);
                // （2）將父節(jié)點設為紅色
                setColor(parentOf(x), RED);
                // （3）以父節(jié)點為支點進行右旋
                rotateRight(parentOf(x));
                // （4）重新設置x的兄弟節(jié)點
                sib = leftOf(parentOf(x));
            }
            if (colorOf(rightOf(sib)) == BLACK &&
                    colorOf(leftOf(sib)) == BLACK) {
                // 情況2）如果兄弟節(jié)點的兩個子節(jié)點都是黑色
                // （1）將兄弟節(jié)點設置為紅色
                setColor(sib, RED);
                // （2）將x的父節(jié)點作為新的當前節(jié)點，進入下一次循環(huán)
                x = parentOf(x);
            } else {
                if (colorOf(leftOf(sib)) == BLACK) {
                    // 情況3）如果兄弟節(jié)點的左子節(jié)點為黑色
                    // （1）將兄弟節(jié)點的右子節(jié)點設為黑色
                    setColor(rightOf(sib), BLACK);
                    // （2）將兄弟節(jié)點設為紅色
                    setColor(sib, RED);
                    // （3）以兄弟節(jié)點為支點進行左旋
                    rotateLeft(sib);
                    // （4）重新設置x的兄弟節(jié)點
                    sib = leftOf(parentOf(x));
                }
                // 情況4）
                // （1）將兄弟節(jié)點的顏色設為父節(jié)點的顏色
                setColor(sib, colorOf(parentOf(x)));
                // （2）將父節(jié)點設為黑色
                setColor(parentOf(x), BLACK);
                // （3）將兄弟節(jié)點的左子節(jié)點設為黑色
                setColor(leftOf(sib), BLACK);
                // （4）以父節(jié)點為支點進行右旋
                rotateRight(parentOf(x));
                // （5）將root作為新的當前節(jié)點（退出循環(huán)）
                x = root;
            }
        }
    }
    // 退出條件為多出來的黑色向上傳遞到了根節(jié)點或者紅節(jié)點
    // 則將x設為黑色即可滿足紅黑樹規(guī)則
    setColor(x, BLACK);
}

刪除元素舉例

假設我們有下面這樣一顆紅黑樹。

treemap-delete1

我們刪除6號元素，則從右子樹中找到了最小元素7，7又沒有子節(jié)點了，所以把7作為當前節(jié)點進行再平衡。

我們看到7是黑節(jié)點，且其兄弟為黑節(jié)點，且其兄弟的兩個子節(jié)點都是紅色，滿足情況4），平衡之后如下圖所示。

treemap-delete2

我們再刪除7號元素，則從右子樹中找到了最小元素8，8有子節(jié)點且為黑色，所以8的子節(jié)點9是替代節(jié)點，以9為當前節(jié)點進行再平衡。

我們發(fā)現(xiàn)9是紅節(jié)點，則直接把它涂成黑色即滿足了紅黑樹的特性，不需要再過多的平衡了。

treemap-delete3

這次我們來個狠的，把根節(jié)點刪除，從右子樹中找到了最小的元素5，5沒有子節(jié)點，所以把5作為當前節(jié)點進行再平衡。

我們看到5是黑節(jié)點，且其兄弟為紅色，符合情況1），平衡之后如下圖所示，然后進入情況2）。

treemap-delete4

對情況2）進行再平衡后如下圖所示。

treemap-delete5

然后進入下一次循環(huán)，發(fā)現(xiàn)不符合循環(huán)條件了，直接把x涂為黑色即可，退出這個方法之后會把舊x刪除掉（見deleteEntry()方法），最后的結果就是下面這樣。

treemap-delete6

二叉樹的遍歷

我們知道二叉查找樹的遍歷有前序遍歷、中序遍歷、后序遍歷。

（1）前序遍歷，先遍歷我，再遍歷我的左子節(jié)點，最后遍歷我的右子節(jié)點；

（2）中序遍歷，先遍歷我的左子節(jié)點，再遍歷我，最后遍歷我的右子節(jié)點；

（3）后序遍歷，先遍歷我的左子節(jié)點，再遍歷我的右子節(jié)點，最后遍歷我；

這里的前中后都是以“我”的順序為準的，我在前就是前序遍歷，我在中就是中序遍歷，我在后就是后序遍歷。

下面讓我們看看經(jīng)典的中序遍歷是怎么實現(xiàn)的：

public class TreeMapTest {
    public static void main(String[] args) {
        // 構建一顆10個元素的樹
        TreeNode<Integer> node = new TreeNode<>(1, null).insert(2)
                .insert(6).insert(3).insert(5).insert(9)
                .insert(7).insert(8).insert(4).insert(10);
        // 中序遍歷，打印結果為1到10的順序
        node.root().inOrderTraverse();
    }
}
/**
 * 樹節(jié)點，假設不存在重復元素
 * @param <T>
 */
class TreeNode<T extends Comparable<T>> {
    T value;
    TreeNode<T> parent;
    TreeNode<T> left, right;
    public TreeNode(T value, TreeNode<T> parent) {
        this.value = value;
        this.parent = parent;
    }
    /**
     * 獲取根節(jié)點
     */
    TreeNode<T> root() {
        TreeNode<T> cur = this;
        while (cur.parent != null) {
            cur = cur.parent;
        }
        return cur;
    }
    /**
     * 中序遍歷
     */
    void inOrderTraverse() {
        if(this.left != null) this.left.inOrderTraverse();
        System.out.println(this.value);
        if(this.right != null) this.right.inOrderTraverse();
    }
    /**
     * 經(jīng)典的二叉樹插入元素的方法
     */
    TreeNode<T> insert(T value) {
        // 先找根元素
        TreeNode<T> cur = root();
        TreeNode<T> p;
        int dir;
        // 尋找元素應該插入的位置
        do {
            p = cur;
            if ((dir=value.compareTo(p.value)) < 0) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        } while (cur != null);
        // 把元素放到找到的位置
        if (dir < 0) {
            p.left = new TreeNode<>(value, p);
            return p.left;
        } else {
            p.right = new TreeNode<>(value, p);
            return p.right;
        }
    }
}

TreeMap的遍歷

從上面二叉樹的遍歷我們很明顯地看到，它是通過遞歸的方式實現(xiàn)的，但是遞歸會占用額外的空間，直接到線程棧整個釋放掉才會把方法中申請的變量銷毀掉，所以當元素特別多的時候是一件很危險的事。

（上面的例子中，沒有申請額外的空間，如果有聲明變量，則可以理解為直到方法完成才會銷毀變量）

那么，有沒有什么方法不用遞歸呢？

讓我們來看看java中的實現(xiàn)：

@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
    Objects.requireNonNull(action);
    // 遍歷前的修改次數(shù)
    int expectedModCount = modCount;
    // 執(zhí)行遍歷，先獲取第一個元素的位置，再循環(huán)遍歷后繼節(jié)點
    for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
        // 執(zhí)行動作
        action.accept(e.key, e.value);
        // 如果發(fā)現(xiàn)修改次數(shù)變了，則拋出異常
        if (expectedModCount != modCount) {
            throw new ConcurrentModificationException();
        }
    }
}

是不是很簡單？！

（1）尋找第一個節(jié)點；

從根節(jié)點開始找最左邊的節(jié)點，即最小的元素。

    final Entry<K,V> getFirstEntry() {
        Entry<K,V> p = root;
        // 從根節(jié)點開始找最左邊的節(jié)點，即最小的元素
        if (p != null)
            while (p.left != null)
                p = p.left;
        return p;
    }

（2）循環(huán)遍歷后繼節(jié)點；

尋找后繼節(jié)點這個方法我們在刪除元素的時候也用到過，當時的場景是有右子樹，則從其右子樹中尋找最小的節(jié)點。

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        // 如果當前節(jié)點為空，返回空
        return null;
    else if (t.right != null) {
        // 如果當前節(jié)點有右子樹，取右子樹中最小的節(jié)點
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        // 如果當前節(jié)點沒有右子樹
        // 如果當前節(jié)點是父節(jié)點的左子節(jié)點，直接返回父節(jié)點
        // 如果當前節(jié)點是父節(jié)點的右子節(jié)點，一直往上找，直到找到一個祖先節(jié)點是其父節(jié)點的左子節(jié)點為止，返回這個祖先節(jié)點的父節(jié)點
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

讓我們一起來分析下這種方式的時間復雜度吧。

首先，尋找第一個元素，因為紅黑樹是接近平衡的二叉樹，所以找最小的節(jié)點，相當于是從頂?shù)降琢?，時間復雜度為O(log n)；

其次，尋找后繼節(jié)點，因為紅黑樹插入元素的時候會自動平衡，最壞的情況就是尋找右子樹中最小的節(jié)點，時間復雜度為O(log k)，k為右子樹元素個數(shù)；

最后，需要遍歷所有元素，時間復雜度為O(n)；

所以，總的時間復雜度為 O(log n) + O(n * log k) ≈ O(n)。

雖然遍歷紅黑樹的時間復雜度是O(n)，但是它實際是要比跳表要慢一點的，啥？跳表是啥？安心，后面會講到跳表的。