教你初步了解紅黑樹
本文參考：Google、算法導論、STL源碼剖析、計算機程序設計藝術。
推薦閱讀：
- Left-Leaning Red-Black Trees, Dagstuhl Workshop on Data Structures, Wadern, Germany, February, 2008，直接下載：http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf。
- 本文的github優化版：https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md。
一、紅黑樹的介紹
先來看下算法導論對R-B Tree的介紹：
紅黑樹，一種二叉查找樹，但在每個結點上增加一個存儲位表示結點的顏色，可以是Red或Black。
通過對任何一條從根到葉子的路徑上各個結點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，因而是接近平衡的。
紅黑樹，作為一棵二叉查找樹，滿足二叉查找樹的一般性質。下面，來了解下 二叉查找樹的一般性質。
二叉查找樹
二叉查找樹，也稱有序二叉樹（ordered binary tree），或已排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質的二叉樹：
- 若任意節點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
- 若任意節點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
- 任意節點的左、右子樹也分別為二叉查找樹。
- 沒有鍵值相等的節點（no duplicate nodes）。
因為一棵由n個結點隨機構造的二叉查找樹的高度為lgn，所以順理成章，二叉查找樹的一般操作的執行時間為O(lgn)。但二叉查找樹若退化成了一棵具有n個結點的線性鏈后，則這些操作最壞情況運行時間為O(n)。
紅黑樹雖然本質上是一棵二叉查找樹，但它在二叉查找樹的基礎上增加了著色和相關的性質使得紅黑樹相對平衡，從而保證了紅黑樹的查找、插入、刪除的時間復雜度最壞為O(log n)。
但它是如何保證一棵n個結點的紅黑樹的高度始終保持在logn的呢？這就引出了紅黑樹的5個性質：
- 每個結點要么是紅的要么是黑的。
- 根結點是黑的。
- 每個葉結點（葉結點即指樹尾端NIL指針或NULL結點）都是黑的。
- 如果一個結點是紅的，那么它的兩個兒子都是黑的。
- 對于任意結點而言，其到葉結點樹尾端NIL指針的每條路徑都包含相同數目的黑結點。
正是紅黑樹的這5條性質，使一棵n個結點的紅黑樹始終保持了logn的高度，從而也就解釋了上面所說的“紅黑樹的查找、插入、刪除的時間復雜度最壞為O(log n)”這一結論成立的原因。
（注：上述第3、5點性質中所說的NULL結點，包括wikipedia.算法導論上所認為的葉子結點即為樹尾端的NIL指針，或者說NULL結點。然百度百科以及網上一些其它博文直接說的葉結點，則易引起誤會，因，此葉結點非子結點）
如下圖所示，即是一顆紅黑樹(下圖引自wikipedia：http://t.cn/hgvH1l)：
此圖忽略了葉子和根部的父結點。同時，上文中我們所說的 "葉結點" 或"NULL結點"，如上圖所示，它不包含數據而只充當樹在此結束的指示，這些節點在繪圖中經常被省略，望看到此文后的讀者朋友注意。
二、樹的旋轉知識
當在對紅黑樹進行插入和刪除等操作時，對樹做了修改可能會破壞紅黑樹的性質。為了繼續保持紅黑樹的性質，可以通過對結點進行重新著色，以及對樹進行相關的旋轉操作，即通過修改樹中某些結點的顏色及指針結構，來達到對紅黑樹進行插入或刪除結點等操作后繼續保持它的性質或平衡的目的。
樹的旋轉分為左旋和右旋，下面借助圖來介紹一下左旋和右旋這兩種操作。
1.左旋
如上圖所示，當在某個結點pivot上，做左旋操作時，我們假設它的右孩子y不是NIL[T]，pivot可以為任何不是NIL[T]的左子結點。左旋以pivot到Y之間的鏈為“支軸”進行，它使Y成為該子樹的新根，而Y的左孩子b則成為pivot的右孩子。
LeftRoate(T, x)
y ← x.right //定義y：y是x的右孩子
x.right ← y.left //y的左孩子成為x的右孩子
if y.left ≠ T.nil
y.left.p ← x
y.p ← x.p //x的父結點成為y的父結點
if x.p = T.nil
then T.root ← y
else if x = x.p.left
then x.p.left ← y
else x.p.right ← y
y.left ← x //x作為y的左孩子
x.p ← y
2.右旋
右旋與左旋差不多，再此不做詳細介紹。
樹在經過左旋右旋之后，樹的搜索性質保持不變，但樹的紅黑性質則被破壞了，所以，紅黑樹插入和刪除數據后，需要利用旋轉與顏色重涂來重新恢復樹的紅黑性質。
至于有些書如《STL源碼剖析》有對雙旋的描述，其實雙旋只是單旋的兩次應用，并無新的內容，因此這里就不再介紹了，而且左右旋也是相互對稱的，只要理解其中一種旋轉就可以了。
三、紅黑樹的插入
要真正理解紅黑樹的插入，還得先理解二叉查找樹的插入。磨刀不誤砍柴工，咱們再來了解一下二叉查找樹的插入和紅黑樹的插入。
如果要在二叉查找樹中插入一個結點，首先要查找到結點要插入的位置，然后進行插入。假設插入的結點為z的話，插入的偽代碼如下：
TREE-INSERT(T, z)
y ← NIL
x ← T.root
while x ≠ NIL
do y ← x
if z.key < x.key
then x ← x.left
else x ← x.right
z.p ← y
if y == NIL
then T.root ← z
else if z.key < y.key
then y.left ← z
else y.right ← z
紅黑樹的插入和插入修復
現在我們了解了二叉查找樹的插入，接下來，咱們便來具體了解下紅黑樹的插入操作。紅黑樹的插入相當于在二叉查找樹插入的基礎上，為了重新恢復平衡，繼續做了插入修復操作。
假設插入的結點為z，紅黑樹的插入偽代碼具體如下所示：
RB-INSERT(T, z)
y ← nil
x ← T.root
while x ≠ T.nil
do y ← x
if z.key < x.key
then x ← x.left
else x ← x.right
z.p ← y
if y == nil[T]
then T.root ← z
else if z.key < y.key
then y.left ← z
else y.right ← z
z.left ← T.nil
z.right ← T.nil
z.color ← RED
RB-INSERT-FIXUP(T, z)
把上面這段紅黑樹的插入代碼，跟之前看到的二叉查找樹的插入代碼比較一下可以看出，RB-INSERT(T, z)前面的第1～13行代碼基本上就是二叉查找樹的插入代碼，然后第14～16行代碼把z的左孩子和右孩子都賦為葉結點nil，再把z結點著為紅色，最后為保證紅黑性質在插入操作后依然保持，調用一個輔助程序RB-INSERT-FIXUP來對結點進行重新著色，并旋轉。
換言之，如果插入的是根結點，由于原樹是空樹，此情況只會違反性質2，因此直接把此結點涂為黑色；如果插入的結點的父結點是黑色，由于此不會違反性質2和性質4，紅黑樹沒有被破壞，所以此時什么也不做。
但當遇到下述3種情況時又該如何調整呢？
-
● 插入修復情況1：如果當前結點的父結點是紅色且祖父結點的另一個子結點（叔叔結點）是紅色
● 插入修復情況2：當前節點的父節點是紅色,叔叔節點是黑色，當前節點是其父節點的右子
● 插入修復情況3：當前節點的父節點是紅色,叔叔節點是黑色，當前節點是其父節點的左子
答案就是根據紅黑樹插入代碼RB-INSERT(T, z)最后一行調用的RB-INSERT-FIXUP ( T , z )函數 所示 的步驟進行操作 ，具體如下所示：
RB-INSERT-FIXUP(T, z)
while z.p.color == RED
do if z.p == z.p.p.left
then y ← z.p.p.right
if y.color == RED
then z.p.color ← BLACK ? Case 1
y.color ← BLACK ? Case 1
z.p.p.color ← RED ? Case 1
z ← z.p.p ? Case 1
else if z == z.p.right
then z ← z.p ? Case 2
LEFT-ROTATE(T, z) ? Case 2
z.p.color ← BLACK ? Case 3
z.p.p.color ← RED ? Case 3
RIGHT-ROTATE(T, z.p.p) ? Case 3
else (same as then clause with "right" and "left" exchanged)
T.root.color ← BLACK
下面，咱們來分別處理上述3種插入修復情況。
- 插入修復情況1：當前結點的父結點是紅色，祖父結點的另一個子結點（叔叔結點）是紅色。
如下代碼所示：
while z.p.color == RED
do if z.p == z.p.p.left
then y ← z.p.p.right
if y.color == RED
此時父結點的父結點一定存在，否則插入前就已不是紅黑樹。與此同時，又分為父結點是祖父結點的左孩子還是右孩子，根據對稱性，我們只要解開一個方向就可以了。這里只考慮父結點為祖父左孩子的情況，如下圖所示。
對此，我們的解決策略是：將當前節點的父節點和叔叔節點涂黑，祖父結點涂紅，把當前結點指向祖父節點，從新的當前節點重新開始算法。即如下代碼所示：
then z.p.color ← BLACK ? Case 1
y.color ← BLACK ? Case 1
z.p.p.color ← RED ? Case 1
z ← z.p.p ? Case 1
所以，變化后如下圖所示：
于是，插入修復情況1轉換成了插入修復情況2。
- 插入修復情況2：當前節點的父節點是紅色,叔叔節點是黑色，當前節點是其父節點的右子
此時，解決對策是：當前節點的父節點做為新的當前節點，以新當前節點為支點左旋。即如下代碼所示：
else if z == z.p.right
then z ← z.p ? Case 2
LEFT-ROTATE(T, z) ? Case 2
所以紅黑樹由之前的：
變化成：
從而插入修復情況2轉換成了插入修復情況3。
- 插入修復情況3：當前節點的父節點是紅色,叔叔節點是黑色，當前節點是其父節點的左孩子
解決對策是：父節點變為黑色，祖父節點變為紅色，在祖父節點為支點右旋，操作代碼為：
z.p.color ← BLACK ? Case 3
z.p.p.color ← RED ? Case 3
RIGHT-ROTATE(T, z.p.p) ? Case 3
最后，把根結點涂為黑色，整棵紅黑樹便重新恢復了平衡。所以紅黑樹由之前的：
變化成：
「回顧：經過上面情況3、情況4、情況5等3種插入修復情況的操作示意圖，讀者自會發現，后面的情況4、情況5都是針對情況3插入節點4以后，進行的一系列插入修復情況操作，不過，指向當前節點N指針一直在變化。所以，你可以想當然的認為：整個下來，情況3、4、5就是一個完整的插入修復情況的操作流程」
四、紅黑樹的刪除
接下來，咱們最后來了解，紅黑樹的刪除操作。
"我們刪除的節點的方法與常規二叉搜索樹中刪除節點的方法是一樣的，如果被刪除的節點不是有雙非空子女，則直接刪除這個節點，用它的唯一子節點頂替它的位置，如果它的子節點分是空節點，那就用空節點頂替它的位置，如果它的雙子全為非空，我們就把它的直接后繼節點內容復制到它的位置，之后以同樣的方式刪除它的后繼節點，它的后繼節點不可能是雙子非空，因此此傳遞過程最多只進行一次。”
二叉查找樹的刪除
繼續講解之前，補充說明下二叉樹結點刪除的幾種情況，待刪除的節點按照兒子的個數可以分為三種：
- 沒有兒子，即為葉結點。直接把父結點的對應兒子指針設為NULL，刪除兒子結點就OK了。
- 只有一個兒子。那么把父結點的相應兒子指針指向兒子的獨生子，刪除兒子結點也OK了。
- 有兩個兒子。這是最麻煩的情況，因為你刪除節點之后，還要保證滿足搜索二叉樹的結構。其實也比較容易，我們可以選擇左兒子中的最大元素或者右兒子中的最小元素放到待刪除節點的位置，就可以保證結構的不變。當然，你要記得調整子樹，畢竟又出現了節點刪除。習慣上大家選擇左兒子中的最大元素，其實選擇右兒子的最小元素也一樣，沒有任何差別，只是人們習慣從左向右。這里咱們也選擇左兒子的最大元素，將它放到待刪結點的位置。左兒子的最大元素其實很好找，只要順著左兒子不斷的去搜索右子樹就可以了，直到找到一個沒有右子樹的結點。那就是最大的了。
二叉查找樹的刪除代碼如下所示：
TREE-DELETE(T, z) 1 if left[z] = NIL or right[z] = NIL 2 then y ← z 3 else y ← TREE-SUCCESSOR(z) 4 if left[y] ≠ NIL 5 then x ← left[y] 6 else x ← right[y] 7 if x ≠ NIL 8 then p[x] ← p[y] 9 if p[y] = NIL 10 then root[T] ← x 11 else if y = left[p[y]] 12 then left[p[y]] ← x 13 else right[p[y]] ← x 14 if y ≠ z 15 then key[z] ← key[y] 16 copy y's satellite data into z 17 return y
紅黑樹的刪除和刪除修復
OK，回到紅黑樹上來，紅黑樹結點刪除的算法實現是：
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 ≠ 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
“在刪除節點后，原紅黑樹的性質可能被改變，如果刪除的是紅色節點，那么原紅黑樹的性質依舊保持，此時不用做修正操作，如果刪除的節點是黑色節點，原紅黑樹的性質可能會被改變，我們要對其做修正操作。那么哪些樹的性質會發生變化呢，如果刪除節點不是樹唯一節點，那么刪除節點的那一個支的到各葉節點的黑色節點數會發生變化，此時性質5被破壞。如果被刪節點的唯一非空子節點是紅色，而被刪節點的父節點也是紅色，那么性質4被破壞。如果被刪節點是根節點，而它的唯一非空子節點是紅色，則刪除后新根節點將變成紅色，違背性質2。”
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
“上面的修復情況看起來有些復雜，下面我們用一個分析技巧：我們從被刪節點后來頂替它的那個節點開始調整，并認為它有額外的一重黑色。這里額外一重黑色是什么意思呢，我們不是把紅黑樹的節點加上除紅與黑的另一種顏色，這里只是一種假設，我們認為我們當前指向它，因此空有額外一種黑色，可以認為它的黑色是從它的父節點被刪除后繼承給它的，它現在可以容納兩種顏色，如果它原來是紅色，那么現在是紅+黑，如果原來是黑色，那么它現在的顏色是黑+黑。有了這重額外的黑色，原紅黑樹性質5就能保持不變。現在只要恢復其它性質就可以了，做法還是盡量向根移動和窮舉所有可能性。"--saturnman。
如果是以下情況，恢復比較簡單：
- a)當前節點是紅+黑色
解法，直接把當前節點染成黑色，結束此時紅黑樹性質全部恢復。 - b)當前節點是黑+黑且是根節點， 解法：什么都不做，結束。
但如果是以下情況呢？：
- 刪除修復情況1：當前節點是黑+黑且兄弟節點為紅色(此時父節點和兄弟節點的子節點分為黑)
- 刪除修復情況2：當前節點是黑加黑且兄弟是黑色且兄弟節點的兩個子節點全為黑色
- 刪除修復情況3：當前節點顏色是黑+黑，兄弟節點是黑色，兄弟的左子是紅色，右子是黑色
- 刪除修復情況4：當前節點顏色是黑-黑色，它的兄弟節點是黑色，但是兄弟節點的右子是紅色，兄弟節點左子的顏色任意
此時，我們需要調用RB-DELETE-FIXUP(T, x)，來恢復與保持紅黑性質的工作。
下面，咱們便來分別處理這4種刪除修復情況。
刪除修復情況1：當前節點是黑+黑且兄弟節點為紅色(此時父節點和兄弟節點的子節點分為黑)。
解法：把父節點染成紅色，把兄弟結點染成黑色，之后重新進入算法（我們只討論當前節點是其父節點左孩子時的情況）。此變換后原紅黑樹性質5不變，而把問題轉化為兄弟節點為黑色的情況(注：變化前，原本就未違反性質5，只是為了把問題轉化為兄弟節點為黑色的情況)。 即如下代碼操作：
//調用RB-DELETE-FIXUP(T, x) 的1-8行代碼 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
變化前：
變化后：
刪除修復情況2：當前節點是黑加黑且兄弟是黑色且兄弟節點的兩個子節點全為黑色。
解法：把當前節點和兄弟節點中抽取一重黑色追加到父節點上，把父節點當成新的當前節點，重新進入算法。（此變換后性質5不變），即調用RB-INSERT-FIXUP(T, z) 的第9-10行代碼操作，如下：
//調用RB-DELETE-FIXUP(T, x) 的9-11行代碼 9 if color[left[w]] = BLACK and color[right[w]] = BLACK 10 then color[w] ← RED ? Case 2 11 x p[x] ? Case 2
變化前
變化后
刪除修復情況3：當前節點顏色是黑+黑，兄弟節點是黑色，兄弟的左子是紅色，右子是黑色。
解法：把兄弟結點染紅，兄弟左子節點染黑，之后再在兄弟節點為支點解右旋，之后重新進入算法。此是把當前的情況轉化為情況4，而性質5得以保持，即調用RB-INSERT-FIXUP(T, z) 的第12-16行代碼，如下所示：
//調用RB-DELETE-FIXUP(T, x) 的第12-16行代碼 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
變化前：
變化后：
刪除修復情況4：當前節點顏色是黑-黑色，它的兄弟節點是黑色，但是兄弟節點的右子是紅色，兄弟節點左子的顏色任意。
解法：把兄弟節點染成當前節點父節點的顏色，把當前節點父節點染成黑色，兄弟節點右子染成黑色，之后以當前節點的父節點為支點進行左旋，此時算法結束，紅黑樹所有性質調整正確，即調用RB-INSERT-FIXUP(T, z)的第17-21行代碼，如下所示：
//調用RB-DELETE-FIXUP(T, x) 的第17-21行代碼 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
變化前：
變化后：
最后值得一提的是上述刪除修復的情況1~4都只是樹的局部，并非樹的整體全部，且刪除修復情況3、4在經過上面的調整后，調整還沒結束（還得繼續調整直至重新恢復平衡，只是圖并沒有畫出來）。
后面會繼續修改完善下本文，感謝關注，thanks。
July、二零一四年九月十五日修訂。
----------------
之前在學校寢室畫紅黑樹畫了好幾個鐘頭，貼倆張圖：
紅黑樹插入修復的3種情況：
紅黑樹刪除修復的4種情況：
updated
繼續請看本文的github優化版本：https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md，或看看這個PPT：http://vdisk.weibo.com/s/zrFL6OXJNfNVU。另，對應新書《編程之法：面試和算法心得》3.1節。July、二零一四年五月三日。
來自： http://blog.csdn.net/v_july_v/article/details/6105630