紅黑樹之個(gè)人見解

在第一部分我主要向大家闡述了自己對紅黑樹基本性質(zhì)的理解和紅黑樹插入結(jié)點(diǎn)算法的解釋，都是很表面，并沒有深入探究。我必須要承認(rèn)的是，對于此，只是遵從于拿來主義，并不在其上做什么深入發(fā)展，所以，本著這個(gè)原則，我將繼續(xù)向大家說下紅黑樹刪除結(jié)點(diǎn)的具體操作過程和偽代碼解析。

先看下結(jié)點(diǎn)刪除的偽代碼吧

//RB-DELETE(T,?z)
1?if?left[z]?=?nil[T]?or?right[z]?=?nil[T]
2?then?y?←?z
3?else?y?←?TREE-SUCCESSOR(z)
4?if?left[y]?≠?nil[T]
5?then?x?←?left[y]
6?else?x?←?right[y]
7?p[x]?←?p[y]
8?if?p[y]?=?nil[T]
9?then?root[T]?←?x
10?else?if?y?=?left[p[y]]
11?then?left[p[y]]?←?x
12?else?right[p[y]]?←?x
13?if?y?3≠?z
14?then?key[z]?←?key[y]
15?copy?y's?satellite?data?into?z
16?if?color[y]?=?BLACK
17?then?RB-DELETE-FIXUP(T,?x)
18?return?y

結(jié)合下圖，我們來看看這段代碼它想干啥

在上圖中我要?jiǎng)h除結(jié)點(diǎn)12，先不看代碼，我們能想出來大概應(yīng)該怎么做嗎。我是這么想的，肯定不能14直接替換12，因?yàn)?4的右孩子是13，它比14還小，這不符合二叉排序樹的規(guī)定。11沒準(zhǔn)可以替換12的位置，然后把10作為11的左孩子，13作為11的右孩子，看起來二叉排序樹符合了，但是如果簡單地這么做，紅黑樹的性質(zhì)肯定無法滿足了，至少性質(zhì)5被破壞。那么，我們就會(huì)想到在插入結(jié)點(diǎn)這部分中有FIXUP，在刪除結(jié)點(diǎn)中也應(yīng)當(dāng)有FXIUP。正如我們期望的那樣，偽代碼中確實(shí)存在FIXUP。經(jīng)過充分地意淫之后，我們就來仔細(xì)看看偽代碼是如何把夢想轉(zhuǎn)變?yōu)楝F(xiàn)實(shí)的吧

我要?jiǎng)h除[12],代碼開始第1~3行，是說，如果[12]有一個(gè)孩子是NIL，那么y也指向[12]。否則，如果z的兩個(gè)孩子都是內(nèi)結(jié)點(diǎn)（非NIL結(jié)點(diǎn)），那么y就指向z的后繼結(jié)點(diǎn)，這里y指向[13]。然后，又出現(xiàn)了一個(gè)新變量x，它指向y的非NIL孩子結(jié)點(diǎn)，如果y的兩個(gè)孩子都是NIL，那么x指向right[y]。在這里，x指向right[13]也就是NIL。接著，代碼第7行，無條件地使x的父結(jié)點(diǎn)指向y的父結(jié)點(diǎn)，所以，現(xiàn)在x就不認(rèn)[13]是他爹了，而是認(rèn)[12]為父，但是，[13]依然視x為自己的孩子，糾結(jié)....

8~12代碼，如果y的父結(jié)點(diǎn)是NIL，那么根結(jié)點(diǎn)就指向x。這是什么情況呢。假設(shè)，我們現(xiàn)在這個(gè)紅黑樹只有一個(gè)結(jié)點(diǎn)[9]，那么這個(gè)結(jié)點(diǎn)肯定是根結(jié)點(diǎn)，y和z都指向這個(gè)根結(jié)點(diǎn)，x指向根結(jié)點(diǎn)右孩子NIL，我如果想刪除根結(jié)點(diǎn)，只需要是根結(jié)點(diǎn)指向NIL，再釋放[9]的內(nèi)存空間，那么就可以了。這就是8~9行代碼所做的。如果不是這樣，那么如果y是其父結(jié)點(diǎn)的左孩子，那么現(xiàn)在它的父結(jié)點(diǎn)就不認(rèn)它這個(gè)兒子，而認(rèn)x為兒子，如果y是右孩子，那么就其父結(jié)點(diǎn)就認(rèn)x為右孩子，總之，就是拋棄y接受x。而之前，我們已經(jīng)使x的父結(jié)點(diǎn)指向了y的父結(jié)點(diǎn)，所以，現(xiàn)在x與p[y]正式建立了父子關(guān)系，而y作為棄兒，是否應(yīng)該立馬斬草除根，free()掉呢。不行，因?yàn)槲覀円獎(jiǎng)h除的結(jié)點(diǎn)的key依然存在，所以，如果y和z不相等，我們就要把z的key改為y。最后，還要判斷，如果color[y] == Black，那么我們還要FIXUP。原因很簡單，如果y是Black，那么我們現(xiàn)在相當(dāng)于拋棄了y，那么紅黑樹的第5條性質(zhì)已然改變，所以，就需要對紅黑樹進(jìn)行修正，好了，現(xiàn)在是時(shí)候看一看RB-DELETE-FIXUP了。

//RB-DELETE-FIXUP(T,?x)
1?while?x?≠?root[T]?and?color[x]?=?BLACK
2?do?if?x?=?left[p[x]]
3?then?w?←?right[p[x]]
4?if?color[w]?=?RED
5?then?color[w]?←?BLACK???Case?1
6?color[p[x]]?←?RED???Case?1
7?LEFT-ROTATE(T,?p[x])???Case?1
8?w?←?right[p[x]]???Case?1
9?if?color[left[w]]?=?BLACK?and?color[right[w]]?=?BLACK
10?then?color[w]?←?RED???Case?2
11?x?p[x]???Case?2
12?else?if?color[right[w]]?=?BLACK
13?then?color[left[w]]?←?BLACK???Case?3
14?color[w]?←?RED???Case?3
15?RIGHT-ROTATE(T,?w)???Case?3
16?w?←?right[p[x]]???Case?3
17?color[w]?←?color[p[x]]???Case?4
18?color[p[x]]?←?BLACK???Case?4
19?color[right[w]]?←?BLACK???Case?4
20?LEFT-ROTATE(T,?p[x])???Case?4
21?x?←?root[T]???Case?4
22?else?(same?as?then?clause?with?"right"?and?"left"?exchanged)
23?color[x]?←?BLACK	

第2行，由于x是父結(jié)點(diǎn)的右孩子，因此屬于else (same as then clause with "right" and "left" exchanged)的內(nèi)容。把所有的left和right互換。這時(shí)，x是右孩子，w就是左孩子[11]。第4行，color[w] == Black，因此不屬于case1。接著往下去case2:w的兩個(gè)孩子都是黑色，也不符合，再往下去，w的左孩子黑色，右孩子紅色也不符合，所以是case4:w的左孩子是紅色，正好color[10] == Red。代碼第17行，w的顏色改為x的父結(jié)點(diǎn)的顏色，所以color[11] == Red，color[13] == Black，color[10] == Black，再以x的父結(jié)點(diǎn)13為支點(diǎn)右旋就得到了下圖

紅黑樹的性質(zhì)得以保存，我們就可以進(jìn)行下一次結(jié)點(diǎn)的插入刪除等操作了。

從以后操作可以看出，刪除結(jié)點(diǎn)操作也是很簡便的。case1,2,3的樣圖我就不再說了，大家可以參考我第一部分提的那個(gè)博客，上面說的非常詳細(xì)。

最后，有一個(gè)問題還是需要注意的。如果插入兩個(gè)相同key值的結(jié)點(diǎn)，比如插入兩個(gè)key值都為1的結(jié)點(diǎn)，那么后插入的1就會(huì)變?yōu)橹安迦氲?的右孩子，那么如果再插入一個(gè)2,就會(huì)在后插入的1的右孩子上再接一個(gè)2，如果再插入一個(gè)2呢。所以，問題就來了，如果我們插入{1, 1, 2, 2, 3, 3...}甚至，如果我們只插入{1, 1, 1, 1, 1, 1...}，那么此時(shí)構(gòu)造的紅黑樹就會(huì)沒有左子樹（NIL不計(jì)）。紅黑樹就會(huì)變得畸形地高。因此，我們需要根據(jù)個(gè)人口味的不同調(diào)制配方，使紅黑樹健康地成長為我們想要的樣子。正如Mahatma Gandhi所說：Be the change you want to see in the world!?

好了，以上就是我對紅黑樹的一點(diǎn)點(diǎn)個(gè)人見解，如果朋友們有什么好的意見和建議，一定要給我留言哦。