教你初步了解紅黑樹

本文參考：Google、算法導(dǎo)論、STL源碼剖析、計(jì)算機(jī)程序設(shè)計(jì)藝術(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。

一、紅黑樹的介紹

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

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

二叉查找樹

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

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

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

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

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

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

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

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

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

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

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

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

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

1.左旋

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

2.右旋

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

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

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

三、紅黑樹的插入

要真正理解紅黑樹的插入，還得先理解二叉查找樹的插入。磨刀不誤砍柴工，咱們?cè)賮?lái)了解一下二叉查找樹的插入和紅黑樹的插入。

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

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

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

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

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

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

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

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

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

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

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

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

如下代碼所示：

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

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

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

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

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

此時(shí)，解決對(duì)策是：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)做為新的當(dāng)前節(jié)點(diǎn)，以新當(dāng)前節(jié)點(diǎn)為支點(diǎn)左旋。即如下代碼所示：

變化成：

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

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

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

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

變化成：

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

接下來(lái)，咱們最后來(lái)了解，紅黑樹的刪除操作。

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

二叉查找樹的刪除

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

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

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

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

OK，回到紅黑樹上來(lái)，紅黑樹結(jié)點(diǎn)刪除的算法實(shí)現(xiàn)是：

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

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

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

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

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

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

但如果是以下情況呢？：

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

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

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

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

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

變化前：

變化后： 

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

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

變化前

變化后

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

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

變化前：

變化后：

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

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

變化前：

變化后：

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

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

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

之前在學(xué)校寢室畫紅黑樹畫了好幾個(gè)鐘頭，貼倆張圖：

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

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

updated

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