教你初步了解紅黑樹

本文參考：Google、算法導(dǎo)論、STL源碼剖析、計算機程序設(shè)計藝術(shù)。

推薦閱讀：

1. Left-Leaning Red-Black Trees, Dagstuhl Workshop on Data Structures, Wadern, Germany, February, 2008，直接下載：http://www.cs./~rs/talks/LLRB/RedBlack.pdf。
2. 本文的github優(yōu)化版：https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md。

一、紅黑樹的介紹

先來看下算法導(dǎo)論對R-B Tree的介紹：
紅黑樹，一種二叉查找樹，但在每個結(jié)點上增加一個存儲位表示結(jié)點的顏色，可以是Red或Black。
通過對任何一條從根到葉子的路徑上各個結(jié)點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，因而是接近平衡的。

紅黑樹，作為一棵二叉查找樹，滿足二叉查找樹的一般性質(zhì)。下面，來了解下 二叉查找樹的一般性質(zhì)。

二叉查找樹

二叉查找樹，也稱有序二叉樹（ordered binary tree），或已排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質(zhì)的二叉樹：

• 若任意節(jié)點的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；
• 若任意節(jié)點的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；
• 任意節(jié)點的左、右子樹也分別為二叉查找樹。
• 沒有鍵值相等的節(jié)點（no duplicate nodes）。

因為一棵由n個結(jié)點隨機構(gòu)造的二叉查找樹的高度為lgn，所以順理成章，二叉查找樹的一般操作的執(zhí)行時間為O(lgn)。但二叉查找樹若退化成了一棵具有n個結(jié)點的線性鏈后，則這些操作最壞情況運行時間為O(n)。

紅黑樹雖然本質(zhì)上是一棵二叉查找樹，但它在二叉查找樹的基礎(chǔ)上增加了著色和相關(guān)的性質(zhì)使得紅黑樹相對平衡，從而保證了紅黑樹的查找、插入、刪除的時間復(fù)雜度最壞為O(log n)。

但它是如何保證一棵n個結(jié)點的紅黑樹的高度始終保持在logn的呢？這就引出了紅黑樹的5個性質(zhì)：

1. 每個結(jié)點要么是紅的要么是黑的。  
2. 根結(jié)點是黑的。  
3. 每個葉結(jié)點（葉結(jié)點即指樹尾端NIL指針或NULL結(jié)點）都是黑的。  
4. 如果一個結(jié)點是紅的，那么它的兩個兒子都是黑的。  
5.  對于任意結(jié)點而言，其到葉結(jié)點樹尾端NIL指針的每條路徑都包含相同數(shù)目的黑結(jié)點。 

正是紅黑樹的這5條性質(zhì)，使一棵n個結(jié)點的紅黑樹始終保持了logn的高度，從而也就解釋了上面所說的“紅黑樹的查找、插入、刪除的時間復(fù)雜度最壞為O(log n)”這一結(jié)論成立的原因。

（注：上述第3、5點性質(zhì)中所說的NULL結(jié)點，包括wikipedia.算法導(dǎo)論上所認為的葉子結(jié)點即為樹尾端的NIL指針，或者說NULL結(jié)點。然百度百科以及網(wǎng)上一些其它博文直接說的葉結(jié)點，則易引起誤會，因，此葉結(jié)點非子結(jié)點）

如下圖所示，即是一顆紅黑樹(下圖引自wikipedia：http:///hgvH1l)：

此圖忽略了葉子和根部的父結(jié)點。同時，上文中我們所說的 '葉結(jié)點' 或'NULL結(jié)點'，如上圖所示，它不包含數(shù)據(jù)而只充當樹在此結(jié)束的指示，這些節(jié)點在繪圖中經(jīng)常被省略，望看到此文后的讀者朋友注意。 

二、樹的旋轉(zhuǎn)知識

    當在對紅黑樹進行插入和刪除等操作時，對樹做了修改可能會破壞紅黑樹的性質(zhì)。為了繼續(xù)保持紅黑樹的性質(zhì)，可以通過對結(jié)點進行重新著色，以及對樹進行相關(guān)的旋轉(zhuǎn)操作，即通過修改樹中某些結(jié)點的顏色及指針結(jié)構(gòu)，來達到對紅黑樹進行插入或刪除結(jié)點等操作后繼續(xù)保持它的性質(zhì)或平衡的目的。

    樹的旋轉(zhuǎn)分為左旋和右旋，下面借助圖來介紹一下左旋和右旋這兩種操作。

1.左旋

如上圖所示，當在某個結(jié)點pivot上，做左旋操作時，我們假設(shè)它的右孩子y不是NIL[T]，pivot可以為任何不是NIL[T]的左子結(jié)點。左旋以pivot到Y之間的鏈為“支軸”進行，它使Y成為該子樹的新根，而Y的左孩子b則成為pivot的右孩子。

2.右旋

右旋與左旋差不多，再此不做詳細介紹。

樹在經(jīng)過左旋右旋之后，樹的搜索性質(zhì)保持不變，但樹的紅黑性質(zhì)則被破壞了，所以，紅黑樹插入和刪除數(shù)據(jù)后，需要利用旋轉(zhuǎn)與顏色重涂來重新恢復(fù)樹的紅黑性質(zhì)。

    至于有些書如《STL源碼剖析》有對雙旋的描述，其實雙旋只是單旋的兩次應(yīng)用，并無新的內(nèi)容，因此這里就不再介紹了，而且左右旋也是相互對稱的，只要理解其中一種旋轉(zhuǎn)就可以了。

三、紅黑樹的插入

要真正理解紅黑樹的插入，還得先理解二叉查找樹的插入。磨刀不誤砍柴工，咱們再來了解一下二叉查找樹的插入和紅黑樹的插入。

如果要在二叉查找樹中插入一個結(jié)點，首先要查找到結(jié)點要插入的位置，然后進行插入。假設(shè)插入的結(jié)點為z的話，插入的偽代碼如下：

紅黑樹的插入和插入修復(fù)

現(xiàn)在我們了解了二叉查找樹的插入，接下來，咱們便來具體了解下紅黑樹的插入操作。紅黑樹的插入相當于在二叉查找樹插入的基礎(chǔ)上，為了重新恢復(fù)平衡，繼續(xù)做了插入修復(fù)操作。

假設(shè)插入的結(jié)點為z，紅黑樹的插入偽代碼具體如下所示：

把上面這段紅黑樹的插入代碼，跟之前看到的二叉查找樹的插入代碼比較一下可以看出，RB-INSERT(T, z)前面的第1～13行代碼基本上就是二叉查找樹的插入代碼，然后第14～16行代碼把z的左孩子和右孩子都賦為葉結(jié)點nil，再把z結(jié)點著為紅色，最后為保證紅黑性質(zhì)在插入操作后依然保持，調(diào)用一個輔助程序RB-INSERT-FIXUP來對結(jié)點進行重新著色，并旋轉(zhuǎn)。

換言之，如果插入的是根結(jié)點，由于原樹是空樹，此情況只會違反性質(zhì)2，因此直接把此結(jié)點涂為黑色；如果插入的結(jié)點的父結(jié)點是黑色，由于此不會違反性質(zhì)2和性質(zhì)4，紅黑樹沒有被破壞，所以此時什么也不做。

但當遇到下述3種情況時又該如何調(diào)整呢？

• ● 插入修復(fù)情況1：如果當前結(jié)點的父結(jié)點是紅色且祖父結(jié)點的另一個子結(jié)點（叔叔結(jié)點）是紅色

  ● 插入修復(fù)情況2：當前節(jié)點的父節(jié)點是紅色,叔叔節(jié)點是黑色，當前節(jié)點是其父節(jié)點的右子

  ● 插入修復(fù)情況3：當前節(jié)點的父節(jié)點是紅色,叔叔節(jié)點是黑色，當前節(jié)點是其父節(jié)點的左子

下面，咱們來分別處理上述3種插入修復(fù)情況。

• 插入修復(fù)情況1：當前結(jié)點的父結(jié)點是紅色，祖父結(jié)點的另一個子結(jié)點（叔叔結(jié)點）是紅色。

如下代碼所示：

此時父結(jié)點的父結(jié)點一定存在，否則插入前就已不是紅黑樹。與此同時，又分為父結(jié)點是祖父結(jié)點的左孩子還是右孩子，根據(jù)對稱性，我們只要解開一個方向就可以了。這里只考慮父結(jié)點為祖父左孩子的情況，如下圖所示。

對此，我們的解決策略是：將當前節(jié)點的父節(jié)點和叔叔節(jié)點涂黑，祖父結(jié)點涂紅，把當前結(jié)點指向祖父節(jié)點，從新的當前節(jié)點重新開始算法。即如下代碼所示：

所以，變化后如下圖所示：

于是，插入修復(fù)情況1轉(zhuǎn)換成了插入修復(fù)情況2。

• 插入修復(fù)情況2：當前節(jié)點的父節(jié)點是紅色,叔叔節(jié)點是黑色，當前節(jié)點是其父節(jié)點的右子

此時，解決對策是：當前節(jié)點的父節(jié)點做為新的當前節(jié)點，以新當前節(jié)點為支點左旋。即如下代碼所示：

變化成：

從而插入修復(fù)情況2轉(zhuǎn)換成了插入修復(fù)情況3。

• 插入修復(fù)情況3：當前節(jié)點的父節(jié)點是紅色,叔叔節(jié)點是黑色，當前節(jié)點是其父節(jié)點的左孩子

解決對策是：父節(jié)點變?yōu)楹谏?，祖父?jié)點變?yōu)榧t色，在祖父節(jié)點為支點右旋，操作代碼為：

最后，把根結(jié)點涂為黑色，整棵紅黑樹便重新恢復(fù)了平衡。所以紅黑樹由之前的：

變化成：

「回顧：經(jīng)過上面情況3、情況4、情況5等3種插入修復(fù)情況的操作示意圖，讀者自會發(fā)現(xiàn)，后面的情況4、情況5都是針對情況3插入節(jié)點4以后，進行的一系列插入修復(fù)情況操作，不過，指向當前節(jié)點N指針一直在變化。所以，你可以想當然的認為：整個下來，情況3、4、5就是一個完整的插入修復(fù)情況的操作流程」

接下來，咱們最后來了解，紅黑樹的刪除操作。

'我們刪除的節(jié)點的方法與常規(guī)二叉搜索樹中刪除節(jié)點的方法是一樣的，如果被刪除的節(jié)點不是有雙非空子女，則直接刪除這個節(jié)點，用它的唯一子節(jié)點頂替它的位置，如果它的子節(jié)點分是空節(jié)點，那就用空節(jié)點頂替它的位置，如果它的雙子全為非空，我們就把它的直接后繼節(jié)點內(nèi)容復(fù)制到它的位置，之后以同樣的方式刪除它的后繼節(jié)點，它的后繼節(jié)點不可能是雙子非空，因此此傳遞過程最多只進行一次?！?/p>

二叉查找樹的刪除

繼續(xù)講解之前，補充說明下二叉樹結(jié)點刪除的幾種情況，待刪除的節(jié)點按照兒子的個數(shù)可以分為三種：

1. 沒有兒子，即為葉結(jié)點。直接把父結(jié)點的對應(yīng)兒子指針設(shè)為NULL，刪除兒子結(jié)點就OK了。
2. 只有一個兒子。那么把父結(jié)點的相應(yīng)兒子指針指向兒子的獨生子，刪除兒子結(jié)點也OK了。
3. 有兩個兒子。這是最麻煩的情況，因為你刪除節(jié)點之后，還要保證滿足搜索二叉樹的結(jié)構(gòu)。其實也比較容易，我們可以選擇左兒子中的最大元素或者右兒子中的最小元素放到待刪除節(jié)點的位置，就可以保證結(jié)構(gòu)的不變。當然，你要記得調(diào)整子樹，畢竟又出現(xiàn)了節(jié)點刪除。習慣上大家選擇左兒子中的最大元素，其實選擇右兒子的最小元素也一樣，沒有任何差別，只是人們習慣從左向右。這里咱們也選擇左兒子的最大元素，將它放到待刪結(jié)點的位置。左兒子的最大元素其實很好找，只要順著左兒子不斷的去搜索右子樹就可以了，直到找到一個沒有右子樹的結(jié)點。那就是最大的了。

二叉查找樹的刪除代碼如下所示：

紅黑樹的刪除和刪除修復(fù)

OK，回到紅黑樹上來，紅黑樹結(jié)點刪除的算法實現(xiàn)是：

RB-DELETE(T, z) 單純刪除結(jié)點的總操作

“在刪除節(jié)點后，原紅黑樹的性質(zhì)可能被改變，如果刪除的是紅色節(jié)點，那么原紅黑樹的性質(zhì)依舊保持，此時不用做修正操作，如果刪除的節(jié)點是黑色節(jié)點，原紅黑樹的性質(zhì)可能會被改變，我們要對其做修正操作。那么哪些樹的性質(zhì)會發(fā)生變化呢，如果刪除節(jié)點不是樹唯一節(jié)點，那么刪除節(jié)點的那一個支的到各葉節(jié)點的黑色節(jié)點數(shù)會發(fā)生變化，此時性質(zhì)5被破壞。如果被刪節(jié)點的唯一非空子節(jié)點是紅色，而被刪節(jié)點的父節(jié)點也是紅色，那么性質(zhì)4被破壞。如果被刪節(jié)點是根節(jié)點，而它的唯一非空子節(jié)點是紅色，則刪除后新根節(jié)點將變成紅色，違背性質(zhì)2?！?/p>

RB-DELETE-FIXUP(T, x) 恢復(fù)與保持紅黑性質(zhì)的工作

“上面的修復(fù)情況看起來有些復(fù)雜，下面我們用一個分析技巧：我們從被刪節(jié)點后來頂替它的那個節(jié)點開始調(diào)整，并認為它有額外的一重黑色。這里額外一重黑色是什么意思呢，我們不是把紅黑樹的節(jié)點加上除紅與黑的另一種顏色，這里只是一種假設(shè)，我們認為我們當前指向它，因此空有額外一種黑色，可以認為它的黑色是從它的父節(jié)點被刪除后繼承給它的，它現(xiàn)在可以容納兩種顏色，如果它原來是紅色，那么現(xiàn)在是紅 黑，如果原來是黑色，那么它現(xiàn)在的顏色是黑 黑。有了這重額外的黑色，原紅黑樹性質(zhì)5就能保持不變?，F(xiàn)在只要恢復(fù)其它性質(zhì)就可以了，做法還是盡量向根移動和窮舉所有可能性。'--saturnman。

如果是以下情況，恢復(fù)比較簡單：

• a)當前節(jié)點是紅 黑色
  解法，直接把當前節(jié)點染成黑色，結(jié)束此時紅黑樹性質(zhì)全部恢復(fù)。
  
• b)當前節(jié)點是黑 黑且是根節(jié)點， 解法：什么都不做，結(jié)束。

但如果是以下情況呢？：

• 刪除修復(fù)情況1：當前節(jié)點是黑 黑且兄弟節(jié)點為紅色(此時父節(jié)點和兄弟節(jié)點的子節(jié)點分為黑)
• 刪除修復(fù)情況2：當前節(jié)點是黑加黑且兄弟是黑色且兄弟節(jié)點的兩個子節(jié)點全為黑色
• 刪除修復(fù)情況3：當前節(jié)點顏色是黑 黑，兄弟節(jié)點是黑色，兄弟的左子是紅色，右子是黑色
• 刪除修復(fù)情況4：當前節(jié)點顏色是黑-黑色，它的兄弟節(jié)點是黑色，但是兄弟節(jié)點的右子是紅色，兄弟節(jié)點左子的顏色任意

此時，我們需要調(diào)用RB-DELETE-FIXUP(T, x)，來恢復(fù)與保持紅黑性質(zhì)的工作。

下面，咱們便來分別處理這4種刪除修復(fù)情況。

刪除修復(fù)情況1：當前節(jié)點是黑 黑且兄弟節(jié)點為紅色(此時父節(jié)點和兄弟節(jié)點的子節(jié)點分為黑)。

解法：把父節(jié)點染成紅色，把兄弟結(jié)點染成黑色，之后重新進入算法（我們只討論當前節(jié)點是其父節(jié)點左孩子時的情況）。此變換后原紅黑樹性質(zhì)5不變，而把問題轉(zhuǎn)化為兄弟節(jié)點為黑色的情況(注：變化前，原本就未違反性質(zhì)5，只是為了把問題轉(zhuǎn)化為兄弟節(jié)點為黑色的情況)。 即如下代碼操作：

變化前：

變化后： 

刪除修復(fù)情況2：當前節(jié)點是黑加黑且兄弟是黑色且兄弟節(jié)點的兩個子節(jié)點全為黑色。

解法：把當前節(jié)點和兄弟節(jié)點中抽取一重黑色追加到父節(jié)點上，把父節(jié)點當成新的當前節(jié)點，重新進入算法。（此變換后性質(zhì)5不變），即調(diào)用RB-INSERT-FIXUP(T, z) 的第9-10行代碼操作，如下：

變化前

變化后

刪除修復(fù)情況3：當前節(jié)點顏色是黑 黑，兄弟節(jié)點是黑色，兄弟的左子是紅色，右子是黑色。

解法：把兄弟結(jié)點染紅，兄弟左子節(jié)點染黑，之后再在兄弟節(jié)點為支點解右旋，之后重新進入算法。此是把當前的情況轉(zhuǎn)化為情況4，而性質(zhì)5得以保持，即調(diào)用RB-INSERT-FIXUP(T, z) 的第12-16行代碼，如下所示：

變化前：

變化后：

刪除修復(fù)情況4：當前節(jié)點顏色是黑-黑色，它的兄弟節(jié)點是黑色，但是兄弟節(jié)點的右子是紅色，兄弟節(jié)點左子的顏色任意。

解法：把兄弟節(jié)點染成當前節(jié)點父節(jié)點的顏色，把當前節(jié)點父節(jié)點染成黑色，兄弟節(jié)點右子染成黑色，之后以當前節(jié)點的父節(jié)點為支點進行左旋，此時算法結(jié)束，紅黑樹所有性質(zhì)調(diào)整正確，即調(diào)用RB-INSERT-FIXUP(T, z)的第17-21行代碼，如下所示：

變化前：

變化后：

最后值得一提的是上述刪除修復(fù)的情況1~4都只是樹的局部，并非樹的整體全部，且刪除修復(fù)情況3、4在經(jīng)過上面的調(diào)整后，調(diào)整還沒結(jié)束（還得繼續(xù)調(diào)整直至重新恢復(fù)平衡，只是圖并沒有畫出來）。
后面會繼續(xù)修改完善下本文，感謝關(guān)注，thanks。

July、二零一四年九月十五日修訂。

----------------

之前在學校寢室畫紅黑樹畫了好幾個鐘頭，貼倆張圖：

  紅黑樹插入修復(fù)的3種情況：

  紅黑樹刪除修復(fù)的4種情況：

updated

繼續(xù)請看本文的github優(yōu)化版本：https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md，或看看這個PPT：http://vdisk.weibo.com/s/zrFL6OXJNfNVU。另，對應(yīng)新書《編程之法：面試和算法心得》3.1節(jié)。July、二零一四年五月三日。