原諒轉(zhuǎn)載自：
http://www.cnblogs.com/skywang12345/p/3245399.html
紅黑樹(一) 原理和算法詳細(xì)介紹
作者：Sky Wang 于 2013-08-08
概述：R-B Tree，又稱為“紅黑樹”。本文參考了《算法導(dǎo)論》中紅黑樹相關(guān)知識，加之自己的理解，然后以圖文的形式對紅黑樹進(jìn)行說明。本文的主要內(nèi)容包括：紅黑樹的特性，紅黑樹的時間復(fù)雜度和它的證明，紅黑樹的左旋、右旋、插入、刪除等操作。
請尊重版權(quán)，轉(zhuǎn)載注明出處：http://www.cnblogs.com/skywang12345/p/3245399.html
1 R-B Tree簡介
R-B Tree，全稱是Red-Black Tree，又稱為“紅黑樹”，它一種特殊的二叉查找樹。紅黑樹的每個節(jié)點上都有存儲位表示節(jié)點的顏色，可以是紅(Red)或黑(Black)。
紅黑樹的特性:
（1）每個節(jié)點或者是黑色，或者是紅色。
（2）根節(jié)點是黑色。
（3）每個葉子節(jié)點（NIL）是黑色。 [注意：這里葉子節(jié)點，是指為空(NIL或NULL)的葉子節(jié)點！]
（4）如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的。
（5）從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點。
注意：
(01) 特性(3)中的葉子節(jié)點，是只為空(NIL或null)的節(jié)點。
(02) 特性(5)，確保沒有一條路徑會比其他路徑長出倆倍。因而，紅黑樹是相對是接近平衡的二叉樹。
紅黑樹示意圖如下：
紅黑樹的應(yīng)用：
紅黑樹的應(yīng)用比較廣泛，主要是用它來存儲有序的數(shù)據(jù)，它的時間復(fù)雜度是O(lgn)，效率非常之高。
例如，Java中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虛擬內(nèi)存的管理，都是通過紅黑樹去實現(xiàn)的。
這里大致介紹下，紅黑樹和AVL樹的差異。AVL樹也是特殊的二叉樹，它的特性是“任何節(jié)點的左右子樹的高度之差不超過1”。基本上，用到紅黑樹的地方都可以用AVL樹(自平衡二叉查找樹)去替換。但是一般情況下，在執(zhí)行添加、刪除節(jié)點時，AVL樹比紅黑樹執(zhí)行的操作更多一些，效率更低一些；而且紅黑樹也是相對平衡的二叉樹(從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點)。因此，紅黑樹的效率會高更一點。
2 R-B Tree時間復(fù)雜度
紅黑樹的時間復(fù)雜度為: O(lgn)
下面通過“數(shù)學(xué)歸納法”對紅黑樹的時間復(fù)雜度進(jìn)行證明。
定理：一棵含有n個節(jié)點的紅黑樹的高度至多為2log(n+1).
證明：
"一棵含有n個節(jié)點的紅黑樹的高度至多為2log(n+1)" 的逆否命題是 "高度為h的紅黑樹，它的包含的內(nèi)節(jié)點個數(shù)至少為 2^{h/2}-1個"。
我們只需要證明逆否命題，即可證明原命題為真；即只需證明 "高度為h的紅黑樹，它的包含的內(nèi)節(jié)點個數(shù)至少為 2^{h/2}-1個"。
從某個節(jié)點x出發(fā)（不包括該節(jié)點）到達(dá)一個葉節(jié)點的任意一條路徑上，黑色節(jié)點的個數(shù)稱為該節(jié)點的黑高度，記為bh(x)。
由紅黑樹的"特性(4)"可知 bh(x)>=h/2；進(jìn)而，我們只需證明 "高度為h的紅黑樹，它的包含的內(nèi)節(jié)點個數(shù)至少為 2^bh(x)-1個"即可。
到這里，我們將需要證明的定理已經(jīng)由
"一棵含有n個節(jié)點的紅黑樹的高度至多為2log(n+1)"
轉(zhuǎn)變成只需要證明
"高度為h的紅黑樹，它的包含的內(nèi)節(jié)點個數(shù)至少為 2^bh(x)-1個"。
下面通過"數(shù)學(xué)歸納法"開始論證高度為h的紅黑樹，它的包含的內(nèi)節(jié)點個數(shù)至少為 2^bh(x)-1個"。
(01) 當(dāng)樹的高度h=0時，
內(nèi)節(jié)點個數(shù)是0，bh(x) 為0，2^bh(x)-1 也為 0。顯然，原命題成立。
(02) 當(dāng)h>0，且樹的高度為 h-1 時，它包含的節(jié)點個數(shù)至少為 2^{bh(x)-1}-1。這個是根據(jù)(01)推斷出來的！
下面，由樹的高度為 h-1 的已知條件推出“樹的高度為 h 時，它所包含的節(jié)點樹為 2^bh(x)-1”。
當(dāng)樹的高度為 h 時，
對于節(jié)點x(x為根節(jié)點)，其黑高度為bh(x)。
對于節(jié)點x的左右子樹，它們黑高度為 bh(x) 或者 bh(x)-1。
根據(jù)(02)的已知條件，我們已知 "x的左右子樹，即高度為 h-1 的節(jié)點，它包含的節(jié)點至少為 2^{bh(x)-1}-1 個"；
所以，節(jié)點x所包含的節(jié)點至少為 ( 2^{bh(x)-1}-1 ) + ( 2^{bh(x)-1}-1 ) + 1 = 2^{bh(x)-1}。即節(jié)點x所包含的節(jié)點至少為 2^{bh(x)-1} 。
因此，原命題成立。
由(01)、(02)得出，"高度為h的紅黑樹，它的包含的內(nèi)節(jié)點個數(shù)至少為 2^bh(x)-1個"。
因此，“一棵含有n個節(jié)點的紅黑樹的高度至多為2log(n+1)”。
3 R-B Tree基本操作
R-B Tree的基本操作是添加、刪除。
添加和刪除操作，都會用到兩個基本的方法：左旋 和 右旋，統(tǒng)稱為旋轉(zhuǎn)。旋轉(zhuǎn)是為了保持紅黑樹的特性而提供的輔助方法，因為當(dāng)我們進(jìn)行添加、刪除節(jié)點時，可能改變紅黑樹的特性(例如，刪除一個黑色節(jié)點之后，就不滿足“從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點”這個特性)；這里，我們就需要旋轉(zhuǎn)方法的輔助來讓樹保持紅黑樹的特性。
3.1 左旋
上面是《算法導(dǎo)論》中左旋的示意圖。
參考上面的示意圖和下面的偽代碼，理解“紅黑樹T的節(jié)點x進(jìn)行左旋”是如何進(jìn)行的。
LEFT-ROTATE(T, x)
01 y ← right[x] // 前提：這里假設(shè)x的右孩子為y。下面開始正式操作
02 right[x] ← left[y] // 將 “y的左孩子” 設(shè)為 “x的右孩子”，即 將β設(shè)為x的右孩子
03 p[left[y]] ← x // 將 “x” 設(shè)為 “y的左孩子的父親”，即 將β的父親設(shè)為x
04 p[y] ← p[x] // 將 “x的父親” 設(shè)為 “y的父親”
05 if p[x] = nil[T]
06 then root[T] ← y // 情況1：如果 “x的父親” 是空節(jié)點，則將y設(shè)為根節(jié)點
07 else if x = left[p[x]]
08 then left[p[x]] ← y // 情況2：如果 x是它父節(jié)點的左孩子，則將y設(shè)為“x的父節(jié)點的左孩子”
09 else right[p[x]] ← y // 情況3：(x是它父節(jié)點的右孩子) 將y設(shè)為“x的父節(jié)點的右孩子”
10 left[y] ← x // 將 “x” 設(shè)為 “y的左孩子”
11 p[x] ← y // 將 “x的父節(jié)點” 設(shè)為 “y”
理解上面的代碼之后，下面以一個更鮮明的圖對左旋轉(zhuǎn)進(jìn)行說明。理解左旋之后，下面的推理應(yīng)該非常簡單，這里就不過多說明。
3.2 右旋
右旋和左旋是相對的，原理類似。理解左旋后，右旋也很容易理解了。
上面是《算法導(dǎo)論》中右旋的示意圖。
參考上面的示意圖和下面的偽代碼，理解“紅黑樹T的節(jié)點y進(jìn)行右旋”是如何進(jìn)行的。
RIGHT-ROTATE(T, y)
01 x ← left[y] // 前提：這里假設(shè)y的左孩子為x。下面開始正式操作
02 left[y] ← right[x] // 將 “x的右孩子” 設(shè)為 “y的左孩子”，即 將β設(shè)為y的左孩子
03 p[right[x]] ← y // 將 “y” 設(shè)為 “x的右孩子的父親”，即 將β的父親設(shè)為y
04 p[x] ← p[y] // 將 “y的父親” 設(shè)為 “x的父親”
05 if p[y] = nil[T]
06 then root[T] ← x // 情況1：如果 “y的父親” 是空節(jié)點，則將x設(shè)為根節(jié)點
07 else if y = right[p[y]]
08 then right[p[y]] ← x // 情況2：如果 y是它父節(jié)點的右孩子，則將x設(shè)為“y的父節(jié)點的左孩子”
09 else left[p[y]] ← x // 情況3：(y是它父節(jié)點的左孩子) 將x設(shè)為“y的父節(jié)點的左孩子”
10 right[x] ← y // 將 “y” 設(shè)為 “x的右孩子”
11 p[y] ← x // 將 “y的父節(jié)點” 設(shè)為 “x”
理解上面的代碼之后，下面以一個更鮮明的圖對右旋轉(zhuǎn)進(jìn)行說明。
旋轉(zhuǎn)總結(jié)：
(01) 左旋 和 右旋 是相對的兩個概念，原理類似。理解一個也就理解了另一個。
(02) 下面談?wù)勅绾螀^(qū)分 左旋 和 右旋。
在實際應(yīng)用中，若沒有徹底理解 左旋 和 右旋，可能會將它們混淆。下面談?wù)勎覍θ绾螀^(qū)分 左旋 和 右旋 的理解。
3.3 區(qū)分 左旋 和 右旋
無論 左旋 或 右旋，它們都是以某一個節(jié)點為中心點。注意：這里，我們理解成以節(jié)點(節(jié)點x)進(jìn)行旋轉(zhuǎn)，而不是以一個分支(分支xy軸 或 分支xz軸)進(jìn)行旋轉(zhuǎn)！！！
我們以圖來進(jìn)行說明。
左旋示例圖(以x為節(jié)點進(jìn)行左旋)：
z
x /
/ \ --(左旋)--> x
y z /
y對x進(jìn)行左旋，意味著，將“x的右孩子”設(shè)為“x的父親節(jié)點”；即，將 x變成了一個左節(jié)點(x成了為z的左孩子)！。 因此，左旋中的“左”，意味著“被旋轉(zhuǎn)的節(jié)點將變成一個左節(jié)點”。
右旋示例圖(以x為節(jié)點進(jìn)行右旋)：
y
x \
/ \ --(右旋)--> x
y z \
z對x進(jìn)行右旋，意味著，將“x的左孩子”設(shè)為“x的父親節(jié)點”；即，將 x變成了一個右節(jié)點(x成了為y的右孩子)！ 因此，右旋中的“右”，意味著“被旋轉(zhuǎn)的節(jié)點將變成一個右節(jié)點”。
3.4 添加操作
向一顆含有n個節(jié)點的紅黑樹中插入一個節(jié)點，可以在時間O(lgn)內(nèi)完成。
將節(jié)點z插入紅黑樹T內(nèi)。需要執(zhí)行的操作依次時：首先，將T當(dāng)作一顆二叉樹，將z插入；然后，將z著色為紅色；最后，通過RB-INSERT-FIXUP來對節(jié)點重新著色并旋轉(zhuǎn)，以此來保證刪除節(jié)點后的樹仍然是一顆紅黑樹。
(01) 將T當(dāng)作一顆二叉樹，將z插入。
因為紅黑樹本身就是一顆二叉樹，所以，我們可以根據(jù)二叉樹的性質(zhì)將z插入。
(02) 將z著色為紅色。
在介紹為什么將則著色為紅色之前，我們重新溫習(xí)一下紅黑樹的特性：
（1）每個節(jié)點或者是黑色，或者是紅色。
（2）根節(jié)點是黑色。
（3）每個葉子節(jié)點（NIL）是黑色。 [注意：這里葉子節(jié)點，是指為空(NIL或NULL)的葉子節(jié)點！]
（4）如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的。
（5）從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點。
將插入的節(jié)點著色為紅色，不會違背“特性(5)”；而若將插入的節(jié)點著色為黑色，會違背該特性。
(03) 通過RB-INSERT-FIXUP來對節(jié)點重新著色并旋轉(zhuǎn)。
因為(02)中插入一個紅色節(jié)點之后，雖然沒有違背“特性(5)”，但是卻可能違背了其它特性(例如，若被插入節(jié)點的父節(jié)點也是紅色；插入后，則違背了“特性(4)”)。我們需要通過RB-INSERT-FIXUP進(jìn)行節(jié)點顏色的調(diào)整以及旋轉(zhuǎn)等工作，讓樹仍然是一顆紅黑樹。
下面是《算法導(dǎo)論》中 “向紅黑樹T中插入節(jié)點z”的偽代碼
RB-INSERT(T, z)
01 y ← nil[T] // 新建節(jié)點“y”，將y設(shè)為空節(jié)點。
02 x ← root[T] // 設(shè)“紅黑樹T”的根節(jié)點為“x”
03 while x ≠ nil[T] // 找出要插入的節(jié)點“z”在二叉樹T中的位置“y”
04 do y ← x
05 if key[z] < key[x]
06 then x ← left[x]
07 else x ← right[x]
08 p[z] ← y // 設(shè)置 “z的父親” 為 “y”
09 if y = nil[T]
10 then root[T] ← z // 情況1：若y是空節(jié)點，則將z設(shè)為根
11 else if key[z] < key[y]
12 then left[y] ← z // 情況2：若“z所包含的值” < “y所包含的值”，則將z設(shè)為“y的左孩子”
13 else right[y] ← z // 情況3：(“z所包含的值” >= “y所包含的值”)將z設(shè)為“y的右孩子”
14 left[z] ← nil[T] // z的左孩子設(shè)為空
15 right[z] ← nil[T] // z的右孩子設(shè)為空。至此，已經(jīng)完成將“節(jié)點z插入到二叉樹”中了。
16 color[z] ← RED // 將z著色為“紅色”
17 RB-INSERT-FIXUP(T, z) // 通過RB-INSERT-FIXUP對紅黑樹的節(jié)點進(jìn)行顏色修改以及旋轉(zhuǎn)，讓樹T仍然是一顆紅黑樹
結(jié)合偽代碼以及為代碼上面的說明，先理解RB-INSERT。理解了RB-INSERT之后，我們接著對 RB-INSERT-FIXUP的偽代碼進(jìn)行說明
RB-INSERT-FIXUP(T, z)
01 while color[p[z]] = RED // 若“當(dāng)前節(jié)點(z)的父節(jié)點是紅色”，則進(jìn)行以下處理。
02 do if p[z] = left[p[p[z]]] // 若“z的父節(jié)點”是“z的祖父節(jié)點的左孩子”，則進(jìn)行以下處理。
03 then y ← right[p[p[z]]] // 將y設(shè)置為“z的叔叔節(jié)點(z的祖父節(jié)點的右孩子)”
04 if color[y] = RED // Case 1條件：叔叔是紅色
05 then color[p[z]] ← BLACK ▹ Case 1 // (01) 將“父節(jié)點”設(shè)為黑色。
06 color[y] ← BLACK ▹ Case 1 // (02) 將“叔叔節(jié)點”設(shè)為黑色。
07 color[p[p[z]]] ← RED ▹ Case 1 // (03) 將“祖父節(jié)點”設(shè)為“紅色”。
08 z ← p[p[z]] ▹ Case 1 // (04) 將“祖父節(jié)點”設(shè)為“當(dāng)前節(jié)點”(紅色節(jié)點)
09 else if z = right[p[z]] // Case 2條件：叔叔是黑色，且當(dāng)前節(jié)點是右孩子
10 then z ← p[z] ▹ Case 2 // (01) 將“父節(jié)點”作為“新的當(dāng)前節(jié)點”。
11 LEFT-ROTATE(T, z) ▹ Case 2 // (02) 以“新的當(dāng)前節(jié)點”為支點進(jìn)行左旋。
12 color[p[z]] ← BLACK ▹ Case 3 // Case 3條件：叔叔是黑色，且當(dāng)前節(jié)點是左孩子。(01) 將“父節(jié)點”設(shè)為“黑色”。
13 color[p[p[z]]] ← RED ▹ Case 3 // (02) 將“祖父節(jié)點”設(shè)為“紅色”。
14 RIGHT-ROTATE(T, p[p[z]]) ▹ Case 3 // (03) 以“祖父節(jié)點”為支點進(jìn)行右旋。
15 else (same as then clause with "right" and "left" exchanged) // 若“z的父節(jié)點”是“z的祖父節(jié)點的右孩子”，將上面的操作中“right”和“left”交換位置，然后依次執(zhí)行。
16 color[root[T]] ← BLACK
總的來說：當(dāng)節(jié)點z被著色為紅色節(jié)點，并插入二叉樹時，有三種情況。
情況一：被插入的節(jié)點是根節(jié)點。
直接把此節(jié)點涂為黑色。
情況二：被插入的節(jié)點的父節(jié)點是黑色。
什么也不需要做。節(jié)點被插入后，仍然是紅黑樹。
情況三：被插入的節(jié)點的父節(jié)點是紅色。
那么，該情況與紅黑樹的“特性(5)”相沖突。情況三包含了“Case 1”、“Case 2” 和“Case 3”三種情況，情況三的目的是恢復(fù)紅黑樹的特性，它的處理思想是：將紅色的節(jié)點移到根節(jié)點；然后，將根節(jié)點設(shè)為黑色。下面介紹情況三的三種情況。
Case 1：叔叔是紅色
Case 1 現(xiàn)象說明：當(dāng)前節(jié)點的父節(jié)點是紅色，且當(dāng)前節(jié)點的祖父節(jié)點的另一個子節(jié)點（叔叔節(jié)點）也是紅色。
Case 1 處理策略：
(01) 將“父節(jié)點”設(shè)為黑色。
(02) 將“叔叔節(jié)點”設(shè)為黑色。
(03) 將“祖父節(jié)點”設(shè)為“紅色”。
(04) 將“祖父節(jié)點”設(shè)為“當(dāng)前節(jié)點”(紅色節(jié)點)；即，之后繼續(xù)對“當(dāng)前節(jié)點”進(jìn)行操作。
下面談?wù)劄槭裁匆@樣處理。(建議理解的時候，通過下面的圖進(jìn)行對比)
“當(dāng)前節(jié)點”和“父節(jié)點”都是紅色，違背“特性(4)”。所以，將“父節(jié)點”設(shè)置“黑色”以解決這個問題。
但是，將“父節(jié)點”由“紅色”變成“黑色”之后，違背了“特性(5)”：因為，包含“父節(jié)點”的分支的黑色節(jié)點的總數(shù)增加了1。 解決這個問題的辦法是：將“祖父節(jié)點”由“黑色”變成紅色，同時，將“叔叔節(jié)點”由“紅色”變成“黑色”。關(guān)于這里，說明幾點：第一，為什么“祖父節(jié)點”之前是黑色？這個應(yīng)該很容易想明白，因為在變換操作之前，該樹是紅黑樹，“父節(jié)點”是紅色，那么“祖父節(jié)點”一定是黑色。 第二，為什么將“祖父節(jié)點”由“黑色”變成紅色，同時，將“叔叔節(jié)點”由“紅色”變成“黑色”；能解決“包含‘父節(jié)點’的分支的黑色節(jié)點的總數(shù)增加了1”的問題。這個道理也很簡單。“包含‘父節(jié)點’的分支的黑色節(jié)點的總數(shù)增加了1” 同時也意味著 “包含‘祖父節(jié)點’的分支的黑色節(jié)點的總數(shù)增加了1”，既然這樣，我們通過將“祖父節(jié)點”由“黑色”變成“紅色”以解決“包含‘祖父節(jié)點’的分支的黑色節(jié)點的總數(shù)增加了1”的問題； 但是，這樣處理之后又會引起另一個問題“包含‘叔叔’節(jié)點的分支的黑色節(jié)點的總數(shù)減少了1”，現(xiàn)在我們已知“叔叔節(jié)點”是“紅色”，將“叔叔節(jié)點”設(shè)為“黑色”就能解決這個問題。 所以，將“祖父節(jié)點”由“黑色”變成紅色，同時，將“叔叔節(jié)點”由“紅色”變成“黑色”；就解決了該問題。
按照上面的步驟處理之后：當(dāng)前節(jié)點、父節(jié)點、叔叔節(jié)點之間都不會違背紅黑樹特性，但祖父節(jié)點卻不一定。若此時，祖父節(jié)點是根節(jié)點，直接將祖父節(jié)點設(shè)為“黑色”，那就完全解決這個問題了；若祖父節(jié)點不是根節(jié)點，那我們需要將“祖父節(jié)點”設(shè)為“新的當(dāng)前節(jié)點”，接著對“新的當(dāng)前節(jié)點”進(jìn)行分析。
Case 1 處理前[當(dāng)前節(jié)點是4]：
Case 1 處理后：
Case 2：叔叔是黑色，且當(dāng)前節(jié)點是右孩子
Case 2 現(xiàn)象說明：當(dāng)前節(jié)點的父節(jié)點是紅色，叔叔節(jié)點是黑色，且當(dāng)前節(jié)點是其父節(jié)點的右孩子
Case 2 處理策略：
(01) 將“父節(jié)點”作為“新的當(dāng)前節(jié)點”。
(02) 以“新的當(dāng)前節(jié)點”為支點進(jìn)行左旋。
下面談?wù)劄槭裁匆@樣處理。(建議理解的時候，通過下面的圖進(jìn)行對比)
首先，將“父節(jié)點”作為“新的當(dāng)前節(jié)點”；接著，以“新的當(dāng)前節(jié)點”為支點進(jìn)行左旋。 為了便于理解，我們先說明第(02)步，再說明第(01)步；為了便于說明，我們設(shè)置“父節(jié)點”的代號為F(Father)，“當(dāng)前節(jié)點”的代號為S(Son)。
為什么要“以F為支點進(jìn)行左旋”呢？根據(jù)已知條件可知：S是F的右孩子。而之前我們說過，我們處理紅黑樹的核心思想：將紅色的節(jié)點移到根節(jié)點；然后，將根節(jié)點設(shè)為黑色。既然是“將紅色的節(jié)點移到根節(jié)點”，那就是說要不斷的將破壞紅黑樹特性的紅色節(jié)點上移(即向根方向移動)。 而S又是一個右孩子，因此，我們可以通過“左旋”來將S上移！
按照上面的步驟(以F為支點進(jìn)行左旋)處理之后：若S變成了根節(jié)點，那么直接將其設(shè)為“黑色”，就完全解決問題了；若S不是根節(jié)點，那我們需要執(zhí)行步驟(01)，即“將F設(shè)為‘新的當(dāng)前節(jié)點’”。那為什么不繼續(xù)以S為新的當(dāng)前節(jié)點繼續(xù)處理，而需要以F為新的當(dāng)前節(jié)點來進(jìn)行處理呢？這是因為“左旋”之后，F(xiàn)變成了S的“子節(jié)點”，即S變成了F的父節(jié)點；而我們處理問題的時候，需要從下至上(由葉到根)方向進(jìn)行處理；也就是說，必須先解決“孩子”的問題，再解決“父親”的問題；所以，我們執(zhí)行步驟(01)：將“父節(jié)點”作為“新的當(dāng)前節(jié)點”。
Case 2 處理前[當(dāng)前節(jié)點是7]：
Case 2處理后：
Case 3：叔叔是黑色，且當(dāng)前節(jié)點是左孩子
Case 3：叔叔是黑色，且當(dāng)前節(jié)點是左孩子
Case 3 現(xiàn)象說明：當(dāng)前節(jié)點的父節(jié)點是紅色，叔叔節(jié)點是黑色，且當(dāng)前節(jié)點是其父節(jié)點的左孩子
Case 3 處理策略：
(01) 將“父節(jié)點”設(shè)為“黑色”。
(02) 將“祖父節(jié)點”設(shè)為“紅色”。
(03) 以“祖父節(jié)點”為支點進(jìn)行右旋。
下面談?wù)劄槭裁匆@樣處理。(建議理解的時候，通過下面的圖進(jìn)行對比)
為了便于說明，我們設(shè)置“當(dāng)前節(jié)點”為S(Original Son)，“兄弟節(jié)點”為B(Brother)，“叔叔節(jié)點”為U(Uncle)，“父節(jié)點”為F(Father)，祖父節(jié)點為G(Grand-Father)。
S和F都是紅色，違背了紅黑樹的“特性(4)”，我們可以將F由“紅色”變?yōu)?#8220;黑色”，就解決了“違背‘特性(4)’”的問題；但卻引起了其它問題：違背特性(5)，因為將F由紅色改為黑色之后，所有經(jīng)過F的分支的黑色節(jié)點的個數(shù)增加了1。那我們?nèi)绾谓鉀Q“所有經(jīng)過F的分支的黑色節(jié)點的個數(shù)增加了1”的問題呢？ 我們可以通過“將G由黑色變成紅色”，同時“以G為支點進(jìn)行右旋”來解決。
Case 3 處理前[當(dāng)前節(jié)點是2]：
Case 3 處理后：
3.5 刪除操作
將紅黑樹T內(nèi)的節(jié)點z刪除。需要執(zhí)行的操作依次是：首先，將T當(dāng)作一顆二叉樹，將節(jié)點刪除；然后，通過RB-DELETE-FIXUP來對節(jié)點重新著色并旋轉(zhuǎn)，以此來保證刪除節(jié)點后的樹仍然是一顆紅黑樹。
(01) 將T當(dāng)作一顆二叉樹，將節(jié)點刪除。
這和"刪除常規(guī)二叉搜索樹中刪除節(jié)點的方法是一樣的"。分3種情況：
第一種，被刪除節(jié)點沒有兒子，即為葉節(jié)點。那么，直接將該節(jié)點刪除就OK了。
第二種，被刪除節(jié)點只有一個兒子。那么，直接刪除該節(jié)點，并用該節(jié)點的唯一子節(jié)點頂替它的位置。
第三種，被刪除節(jié)點有兩個兒子。那么，首先把“它的后繼節(jié)點的內(nèi)容”復(fù)制給“該節(jié)點的內(nèi)容”；之后，刪除“它的后繼節(jié)點”。
這里有兩點需要說明：第一步中復(fù)制時，僅僅復(fù)制內(nèi)容，即將“它的后繼節(jié)點的內(nèi)容”復(fù)制給“該節(jié)點的內(nèi)容”。 這相當(dāng)于用“該節(jié)點的后繼節(jié)點”取代“該節(jié)點”，之后就刪除“該節(jié)點的后繼節(jié)點”即可，而不需要刪除“該節(jié)點”(因為“該節(jié)點”已經(jīng)被“它的后繼節(jié)點”所取代)。
第二步中刪除“該節(jié)點的后繼節(jié)點”時，需要注意：“該節(jié)點的后繼節(jié)點”不可能是雙子非空，這個根據(jù)二叉樹的特性可知。 既然“該節(jié)點的后繼節(jié)點”不可能雙子都非空，就意味著“該節(jié)點的后繼節(jié)點”要么沒有兒子，要么只有一個兒子。若沒有兒子，則按“第一種”種的辦法進(jìn)行處理；若只有一個兒子，則按“第二種”中的辦法進(jìn)行處理。
(02) 通過RB-DELETE-FIXUP來對節(jié)點重新著色并旋轉(zhuǎn)，以此來保證刪除節(jié)點后的樹仍然是一顆紅黑樹。
因為(01)中刪除節(jié)點之后，可能會違背紅黑樹的特性。所以需要，通過RB-DELETE-FIXUP來重新校正，為當(dāng)前樹保持紅黑樹的特性。
下面是《算法導(dǎo)論》中 “從紅黑樹T中刪除節(jié)點z”的偽代碼
RB-DELETE(T, z)
01 if left[z] = nil[T] or right[z] = nil[T]
02 then y ← z // 若“z的左孩子” 或 “z的右孩子”為空，則將“z”賦值給 “y”；
03 else y ← TREE-SUCCESSOR(z) // 否則，將“z的后繼節(jié)點”賦值給 “y”。
04 if left[y] ≠ nil[T]
05 then x ← left[y] // 若“y的左孩子” 不為空，則將“y的左孩子” 賦值給 “x”；
06 else x ← right[y] // 否則，“y的右孩子” 賦值給 “x”。
07 p[x] ← p[y] // 將“y的父節(jié)點” 設(shè)置為 “x的父節(jié)點”
08 if p[y] = nil[T]
09 then root[T] ← x // 情況1：若“y的父節(jié)點” 為空，則設(shè)置“x” 為 “根節(jié)點”。
10 else if y = left[p[y]]
11 then left[p[y]] ← x // 情況2：若“y是它父節(jié)點的左孩子”，則設(shè)置“x” 為 “y的父節(jié)點的左孩子”
12 else right[p[y]] ← x // 情況3：若“y是它父節(jié)點的右孩子”，則設(shè)置“x” 為 “y的父節(jié)點的右孩子”
13 if y ≠ z
14 then key[z] ← key[y] // 若“y的值” 賦值給 “z”。注意：這里只拷貝z的值給y，而沒有拷貝z的顏色！！！
15 copy y's satellite data into z
16 if color[y] = BLACK
17 then RB-DELETE-FIXUP(T, x) // 若“y為黑節(jié)點”，則調(diào)用
18 return y
結(jié)合偽代碼以及為代碼上面的說明，先理解RB-DELETE。理解了RB-DELETE之后，接著對 RB-DELETE-FIXUP的偽代碼進(jìn)行說明
RB-DELETE-FIXUP(T, x)
01 while x ≠ root[T] and color[x] = BLACK
02 do if x = left[p[x]]
03 then w ← right[p[x]] // 若 “x”是“它父節(jié)點的左孩子”，則設(shè)置 “w”為“x的叔叔”(即x為它父節(jié)點的右孩子)
04 if color[w] = RED // Case 1: x是“黑+黑”節(jié)點，x的兄弟節(jié)點是紅色。(此時x的父節(jié)點和x的兄弟節(jié)點的子節(jié)點都是黑節(jié)點)。
05 then color[w] ← BLACK ▹ Case 1 // (01) 將x的兄弟節(jié)點設(shè)為“黑色”。
06 color[p[x]] ← RED ▹ Case 1 // (02) 將x的父節(jié)點設(shè)為“紅色”。
07 LEFT-ROTATE(T, p[x]) ▹ Case 1 // (03) 對x的父節(jié)點進(jìn)行左旋。
08 w ← right[p[x]] ▹ Case 1 // (04) 左旋后，重新設(shè)置x的兄弟節(jié)點。
09 if color[left[w]] = BLACK and color[right[w]] = BLACK // Case 2: x是“黑+黑”節(jié)點，x的兄弟節(jié)點是黑色，x的兄弟節(jié)點的兩個孩子都是黑色。
10 then color[w] ← RED ▹ Case 2 // (01) 將x的兄弟節(jié)點設(shè)為“紅色”。
11 x ← p[x] ▹ Case 2 // (02) 設(shè)置“x的父節(jié)點”為“新的x節(jié)點”。
12 else if color[right[w]] = BLACK // Case 3: x是“黑+黑”節(jié)點，x的兄弟節(jié)點是黑色；x的兄弟節(jié)點的左孩子是紅色，右孩子是黑色的。
13 then color[left[w]] ← BLACK ▹ Case 3 // (01) 將x兄弟節(jié)點的左孩子設(shè)為“黑色”。
14 color[w] ← RED ▹ Case 3 // (02) 將x兄弟節(jié)點設(shè)為“紅色”。
15 RIGHT-ROTATE(T, w) ▹ Case 3 // (03) 對x的兄弟節(jié)點進(jìn)行右旋。
16 w ← right[p[x]] ▹ Case 3 // (04) 右旋后，重新設(shè)置x的兄弟節(jié)點。
17 color[w] ← color[p[x]] ▹ Case 4 // Case 4: x是“黑+黑”節(jié)點，x的兄弟節(jié)點是黑色；x的兄弟節(jié)點的右孩子是紅色的。(01) 將x父節(jié)點顏色 賦值給 x的兄弟節(jié)點。
18 color[p[x]] ← BLACK ▹ Case 4 // (02) 將x父節(jié)點設(shè)為“黑色”。
19 color[right[w]] ← BLACK ▹ Case 4 // (03) 將x兄弟節(jié)點的右子節(jié)設(shè)為“黑色”。
20 LEFT-ROTATE(T, p[x]) ▹ Case 4 // (04) 對x的父節(jié)點進(jìn)行左旋。
21 x ← root[T] ▹ Case 4 // (05) 設(shè)置“x”為“根節(jié)點”。
22 else (same as then clause with "right" and "left" exchanged) // 若 “x”是“它父節(jié)點的右孩子”，將上面的操作中“right”和“left”交換位置，然后依次執(zhí)行。
23 color[x] ← BLACK
在開始說明RB-DELETE-FIXUP之前，我們再次溫習(xí)一下紅黑樹的幾個特性：
（1）每個節(jié)點或者是黑色，或者是紅色。
（2）根節(jié)點是黑色。
（3）每個葉子節(jié)點（NIL）是黑色。 [注意：這里葉子節(jié)點，是指為空(NIL或NULL)的葉子節(jié)點！]
（4）如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的。
（5）從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點。
在RB-DELETE中，若被刪除的節(jié)點y是黑色的，則會產(chǎn)生三個問題。
問題一：如y是根節(jié)點，而刪除y后，它的紅色孩子成了新的根節(jié)點，則違反了“特性(2)”。
問題二：如x和“y的父節(jié)點”都是紅色，則違反了“特性(4)”。因為刪除y之后，“y的父節(jié)點”和“x”是父子關(guān)系。
問題三：刪除y，意味著刪除了一個黑色節(jié)點，那么“之前所有包含y的路徑上的黑節(jié)點總數(shù)減少了1”，這違反了“特性(5)”。
合計起來，違反了“特性(2)、(4)、(5)”三個特性。
RB-DELETE-FIXUP需要解決上面的三個問題，進(jìn)而保持紅黑樹的全部特性。
為了便于分析，我們假設(shè)“x包含一個額外的黑色”(x原本的顏色還存在)，這樣就不會違反“特性(5)”。為什么呢？
通過RB-DELETE算法，我們知道：刪除節(jié)點y之后，x占據(jù)了原來節(jié)點y的位置。 既然刪除y(y是黑色)，意味著減少一個黑色節(jié)點；那么，再在該位置上增加一個黑色即可。這樣，當(dāng)我們假設(shè)“x包含一個額外的黑色”，就正好彌補(bǔ)了“刪除y所丟失的黑色節(jié)點”，也就不會違反“特性(5)”。 因此，假設(shè)“x包含一個額外的黑色”(x原本的顏色還存在)，這樣就不會違反“特性(5)”。
現(xiàn)在，x不僅包含它原本的顏色屬性，x還包含一個額外的黑色。即x的顏色屬性是“紅+黑”或“黑+黑”，它違反了“特性(1)”。
現(xiàn)在，我們面臨的問題，由解決“違反了特性(2)、(4)、(5)三個特性”轉(zhuǎn)換成了“解決違反特性(1)、(2)、(4)三個特性”。
RB-DELETE-FIXUP就是通過算法恢復(fù)紅黑樹的特性(1)、(2)、(4)。RB-DELETE-FIXUP的思想是：將x所包含的額外的黑色不斷沿樹上移(向根方向移動)，直到：
(01) x指向一個“紅+黑”節(jié)點。此時，將x設(shè)為一個“黑”節(jié)點即可。
(02) x指向根。此時，將x設(shè)為一個“黑”節(jié)點即可。
(03) 做必要的旋轉(zhuǎn)和顏色修改。
將上面的思想，可以概括為3種情況。
情況一：x是“紅+黑”節(jié)點。
直接把x設(shè)為黑色，結(jié)束。此時紅黑樹性質(zhì)全部恢復(fù)。
情況二：x是“黑+黑”節(jié)點，且x是根。
什么都不做，結(jié)束。此時紅黑樹性質(zhì)全部恢復(fù)。
情況三：x是“黑+黑”節(jié)點，且x不是根。這又可以劃分了4種情況：Case 1、Case 2、Case 3、Case 4。
Case 1
Case 1 現(xiàn)象說明：x是“黑+黑”節(jié)點，x的兄弟節(jié)點是紅色。(此時x的父節(jié)點和x的兄弟節(jié)點的子節(jié)點都是黑節(jié)點)。
Case 1 處理策略：
(01) 將x的兄弟節(jié)點設(shè)為“黑色”。
(02) 將x的父節(jié)點設(shè)為“紅色”。
(03) 對x的父節(jié)點進(jìn)行左旋。
(04) 左旋后，重新設(shè)置x的兄弟節(jié)點。
下面談?wù)劄槭裁匆@樣處理。(建議理解的時候，通過下面的圖進(jìn)行對比)
這樣做的目的是將“Case 1”轉(zhuǎn)換為“Case 2”、“Case 3”或“Case 4”，從而進(jìn)行進(jìn)一步的處理。對x的父節(jié)點進(jìn)行左旋；左旋后，為了保持紅黑樹特性，就需要在左旋前“將x的兄弟節(jié)點設(shè)為黑色”，同時“將x的父節(jié)點設(shè)為紅色”；左旋后，由于x的兄弟節(jié)點發(fā)生了變化，需要更新x的兄弟節(jié)點，從而進(jìn)行后續(xù)處理。
Case 1 處理前[當(dāng)前節(jié)點是A]：
Case 1 處理后：
Case 2
Case 2 現(xiàn)象說明：x是“黑+黑”節(jié)點，x的兄弟節(jié)點是黑色，x的兄弟節(jié)點的兩個孩子都是黑色。
Case 2 處理策略：
(01) 將x的兄弟節(jié)點設(shè)為“紅色”。
(02) 設(shè)置“x的父節(jié)點”為“新的x節(jié)點”。
下面談?wù)劄槭裁匆@樣處理。(建議理解的時候，通過下面的圖進(jìn)行對比)
這個情況的處理思想：是將“x中多余的一個黑色屬性上移(往根方向移動)”。 x是“黑+黑”節(jié)點，我們將x由“黑+黑”節(jié)點 變成 “黑”節(jié)點，多余的一個“黑”屬性移到x的父節(jié)點中，即x的父節(jié)點多出了一個黑屬性(若x的父節(jié)點原先是“黑”，則此時變成了“黑+黑”；若x的父節(jié)點原先時“紅”，則此時變成了“紅+黑”)。 此時，需要注意的是：所有經(jīng)過x的分支中黑節(jié)點個數(shù)沒變化；但是，所有經(jīng)過x的兄弟節(jié)點的分支中黑色節(jié)點的個數(shù)增加了1(因為x的父節(jié)點多了一個黑色屬性)！為了解決這個問題，我們需要將“所有經(jīng)過x的兄弟節(jié)點的分支中黑色節(jié)點的個數(shù)減1”即可，那么就可以通過“將x的兄弟節(jié)點由黑色變成紅色”來實現(xiàn)。
經(jīng)過上面的步驟(將x的兄弟節(jié)點設(shè)為紅色)，多余的一個顏色屬性(黑色)已經(jīng)跑到x的父節(jié)點中。我們需要將x的父節(jié)點設(shè)為“新的x節(jié)點”進(jìn)行處理。若“新的x節(jié)點”是“黑+紅”，直接將“新的x節(jié)點”設(shè)為黑色，即可完全解決該問題；若“新的x節(jié)點”是“黑+黑”，則需要對“新的x節(jié)點”進(jìn)行進(jìn)一步處理。
Case 2 處理前[當(dāng)前節(jié)點是A]：
Case 2 處理后：
Case 3
Case 3 現(xiàn)象說明：x是“黑+黑”節(jié)點，x的兄弟節(jié)點是黑色；x的兄弟節(jié)點的左孩子是紅色，右孩子是黑色的。
Case 3 處理策略：
(01) 將x兄弟節(jié)點的左孩子設(shè)為“黑色”。
(02) 將x兄弟節(jié)點設(shè)為“紅色”。
(03) 對x的兄弟節(jié)點進(jìn)行右旋。
(04) 右旋后，重新設(shè)置x的兄弟節(jié)點。
下面談?wù)劄槭裁匆@樣處理。(建議理解的時候，通過下面的圖進(jìn)行對比)
我們處理“Case 3”的目的是為了將“Case 3”進(jìn)行轉(zhuǎn)換，轉(zhuǎn)換成“Case 4”,從而進(jìn)行進(jìn)一步的處理。轉(zhuǎn)換的方式是對x的兄弟節(jié)點進(jìn)行右旋；為了保證右旋后，它仍然是紅黑樹，就需要在右旋前“將x的兄弟節(jié)點的左孩子設(shè)為黑色”，同時“將x的兄弟節(jié)點設(shè)為紅色”；右旋后，由于x的兄弟節(jié)點發(fā)生了變化，需要更新x的兄弟節(jié)點，從而進(jìn)行后續(xù)處理。
Case 3 處理前[當(dāng)前節(jié)點是A]：
Case 3 處理后：
Case 4
Case 4 現(xiàn)象說明：x是“黑+黑”節(jié)點，x的兄弟節(jié)點是黑色；x的兄弟節(jié)點的左孩子是紅色，右孩子是黑色的。
Case 4 現(xiàn)象說明：x是“黑+黑”節(jié)點，x的兄弟節(jié)點是黑色；x的兄弟節(jié)點的右孩子是紅色的。
Case 4 處理策略：
(01) 將x父節(jié)點顏色 賦值給 x的兄弟節(jié)點。
(02) 將x父節(jié)點設(shè)為“黑色”。
(03) 將x兄弟節(jié)點的右子節(jié)設(shè)為“黑色”。
(04) 對x的父節(jié)點進(jìn)行左旋。
(05) 設(shè)置“x”為“根節(jié)點”。
下面談?wù)劄槭裁匆@樣處理。(建議理解的時候，通過下面的圖進(jìn)行對比)
我們處理“Case 4”的目的是：去掉x中額外的黑色，將x變成單獨的黑色。處理的方式是“：進(jìn)行顏色修改，然后對x的父節(jié)點進(jìn)行左旋。下面，我們來分析是如何實現(xiàn)的。
為了便于說明，我們設(shè)置“當(dāng)前節(jié)點”為S(Original Son)，“兄弟節(jié)點”為B(Brother)，“兄弟節(jié)點的左孩子”為BLS(Brother's Left Son)，“兄弟節(jié)點的右孩子”為BRS(Brother's Right Son)，“父節(jié)點”為F(Father)。
我們要對F進(jìn)行左旋。但在左旋前，我們需要調(diào)換F和B的顏色，并設(shè)置BRS為黑色。為什么需要這里處理呢？因為左旋后，F(xiàn)和BLS是父子關(guān)系，而我們已知BL是紅色，如果F是紅色，則違背了“特性(4)”；為了解決這一問題，我們將“F設(shè)置為黑色”。 但是，F(xiàn)設(shè)置為黑色之后，為了保證滿足“特性(5)”，即為了保證左旋之后：
第一，“同時經(jīng)過根節(jié)點和S的分支的黑色節(jié)點個數(shù)不變”。
若滿足“第一”，只需要S丟棄它多余的顏色即可。因為S的顏色是“黑+黑”，而左旋后“同時經(jīng)過根節(jié)點和S的分支的黑色節(jié)點個數(shù)”增加了1；現(xiàn)在，只需將S由“黑+黑”變成單獨的“黑”節(jié)點，即可滿足“第一”。
第二，“同時經(jīng)過根節(jié)點和BLS的分支的黑色節(jié)點數(shù)不變”。
若滿足“第二”，只需要將“F的原始顏色”賦值給B即可。之前，我們已經(jīng)將“F設(shè)置為黑色”(即，將B的顏色"黑色"，賦值給了F)。至此，我們算是調(diào)換了F和B的顏色。
第三，“同時經(jīng)過根節(jié)點和BRS的分支的黑色節(jié)點數(shù)不變”。
在“第二”已經(jīng)滿足的情況下，若要滿足“第三”，只需要將BRS設(shè)置為“黑色”即可。
經(jīng)過，上面的處理之后。紅黑樹的特性全部得到的滿足！接著，我們將x設(shè)為根節(jié)點，就可以跳出while循環(huán)(參考偽代碼)；即完成了全部處理。
至此，我們就完成了Case 4的處理。理解Case 4的核心，是了解如何“去掉當(dāng)前節(jié)點額外的黑色”。
Case 4 處理前[當(dāng)前節(jié)點是A]：
Case 4 處理后：
OK！至此，紅黑樹的理論知識差不多講完了。后續(xù)再更新紅黑樹的實現(xiàn)代碼！
參考文獻(xiàn)
1, 《算法導(dǎo)論》
2, 教你透徹了解紅黑樹