死磕java集合之TreeMap源碼分析（三）-內(nèi)含紅黑樹分析全過(guò)程

刪除元素

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

創(chuàng)新互聯(lián)公司主要從事網(wǎng)站建設(shè)、成都網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)龍文,十多年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來(lái)電咨詢建站服務(wù):18982081108

（1）如果刪除的位置有兩個(gè)葉子節(jié)點(diǎn)，則從其右子樹中取最小的元素放到刪除的位置，然后把刪除位置移到替代元素的位置，進(jìn)入下一步。

（2）如果刪除的位置只有一個(gè)葉子節(jié)點(diǎn)（有可能是經(jīng)過(guò)第一步轉(zhuǎn)換后的刪除位置），則把那個(gè)葉子節(jié)點(diǎn)作為替代元素，放到刪除的位置，然后把這個(gè)葉子節(jié)點(diǎn)刪除。

（3）如果刪除的位置沒(méi)有葉子節(jié)點(diǎn)，則直接把這個(gè)刪除位置的元素刪除即可。

（4）針對(duì)紅黑樹，如果刪除位置是黑色節(jié)點(diǎn)，還需要做再平衡。

（5）如果有替代元素，則以替代元素作為當(dāng)前節(jié)點(diǎn)進(jìn)入再平衡。

（6）如果沒(méi)有替代元素，則以刪除的位置的元素作為當(dāng)前節(jié)點(diǎn)進(jìn)入再平衡，平衡之后再刪除這個(gè)節(jié)點(diǎn)。

public V remove(Object key) {
    // 獲取節(jié)點(diǎn)
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

    V oldValue = p.value;
    // 刪除節(jié)點(diǎn)
    deleteEntry(p);
    // 返回刪除的value
    return oldValue;
}

private void deleteEntry(Entry<K,V> p) {
    // 修改次數(shù)加1
    modCount++;
    // 元素個(gè)數(shù)減1
    size--;

    if (p.left != null && p.right != null) {
        // 如果當(dāng)前節(jié)點(diǎn)既有左子節(jié)點(diǎn)，又有右子節(jié)點(diǎn)
        // 取其右子樹中最小的節(jié)點(diǎn)
        Entry<K,V> s = successor(p);
        // 用右子樹中最小節(jié)點(diǎn)的值替換當(dāng)前節(jié)點(diǎn)的值
        p.key = s.key;
        p.value = s.value;
        // 把右子樹中最小節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn)
        p = s;
        // 這種情況實(shí)際上并沒(méi)有刪除p節(jié)點(diǎn)，而是把p節(jié)點(diǎn)的值改了，實(shí)際刪除的是p的后繼節(jié)點(diǎn)
    }

    // 如果原來(lái)的當(dāng)前節(jié)點(diǎn)（p）有2個(gè)子節(jié)點(diǎn)，則當(dāng)前節(jié)點(diǎn)已經(jīng)變成原來(lái)p的右子樹中的最小節(jié)點(diǎn)了，也就是說(shuō)其沒(méi)有左子節(jié)點(diǎn)了
    // 到這一步，p肯定只有一個(gè)子節(jié)點(diǎn)了
    // 如果當(dāng)前節(jié)點(diǎn)有子節(jié)點(diǎn)，則用子節(jié)點(diǎn)替換當(dāng)前節(jié)點(diǎn)
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    if (replacement != null) {
        // 把替換節(jié)點(diǎn)直接放到當(dāng)前節(jié)點(diǎn)的位置上（相當(dāng)于刪除了p，并把替換節(jié)點(diǎn)移動(dòng)過(guò)來(lái)了）
        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的各項(xiàng)屬性都設(shè)為空
        p.left = p.right = p.parent = null;

        // 如果p是黑節(jié)點(diǎn)，則需要再平衡
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) {
        // 如果當(dāng)前節(jié)點(diǎn)就是根節(jié)點(diǎn)，則直接將根節(jié)點(diǎn)設(shè)為空即可
        root = null;
    } else {
        // 如果當(dāng)前節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)且其為黑節(jié)點(diǎn)，則把自己當(dāng)作虛擬的替換節(jié)點(diǎn)進(jìn)行再平衡
        if (p.color == BLACK)
            fixAfterDeletion(p);

        // 平衡完成后刪除當(dāng)前節(jié)點(diǎn)（與父節(jié)點(diǎn)斷絕關(guā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;
        }
    }
}

刪除再平衡

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

因?yàn)閯h除的是黑色節(jié)點(diǎn)，導(dǎo)致整顆樹不平衡了，所以這里我們假設(shè)把刪除的黑色賦予當(dāng)前節(jié)點(diǎn)，這樣當(dāng)前節(jié)點(diǎn)除了它自已的顏色還多了一個(gè)黑色，那么：

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

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

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

（假設(shè)當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)的左子節(jié)點(diǎn)）

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

（假設(shè)當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)的右子節(jié)點(diǎn)，正好反過(guò)來(lái)）

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

讓我們來(lái)看看TreeMap中的實(shí)現(xiàn)：

/**
 * 刪除再平衡
 *（1）每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色。
 *（2）根節(jié)點(diǎn)是黑色。
 *（3）每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色。（注意：這里葉子節(jié)點(diǎn)，是指為空(NIL或NULL)的葉子節(jié)點(diǎn)！）
 *（4）如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的。
 *（5）從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。
 */
private void fixAfterDeletion(Entry<K,V> x) {
    // 只有當(dāng)前節(jié)點(diǎn)不是根節(jié)點(diǎn)且當(dāng)前節(jié)點(diǎn)是黑色時(shí)才進(jìn)入循環(huán)
    while (x != root && colorOf(x) == BLACK) {
        if (x == leftOf(parentOf(x))) {
            // 如果當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)
            // sib是當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)
            Entry<K,V> sib = rightOf(parentOf(x));

            // 情況1）如果兄弟節(jié)點(diǎn)是紅色
            if (colorOf(sib) == RED) {
                // （1）將兄弟節(jié)點(diǎn)設(shè)為黑色
                setColor(sib, BLACK);
                // （2）將父節(jié)點(diǎn)設(shè)為紅色
                setColor(parentOf(x), RED);
                // （3）以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋
                rotateLeft(parentOf(x));
                // （4）重新設(shè)置x的兄弟節(jié)點(diǎn)，進(jìn)入下一步
                sib = rightOf(parentOf(x));
            }

            if (colorOf(leftOf(sib))  == BLACK &&
                    colorOf(rightOf(sib)) == BLACK) {
                // 情況2）如果兄弟節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色
                // （1）將兄弟節(jié)點(diǎn)設(shè)置為紅色
                setColor(sib, RED);
                // （2）將x的父節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn)，進(jìn)入下一次循環(huán)
                x = parentOf(x);
            } else {
                if (colorOf(rightOf(sib)) == BLACK) {
                    // 情況3）如果兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)為黑色
                    // （1）將兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)設(shè)為黑色
                    setColor(leftOf(sib), BLACK);
                    // （2）將兄弟節(jié)點(diǎn)設(shè)為紅色
                    setColor(sib, RED);
                    // （3）以兄弟節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋
                    rotateRight(sib);
                    // （4）重新設(shè)置x的兄弟節(jié)點(diǎn)
                    sib = rightOf(parentOf(x));
                }
                // 情況4）
                // （1）將兄弟節(jié)點(diǎn)的顏色設(shè)為父節(jié)點(diǎn)的顏色
                setColor(sib, colorOf(parentOf(x)));
                // （2）將父節(jié)點(diǎn)設(shè)為黑色
                setColor(parentOf(x), BLACK);
                // （3）將兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)設(shè)為黑色
                setColor(rightOf(sib), BLACK);
                // （4）以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋
                rotateLeft(parentOf(x));
                // （5）將root作為新的當(dāng)前節(jié)點(diǎn)（退出循環(huán)）
                x = root;
            }
        } else { // symmetric
            // 如果當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的右子節(jié)點(diǎn)
            // sib是當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)
            Entry<K,V> sib = leftOf(parentOf(x));

            // 情況1）如果兄弟節(jié)點(diǎn)是紅色
            if (colorOf(sib) == RED) {
                // （1）將兄弟節(jié)點(diǎn)設(shè)為黑色
                setColor(sib, BLACK);
                // （2）將父節(jié)點(diǎn)設(shè)為紅色
                setColor(parentOf(x), RED);
                // （3）以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋
                rotateRight(parentOf(x));
                // （4）重新設(shè)置x的兄弟節(jié)點(diǎn)
                sib = leftOf(parentOf(x));
            }

            if (colorOf(rightOf(sib)) == BLACK &&
                    colorOf(leftOf(sib)) == BLACK) {
                // 情況2）如果兄弟節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色
                // （1）將兄弟節(jié)點(diǎn)設(shè)置為紅色
                setColor(sib, RED);
                // （2）將x的父節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn)，進(jìn)入下一次循環(huán)
                x = parentOf(x);
            } else {
                if (colorOf(leftOf(sib)) == BLACK) {
                    // 情況3）如果兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)為黑色
                    // （1）將兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)設(shè)為黑色
                    setColor(rightOf(sib), BLACK);
                    // （2）將兄弟節(jié)點(diǎn)設(shè)為紅色
                    setColor(sib, RED);
                    // （3）以兄弟節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋
                    rotateLeft(sib);
                    // （4）重新設(shè)置x的兄弟節(jié)點(diǎn)
                    sib = leftOf(parentOf(x));
                }
                // 情況4）
                // （1）將兄弟節(jié)點(diǎn)的顏色設(shè)為父節(jié)點(diǎn)的顏色
                setColor(sib, colorOf(parentOf(x)));
                // （2）將父節(jié)點(diǎn)設(shè)為黑色
                setColor(parentOf(x), BLACK);
                // （3）將兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)設(shè)為黑色
                setColor(leftOf(sib), BLACK);
                // （4）以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋
                rotateRight(parentOf(x));
                // （5）將root作為新的當(dāng)前節(jié)點(diǎn)（退出循環(huán)）
                x = root;
            }
        }
    }

    // 退出條件為多出來(lái)的黑色向上傳遞到了根節(jié)點(diǎn)或者紅節(jié)點(diǎn)
    // 則將x設(shè)為黑色即可滿足紅黑樹規(guī)則
    setColor(x, BLACK);
}