1.簡介

紅黑樹是一種自平衡二叉查找樹。它的統(tǒng)計(jì)性能要好于平衡二叉樹（AVL樹），因此，紅黑樹在很多地方都有應(yīng)用。在C++ STL中，很多部分(目前包括set, multiset, map, multimap)應(yīng)用了紅黑樹的變體(SGI STL中的紅黑樹有一些變化，這些修改提供了更好的性能，以及對set操作的支持)。它是復(fù)雜的，但它的操作有著良好的最壞情況運(yùn)行時(shí)間，并且在實(shí)踐中是高效的: 它可以在O(log n)時(shí)間內(nèi)做查找，插入和刪除等操作。

本文介紹了紅黑樹的基本性質(zhì)和基本操作。

2.紅黑樹的性質(zhì)

紅黑樹，顧名思義，通過紅黑兩種顏色域保證樹的高度近似平衡。它的每個(gè)節(jié)點(diǎn)是一個(gè)五元組：color（顏色），key（數(shù)據(jù)），left（左孩子），right（右孩子）和p（父節(jié)點(diǎn)）。

紅黑樹的定義也是它的性質(zhì)，有以下五條：

性質(zhì)1. 節(jié)點(diǎn)是紅色或黑色

性質(zhì)2. 根是黑色

性質(zhì)3. 所有葉子都是黑色（葉子是NIL節(jié)點(diǎn)）

性質(zhì)4. 如果一個(gè)節(jié)點(diǎn)是紅的，則它的兩個(gè)兒子都是黑的

性質(zhì)5. 從任一節(jié)點(diǎn)到其葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

這五個(gè)性質(zhì)強(qiáng)制了紅黑樹的關(guān)鍵性質(zhì): 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。為什么呢？性質(zhì)4暗示著任何一個(gè)簡單路徑上不能有兩個(gè)毗連的紅色節(jié)點(diǎn)，這樣，最短的可能路徑全是黑色節(jié)點(diǎn)，最長的可能路徑有交替的紅色和黑色節(jié)點(diǎn)。同時(shí)根據(jù)性質(zhì)5知道：所有最長的路徑都有相同數(shù)目的黑色節(jié)點(diǎn)，這就表明了沒有路徑能多于任何其他路徑的兩倍長。

3.紅黑樹的基本操作

因?yàn)榧t黑樹也是二叉查找樹，因此紅黑樹上的查找操作與普通二叉查找樹上的查找操作相同。然而，紅黑樹上的插入操作和刪除操作會導(dǎo)致不再符合紅黑樹的性質(zhì)?；謴?fù)紅黑樹的性質(zhì)需要少量(O(log n))的顏色變更(實(shí)際是非?？焖俚?和不超過三次樹旋轉(zhuǎn)(對于插入操作是兩次)。雖然插入和刪除很復(fù)雜，但操作時(shí)間仍可以保持為 O(log n) 次。

3.1插入操作

插入操作可以概括為以下幾個(gè)步驟：

(1)查找要插入的位置，時(shí)間復(fù)雜度為：O(N)

(2)將新節(jié)點(diǎn)的color賦為紅色

(3)自下而上重新調(diào)整該樹為紅黑樹

其中，第(1)步的查找方法跟普通二叉查找樹一樣，第(2)步之所以將新插入的節(jié)點(diǎn)的顏色賦為紅色，是因?yàn)椋喝绻O(shè)為黑色，就會導(dǎo)致根到葉子的路徑上有一條路上，多一個(gè)額外的黑節(jié)點(diǎn)，這個(gè)是很難調(diào)整的。但是設(shè)為紅色節(jié)點(diǎn)后，可能會導(dǎo)致出現(xiàn)兩個(gè)連續(xù)紅色節(jié)點(diǎn)的沖突，那么可以通過顏色調(diào)換（color flips）和樹旋轉(zhuǎn)來調(diào)整，這樣簡單多了。下面討論步驟(3)的一些細(xì)節(jié)：

設(shè)要插入的節(jié)點(diǎn)為N，其父節(jié)點(diǎn)為P，其父親G的兄弟節(jié)點(diǎn)為U（即P和U是同一個(gè)節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)）。

[1] 如果P是黑色的，則整棵樹不必調(diào)整便是紅黑樹。

[2] 如果P是紅色的（可知，其父節(jié)點(diǎn)G一定是黑色的），則插入z后，違背了性質(zhì)4，需要進(jìn)行調(diào)整。調(diào)整時(shí)分以下3種情況：

（a）N的叔叔U是紅色的

如上圖所示，我們將P和U重繪為黑色并重繪節(jié)點(diǎn)G為紅色(用來保持性質(zhì)5)。現(xiàn)在新節(jié)點(diǎn)N有了一個(gè)黑色的父節(jié)點(diǎn)P，因?yàn)橥ㄟ^父節(jié)點(diǎn)P或叔父節(jié)點(diǎn)U的任何路徑都必定通過祖父節(jié)點(diǎn)G，在這些路徑上的黑節(jié)點(diǎn)數(shù)目沒有改變。但是，紅色的祖父節(jié)點(diǎn)G的父節(jié)點(diǎn)也有可能是紅色的，這就違反了性質(zhì)4。為了解決這個(gè)問題，我們在祖父節(jié)點(diǎn)G上遞歸調(diào)整顏色。

（b）N的叔叔U是黑色的，且N是右孩子

如上圖所示，我們對P進(jìn)行一次左旋轉(zhuǎn)調(diào)換新節(jié)點(diǎn)和其父節(jié)點(diǎn)的角色; 接著，按情形(c)處理以前的父節(jié)點(diǎn)P以解決仍然失效的性質(zhì)4。

（c）N的叔叔U是黑色的，且N是左孩子

如上圖所示，對祖父節(jié)點(diǎn)G 的一次右旋轉(zhuǎn); 在旋轉(zhuǎn)產(chǎn)生的樹中，以前的父節(jié)點(diǎn)P現(xiàn)在是新節(jié)點(diǎn)N和以前的祖父節(jié)點(diǎn)G 的父節(jié)點(diǎn)， 然后交換以前的父節(jié)點(diǎn)P和祖父節(jié)點(diǎn)G的顏色，結(jié)果的樹滿足性質(zhì)4，同時(shí)性質(zhì)5[4]也仍然保持滿足。

3.2刪除操作

刪除操作可以概括為以下幾個(gè)步驟：

(1)查找要?jiǎng)h除位置，時(shí)間復(fù)雜度為：O(N)

(2)用刪除節(jié)點(diǎn)后繼或者節(jié)點(diǎn)替換該節(jié)點(diǎn)（只進(jìn)行數(shù)據(jù)替換即可，不必調(diào)整指針，后繼節(jié)點(diǎn)是中序遍歷中緊挨著該節(jié)點(diǎn)的節(jié)點(diǎn)，即：右孩子的最左孩子節(jié)點(diǎn)）

(3)如果刪除節(jié)點(diǎn)的替換節(jié)點(diǎn)為黑色，則需重新調(diào)整該樹為紅黑樹

其中，第(1)步的查找方法跟普通二叉查找樹一樣，第(2)步之所以用后繼節(jié)點(diǎn)替換刪除節(jié)點(diǎn)，是因?yàn)檫@樣可以保證該后繼節(jié)點(diǎn)之上仍是一個(gè)紅黑樹，而后繼節(jié)點(diǎn)可能是一個(gè)葉節(jié)點(diǎn)或者只有右子樹的節(jié)點(diǎn)，這樣只需用有節(jié)點(diǎn)替換后繼節(jié)點(diǎn)即可達(dá)到刪除的目的。如果需要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)兒子，那么問題可以被轉(zhuǎn)化成刪除另一個(gè)只有一個(gè)兒子的節(jié)點(diǎn)的問題。（沒看懂？？？可參考：http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91 ）在第(3)步中，如果，如果刪除節(jié)點(diǎn)為紅色節(jié)點(diǎn)，則他的父親和孩子全為黑節(jié)點(diǎn)，這樣直接刪除該節(jié)點(diǎn)即可，不必進(jìn)行任何調(diào)整。如果刪除節(jié)點(diǎn)是黑節(jié)點(diǎn)，分四種情況：

設(shè)要?jiǎng)h除的節(jié)點(diǎn)為N，其父節(jié)點(diǎn)為P，其兄弟節(jié)點(diǎn)為S。

由于N是黑色的，則P可能是黑色的，也可能是紅色的，S也可能是黑色的或者紅色的

（1）S是紅色的

此時(shí)P肯定是紅色的。我們對N的父節(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn)，然后把紅色兄弟轉(zhuǎn)換成N的祖父。我們接著對調(diào) N 的父親和祖父的顏色。盡管所有的路徑仍然有相同數(shù)目的黑色節(jié)點(diǎn)，現(xiàn)在 N 有了一個(gè)黑色的兄弟和一個(gè)紅色的父親，所以我們可以接下去按 (2)、(3)或(4)情況來處理。

（2）S和S的孩子全是黑色的

在這種情況下，P可能是黑色的或者紅色的，我們簡單的重繪S 為紅色。結(jié)果是通過S的所有路徑，它們就是以前不通過 N 的那些路徑，都少了一個(gè)黑色節(jié)點(diǎn)。因?yàn)閯h除 N 的初始的父親使通過 N 的所有路徑少了一個(gè)黑色節(jié)點(diǎn)，這使事情都平衡了起來。但是，通過 P 的所有路徑現(xiàn)在比不通過 P 的路徑少了一個(gè)黑色節(jié)點(diǎn)。接下來，要調(diào)整以P作為N遞歸調(diào)整樹。

（3）S是黑色的，S的左孩子是紅色，右孩子是黑色

這種情況下我們在 S 上做右旋轉(zhuǎn)，這樣 S 的左兒子成為 S 的父親和 N 的新兄弟。我們接著交換 S 和它的新父親的顏色。所有路徑仍有同樣數(shù)目的黑色節(jié)點(diǎn)，但是現(xiàn)在 N 有了一個(gè)右兒子是紅色的黑色兄弟，所以我們進(jìn)入了情況（4）。N 和它的父親都不受這個(gè)變換的影響。

（4）S是黑色的，S的右孩子是紅色

在這種情況下我們在 N 的父親上做左旋轉(zhuǎn)，這樣 S 成為 N 的父親和 S 的右兒子的父親。我們接著交換 N 的父親和 S 的顏色，并使 S 的右兒子為黑色。子樹在它的根上的仍是同樣的顏色，所以屬性 3 沒有被違反。但是，N 現(xiàn)在增加了一個(gè)黑色祖先: 要么 N 的父親變成黑色，要么它是黑色而 S 被增加為一個(gè)黑色祖父。所以，通過 N 的路徑都增加了一個(gè)黑色節(jié)點(diǎn)。

4.參考資料

(1)《算法導(dǎo)論》，第二版

(2) http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91