【死磕 Java 集合】--- TreeMap源碼分析（三）

【死磕 Java 集合】--- TreeMap源碼分析（三）

刪除元素

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

（1）如果刪除的位置有兩個(gè)葉子節(jié)點(diǎn)，則從其右子樹(shù)中取最小的元素放到刪除的位置，然后把刪除位置移到替代元素的位置，進(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ì)紅黑樹(shù)，如果刪除位置是黑色節(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)

// 取其右子樹(shù)中最小的節(jié)點(diǎn)

Entry
<
K
,
V
>
 s 
=
 successor
(
p
);

// 用右子樹(shù)中最小節(jié)點(diǎn)的值替換當(dāng)前節(jié)點(diǎn)的值
        p
.
key 
=
 s
.
key
;
        p
.
value 
=
 s
.
value
;

// 把右子樹(shù)中最小節(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的右子樹(shù)中的最小節(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ù)不平衡了，所以這里我們假設(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è)為黑色；

（2）將父節(jié)點(diǎn)設(shè)為紅色；

（3）以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋；

（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è)置為紅色；

（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è)為黑色；

（2）將兄弟節(jié)點(diǎn)設(shè)為紅色；

（3）以兄弟節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋；

（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)的顏色；

（2）將父節(jié)點(diǎn)設(shè)為黑色；

（3）將兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)設(shè)為黑色；

（4）以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋；

（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è)為黑色；

（2）將父節(jié)點(diǎn)設(shè)為紅色；

（3）以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋；

（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è)置為紅色；

（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è)為黑色；

（2）將兄弟節(jié)點(diǎn)設(shè)為紅色；

（3）以兄弟節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋；

（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)的顏色；

（2）將父節(jié)點(diǎn)設(shè)為黑色；

（3）將兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)設(shè)為黑色；

（4）以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋；

（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è)為黑色即可滿足紅黑樹(shù)規(guī)則
    setColor
(
x
,
 BLACK
);
}

刪除元素舉例

假設(shè)我們有下面這樣一顆紅黑樹(shù)。

我們刪除6號(hào)元素，則從右子樹(shù)中找到了最小元素7，7又沒(méi)有子節(jié)點(diǎn)了，所以把7作為當(dāng)前節(jié)點(diǎn)進(jìn)行再平衡。

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

我們?cè)賱h除7號(hào)元素，則從右子樹(shù)中找到了最小元素8，8有子節(jié)點(diǎn)且為黑色，所以8的子節(jié)點(diǎn)9是替代節(jié)點(diǎn)，以9為當(dāng)前節(jié)點(diǎn)進(jìn)行再平衡。

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

這次我們來(lái)個(gè)狠的，把根節(jié)點(diǎn)刪除，從右子樹(shù)中找到了最小的元素5，5沒(méi)有子節(jié)點(diǎn)，所以把5作為當(dāng)前節(jié)點(diǎn)進(jìn)行再平衡。

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

對(duì)情況2）進(jìn)行再平衡后如下圖所示。

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

未完待續(xù)，下一節(jié)我們一起探討紅黑樹(shù)遍歷元素的操作。