徹底理解紅黑樹（一）之 二叉搜索樹
徹底理解紅黑樹（二）之 插入
徹底理解紅黑樹（三）之 刪除
前言
紅黑樹的刪除情況相對插入會復(fù)雜一些，這里以個(gè)人認(rèn)為較好理解和記憶的方式進(jìn)行分類，和其他一些文章（比如維基百科）的表達(dá)可能不一樣，但是實(shí)際上是一樣的。比如說家有兩兄弟A和B。我是根據(jù)A是哥哥還是弟弟進(jìn)行分類；他是根據(jù)B是哥哥還是弟弟進(jìn)行分類。
建議閱讀本文后，自己動手試試，一來印證本文是否正確，二來自己嘗試著摸一些規(guī)律，加深印象（文末也有一個(gè)簡單的例子）。
1.刪除動作
紅黑樹和二叉搜索樹的刪除類似，只不過加上顏色屬性（這里的子節(jié)點(diǎn)均指非NULL節(jié)點(diǎn)）：
- 無子節(jié)點(diǎn)時(shí)，刪除節(jié)點(diǎn)可能為紅色或者黑色；
1.1 如果為紅色，直接刪除即可，不會影響黑色節(jié)點(diǎn)的數(shù)量；
1.2 如果為黑色，則需要進(jìn)行刪除平衡的操作了； - 只有一個(gè)子節(jié)點(diǎn)時(shí)，刪除節(jié)點(diǎn)只能是黑色，其子節(jié)點(diǎn)為紅色，否則無法滿足紅黑樹的性質(zhì)了。 此時(shí)用刪除節(jié)點(diǎn)的子節(jié)點(diǎn)接到父節(jié)點(diǎn)，且將子節(jié)點(diǎn)顏色涂黑，保證黑色數(shù)量。
- 有兩個(gè)子節(jié)點(diǎn)時(shí)，與二叉搜索樹一樣，使用后繼節(jié)點(diǎn)作為替換的刪除節(jié)點(diǎn)，情形轉(zhuǎn)至為1或2處理。
我們發(fā)現(xiàn)，刪除情形3總是會轉(zhuǎn)換為情形1和2的，而情形1.1和情形2處理平衡非常簡單，本文主要討論的是情形1.2：刪除黑色的葉子節(jié)點(diǎn)。因?yàn)橐坏┰摴?jié)點(diǎn)被拿掉，紅黑樹中通過該節(jié)點(diǎn)的路徑黑色節(jié)點(diǎn)數(shù)量將會減1，而且無法像情形2那樣將子節(jié)點(diǎn)涂黑來達(dá)到平衡。此時(shí)只能自底向上進(jìn)行平衡操作。
這里的圖特意將黑色的NULL節(jié)點(diǎn)給加上，這是因?yàn)閯h除節(jié)點(diǎn)被摘掉后，我們可以用一個(gè)黑色的節(jié)點(diǎn)接上，從而進(jìn)行統(tǒng)一處理。
2.刪除后的平衡
我們先約定一下節(jié)點(diǎn)名稱：
h(A->B->葉子)表示從A走到B再走到某一個(gè)葉子路徑的黑色節(jié)點(diǎn)數(shù)量（A與B，B與葉子之間可能間隔了多個(gè)節(jié)點(diǎn)）
本文余下內(nèi)容均指的是刪除黑色的葉子節(jié)點(diǎn)后引發(fā)的一系列平衡操作。比如P->D->N，刪除D（黑色）后，N接至父節(jié)點(diǎn)：P->N。
因?yàn)閯h除了一個(gè)黑色節(jié)點(diǎn)（N的父節(jié)點(diǎn)D），經(jīng)過N的路徑的黑色數(shù)量減1，即h(P->N->葉子) 比 h(P->S->葉子) 少1。平衡的方式有：
（1）h(P->N->葉子)不變，h(P->S->葉子)減1，此時(shí)已經(jīng)子平衡；然而h(GP->P->葉子)還是會比h(GP -> U ->葉子)少1。此時(shí)需要將P當(dāng)作新的N，向上遞歸處理；
（2）h(P->N->葉子)加1，h(P->S->葉子)不變，也就是恢復(fù)了原來的狀態(tài)，此時(shí)已經(jīng)平衡，因?yàn)閔(GP->P->葉子)=h(GP -> U ->葉子)。
本文下面平衡的思路主要就是基于以上兩種方式，另外要注意的是，紅色和紅色不能連一起的約束也不能違反。理解這個(gè)比較重要。
GP->P->葉子 的路徑，要么經(jīng)過N，要么經(jīng)過S，如果h(P->N->葉子)和h(P->S->葉子)均少1了，自然h(GP->P->葉子)會少1。
刪除平衡情形，主要根據(jù) [兄節(jié)點(diǎn)的位置/顏色]、[兄的子節(jié)點(diǎn)的顏色]、[父節(jié)點(diǎn)顏色] 進(jìn)行分類：
N節(jié)點(diǎn)的位置知道后，S的位置自然也就知道了，相反亦可；這里以S位置作為分類，主要是為了便于理解和記憶。
情形1 當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)（父節(jié)點(diǎn)為NULL）
比較特殊的情況，無需平衡操作。因?yàn)榻?jīng)過根節(jié)點(diǎn)的黑色數(shù)量少一個(gè)，意味著所有路徑都少一個(gè)，已然平衡。
情形2 兄弟節(jié)點(diǎn)為黑色（S=黑）
情形2.1 兄弟的子節(jié)點(diǎn)全黑（SL/SR=黑）
兄弟節(jié)點(diǎn)的子節(jié)點(diǎn)全為黑色，也就意味著兄弟節(jié)點(diǎn)（S）可以涂紅而不會和子沖突。S涂紅后，也就實(shí)現(xiàn)了子平衡，
這時(shí)候我們看父節(jié)點(diǎn)是紅是黑，再做處理。
情形2.1.1 父節(jié)點(diǎn)為黑色（P=黑）
此時(shí)將S涂紅，父節(jié)點(diǎn)作為新的平衡節(jié)點(diǎn)N，遞歸上去處理。
這個(gè)也就是之前提到的h(P->N->葉子)不變，h(P->S->葉子)減1；而h(GP->P->葉子)，依然會比h(GP -> U ->葉子)少1，所以要遞歸上去處理。
情形2.1.2 父節(jié)點(diǎn)為紅色（P=紅）
此時(shí)將S涂紅，P涂黑，平衡結(jié)束。
S涂紅后，h(P->N->葉子)不變，h(P->S->葉子)-1，實(shí)現(xiàn)子平衡；因?yàn)镻節(jié)點(diǎn)是紅色的，如果將它涂黑，h(P->N->葉子)和h(P->S->葉子)均會+1，就可以恢復(fù)原來的狀態(tài)了，而不用遞歸上去。
情形2.2 兄弟的子節(jié)點(diǎn)不全黑
所謂的不全黑包括：[SL紅, SR紅]、[SL黑，SR紅]、[SL紅，SR黑]。如果其中一個(gè)為黑，另外一個(gè)肯定是紅。
以全黑/非全黑作為分類，是因?yàn)槿跁r(shí)無論N是在左子還是右子，其處理方式是一樣的。
而非全黑則要看N所處的位置（或者說S所處的位置）進(jìn)行特定方向的旋轉(zhuǎn)。
為了方便理解和記憶，以S進(jìn)行分組：
S為左子時(shí)（即N為右子），主要分兩組 [SL=紅]、[SL=黑]。
S為右子時(shí)（即N為左子），主要分兩組 [SR=紅]、[SR=黑]。
【S為左子，SL紅】與【S為右子，SR紅】處理方式對稱；
【S為左子，SL黑】與【S為右子，SR黑】處理方式對稱。
情形2.2.1 S為左子，SL紅；S為右子，SR紅
情形(1) S為黑色，S為左子，SL紅時(shí)：
以P為支點(diǎn)右旋；交換P和S顏色，SL涂黑；平衡結(jié)束。
這里的平衡思路其實(shí)就是：h(P->S->葉子)不變（因?yàn)镾L涂黑補(bǔ)回來了），h(P->N->葉子)+1（因?yàn)槎嗔藗€(gè)黑色P）。
通常旋轉(zhuǎn)后，新的P節(jié)點(diǎn)往往都會涂成原P的顏色：一是為了讓GP-P不會顏色沖突；二是保持經(jīng)過P的路徑黑色數(shù)量不變。
對稱的情形(2)：S為黑色，S為右子，SR紅時(shí)：
以P為支點(diǎn)左旋；交換P和S顏色（S涂為P原顏色，P涂黑），SR涂黑；平衡結(jié)束。
情形2.2.2 S為左子，SL黑；S為右子，SR黑
情形(1) S為黑色，S為左子，SL黑
以S為支點(diǎn)左旋，交換S和SR顏色（SR涂黑，S涂紅） ，此時(shí)轉(zhuǎn)至情形2.2.1-(1) S左-SL紅 進(jìn)行處理。
S涂紅是為了使h(原S->SR->葉子)不變。
對稱的情形(2) S為黑色，S為右子，SR黑
以S為支點(diǎn)右旋，交換S和SL顏色（SL涂黑，S涂紅），此時(shí)轉(zhuǎn)至2.2.1-(1) S右-SR紅進(jìn)行處理。
情形3 兄弟節(jié)點(diǎn)為紅色（S=紅）
情形(1) S為左子時(shí)，以P進(jìn)行右旋；
情形(2) S為右子時(shí)，以P進(jìn)行左旋；
旋轉(zhuǎn)后交換P和S的顏色（S涂黑，P涂紅），N兄弟節(jié)點(diǎn)變?yōu)楹谏?，進(jìn)入情形2-兄弟節(jié)點(diǎn)為黑色進(jìn)行處理。
3.刪除總結(jié)與實(shí)例
- 刪除動作（移除節(jié)點(diǎn)）之后，看看這個(gè)節(jié)點(diǎn)是不是黑色的葉子節(jié)點(diǎn)，如果不是，簡單處理就可以達(dá)到平衡了；
- 先看N是不是根節(jié)點(diǎn)，是的話啥都不用管；不是的話看兄弟什么顏色：
2.1 兄弟是紅色：進(jìn)行旋轉(zhuǎn)涂色，去到兄弟為黑色那里處理
2.2 兄弟是黑色，看看兄弟子節(jié)點(diǎn)是不是全部都是黑。
（1）全黑的話，看父什么顏色進(jìn)行對應(yīng)處理；
（2）不全黑，看兄在的位置，兄在左的話，看兄的左子是不是紅色，進(jìn)行對應(yīng)處理；兄在右的話，看兄的右子是不是紅色，進(jìn)行對應(yīng)處理。
現(xiàn)在我們有一顆紅黑樹：
（1）刪除50，刪除動作-情形3 --> 刪除動作-情形2，簡單處理即可：
（2）刪除70，即黑色葉子節(jié)點(diǎn)，進(jìn)行平衡：
（3）刪除60：
（4）刪除10：
（5）刪除20：
