紅-黑樹

紅-黑樹（英語：Red–black tree）是一種自平衡二叉查找樹，是在計算機科學中用到的一種數據結構，典型的用途是實現關聯數組。

基本介紹

• 中文名：紅-黑樹
• 外文名：Red–black tree
• 發明人：魯道夫·貝爾

簡介

紅-黑樹是在1972年由魯道夫·貝爾發明的，他稱之為“對稱二叉B樹”，它現代的名字是在Leo J. Guibas和Robert Sedgewick於1978年寫的一篇論文中獲得的。它是複雜的，但它的操作有著良好的最壞情況運行時間，並且在實踐中是高效的：它可以在 時間內做查找，插入和刪除，這裡的n是樹中元素的數目。

用途和好處

紅黑樹和AVL樹一樣都對插入時間、刪除時間和查找時間提供了最好可能的最壞情況擔保。這不只是使它們在時間敏感的套用如實時套用（real time application）中有價值，而且使它們有在提供最壞情況擔保的其他數據結構中作為建造板塊的價值；例如，在計算幾何中使用的很多數據結構都可以基於紅黑樹。

紅黑樹在函式式編程中也特別有用，在這裡它們是最常用的持久數據結構（persistent data structure）之一，它們用來構造關聯數組和集合，每次插入、刪除之後它們能保持為以前的版本。除了 的時間之外，紅黑樹的持久版本對每次插入或刪除需要 的空間。

紅黑樹是2-3-4樹的一種等同。換句話說，對於每個2-3-4樹，都存在至少一個數據元素是同樣次序的紅黑樹。在2-3-4樹上的插入和刪除操作也等同於在紅黑樹中顏色翻轉和旋轉。這使得2-3-4樹成為理解紅黑樹背後的邏輯的重要工具，這也是很多介紹算法的教科書在紅黑樹之前介紹2-3-4樹的原因，儘管2-3-4樹在實踐中不經常使用。
紅黑樹相對於AVL樹來說，犧牲了部分平衡性以換取插入/刪除操作時少量的旋轉操作，整體來說性能要優於AVL樹。

性質

紅黑樹是每個節點都帶有顏色屬性的二叉查找樹，顏色為紅色或黑色。在二叉查找樹強制一般要求以外，對於任何有效的紅黑樹我們增加了如下的額外要求：

1. 節點是紅色或黑色。
2. 根是黑色。
3. 所有葉子都是黑色（葉子是NIL節點）。
4. 每個紅色節點必須有兩個黑色的子節點。（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點。）
5. 從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點。

下面是一個具體的紅黑樹的圖例：

紅黑樹圖例

這些約束確保了紅黑樹的關鍵特性：從根到葉子的最長的可能路徑不多於最短的可能路徑的兩倍長。結果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同於普通的二叉查找樹。

要知道為什麼這些性質確保了這個結果，注意到性質4導致了路徑不能有兩個毗連的紅色節點就足夠了。最短的可能路徑都是黑色節點，最長的可能路徑有交替的紅色和黑色節點。因為根據性質5所有最長的路徑都有相同數目的黑色節點，這就表明了沒有路徑能多於任何其他路徑的兩倍長。
在很多樹數據結構的表示中，一個節點有可能只有一個子節點，而葉子節點包含數據。用這種範例表示紅黑樹是可能的，但是這會改變一些性質並使算法複雜。為此，本文中我們使用"nil葉子"或"空（null）葉子"，如上圖所示，它不包含數據而只充當樹在此結束的指示。這些節點在繪圖中經常被省略，導致了這些樹好像同上述原則相矛盾，而實際上不是這樣。與此有關的結論是所有節點都有兩個子節點，儘管其中的一個或兩個可能是空葉子。

操作

因為每一個紅黑樹也是一個特化的二叉查找樹，因此紅黑樹上的唯讀操作與普通二叉查找樹上的唯讀操作相同。然而，在紅黑樹上進行插入操作和刪除操作會導致不再匹配紅黑樹的性質。恢復紅黑樹的性質需要少量（ ）的顏色變更（實際是非常快速的）和不超過三次樹旋轉（對於插入操作是兩次）。雖然插入和刪除很複雜，但操作時間仍可以保持為 次。

插入

我們首先以二叉查找樹的方法增加節點並標記它為紅色。（如果設為黑色，就會導致根到葉子的路徑上有一條路上，多一個額外的黑節點，這個是很難調整的。但是設為紅色節點後，可能會導致出現兩個連續紅色節點的衝突，那么可以通過顏色調換（color flips）和樹旋轉來調整。）下面要進行什麼操作取決於其他臨近節點的顏色。同人類的家族樹中一樣，我們將使用術語叔父節點來指一個節點的父節點的兄弟節點。注意：

• 性質1和性質3總是保持著。
• 性質4隻在增加紅色節點、重繪黑色節點為紅色，或做旋轉時受到威脅。
• 性質5隻在增加黑色節點、重繪紅色節點為黑色，或做旋轉時受到威脅。

情形1：新節點N位於樹的根上，沒有父節點。在這種情形下，我們把它重繪為黑色以滿足性質2。因為它在每個路徑上對黑節點數目增加一，性質5匹配。

情形2：新節點的父節點P是黑色，所以性質4沒有失效（新節點是紅色的）。在這種情形下，樹仍是有效的。性質5也未受到威脅，儘管新節點N有兩個黑色葉子子節點；但由於新節點N是紅色，通過它的每個子節點的路徑就都有同通過它所取代的黑色的葉子的路徑同樣數目的黑色節點，所以依然滿足這個性質。

注意：在下列情形下我們假定新節點的父節點為紅色，所以它有祖父節點；因為如果父節點是根節點，那父節點就應當是黑色。所以新節點總有一個叔父節點，儘管在情形4和5下它可能是葉子節點。

情形3：如果父節點P和叔父節點U二者都是紅色，（此時新插入節點N做為P的左子節點或右子節點都屬於情形3，這裡右圖僅顯示N做為P左子的情形）則我們可以將它們兩個重繪為黑色並重繪祖父節點G為紅色（用來保持性質5）。當前我們的新節點N有了一個黑色的父節點P。因為通過父節點P或叔父節點U的任何路徑都必定通過祖父節點G，在這些路徑上的黑節點數目沒有改變。但是，紅色的祖父節點G可能是根節點，這就違反了性質2，也有可能祖父節點G的父節點是紅色的，這就違反了性質4。為了解決這個問題，我們在祖父節點G上遞歸地進行情形1的整個過程。（把G當成是新加入的節點進行各種情形的檢查）

情形3

注意：在餘下的情形下，我們假定父節點P是其父親G的左子節點。如果它是右子節點，情形4和情形5中的左和右應當對調。

情形4：父節點P是紅色而叔父節點U是黑色或缺少，並且新節點N是其父節點P的右子節點而父節點P又是其父節點的左子節點。在這種情形下，我們進行一次左旋轉調換新節點和其父節點的角色;接著，我們按情形5處理以前的父節點P以解決仍然失效的性質4。注意這個改變會導致某些路徑通過它們以前不通過的新節點N（比如圖中1號葉子節點）或不通過節點P（比如圖中3號葉子節點），但由於這兩個節點都是紅色的，所以性質5仍有效。

情形4

情形5：父節點P是紅色而叔父節點U是黑色或缺少，新節點N是其父節點的左子節點，而父節點P又是其父節點G的左子節點。在這種情形下，我們進行針對祖父節點G的一次右旋轉；在旋轉產生的樹中，以前的父節點P出現到是新節點N和以前的祖父節點G的父節點。我們知道以前的祖父節點G是黑色，否則父節點P就不可能是紅色（如果P和G都是紅色就違反了性質4，所以G必須是黑色）。我們切換以前的父節點P和祖父節點G的顏色，結果的樹滿足性質4。性質5也仍然保持滿足，因為通過這三個節點中任何一個的所有路徑以前都通過祖父節點G，出現到它們都通過以前的父節點P。在各自的情形下，這都是三個節點中的黑色節點。

注意插入實際上是原地算法，因為上述所有調用都使用了尾部遞歸。

情形5

刪除

如果需要刪除的節點有兩個兒子，那么問題可以被轉化成刪除另一個只有一個兒子的節點的問題（為了表述方便，這裡所指的兒子，為非葉子節點的兒子）。對於二叉查找樹，在刪除帶有兩個非葉子兒子的節點的時候，我們要么找到它左子樹中的最大元素、要么找到它右子樹中的最小元素，並把它的值轉移到要刪除的節點中（如在這裡所展示的那樣）。我們接著刪除我們從中複製出值的那個節點，它必定有少於兩個非葉子的兒子。因為只是複製了一個值，不違反任何性質，這就把問題簡化為如何刪除最多有一個兒子的節點的問題。它不關心這個節點是最初要刪除的節點還是我們從中複製出值的那個節點。

在本文餘下的部分中，我們只需要討論刪除只有一個兒子的節點（如果它兩個兒子都為空，即均為葉子，我們任意將其中一個看作它的兒子）。如果我們刪除一個紅色節點（此時該節點的兒子將都為葉子節點），它的父親和兒子一定是黑色的。所以我們可以簡單的用它的黑色兒子替換它，並不會破壞性質3和性質4。通過被刪除節點的所有路徑只是少了一個紅色節點，這樣可以繼續保證性質5。另一種簡單情況是在被刪除節點是黑色而它的兒子是紅色的時候。如果只是去除這個黑色節點，用它的紅色兒子頂替上來的話，會破壞性質5，但是如果我們重繪它的兒子為黑色，則曾經通過它的所有路徑將通過它的黑色兒子，這樣可以繼續保持性質5。

需要進一步討論的是在要刪除的節點和它的兒子二者都是黑色的時候，這是一種複雜的情況。我們首先把要刪除的節點替換為它的兒子。出於方便，稱呼這個兒子為N（在新的位置上），稱呼它的兄弟（它父親的另一個兒子）為S。在下面的示意圖中，我們還是使用P稱呼N的父親，S_L稱呼S的左兒子，S_R稱呼S的右兒子。我們將使用下述函式找到兄弟節點：

如果N和它初始的父親是黑色，則刪除它的父親導致通過N的路徑都比不通過它的路徑少了一個黑色節點。因為這違反了性質5，樹需要被重新平衡。有幾種情形需要考慮：

情形1：N是新的根。在這種情形下，我們就做完了。我們從所有路徑去除了一個黑色節點，而新根是黑色的，所以性質都保持著。

注意：在情形2、5和6下，我們假定N是它父親的左兒子。如果它是右兒子，則在這些情形下的左和右應當對調。

情形2：S是紅色。在這種情形下我們在N的父親上做左旋轉，把紅色兄弟轉換成N的祖父，我們接著對調N的父親和祖父的顏色。完成這兩個操作後，儘管所有路徑上黑色節點的數目沒有改變，但當前N有了一個黑色的兄弟和一個紅色的父親（它的新兄弟是黑色因為它是紅色S的一個兒子），所以我們可以接下去按情形4、情形5或情形6來處理。

（注意：這裡的圖中沒有顯示出來，N是刪除了黑色節點後替換上來的子節點，所以這個過程中由P->X->N變成了P->N，實際上是少了一個黑色節點，也可以理解為Parent(Black)和Silbing(Red)那么他們的孩子黑色節點的數目肯定不等，讓他們做新兄弟肯定是不平衡的，還需後面繼續處理。）

刪除-情形2

情形3：N的父親、S和S的兒子都是黑色的。在這種情形下，我們簡單的重繪S為紅色。結果是通過S的所有路徑，它們就是以前不通過N的那些路徑，都少了一個黑色節點。因為刪除N的初始的父親使通過N的所有路徑少了一個黑色節點，這使事情都平衡了起來。但是，通過P的所有路徑當前比不通過P的路徑少了一個黑色節點，所以仍然違反性質5。要修正這個問題，我們要從情形1開始，在P上做重新平衡處理。

刪除-情形3

情形4：S和S的兒子都是黑色，但是N的父親是紅色。在這種情形下，我們簡單的交換N的兄弟和父親的顏色。這不影響不通過N的路徑的黑色節點的數目，但是它在通過N的路徑上對黑色節點數目增加了一，添補了在這些路徑上刪除的黑色節點。

情形5： S是黑色，S的左兒子是紅色，S的右兒子是黑色，而N是它父親的左兒子。在這種情形下我們在S上做右旋轉，這樣S的左兒子成為S的父親和N的新兄弟。我們接著交換S和它的新父親的顏色。所有路徑仍有同樣數目的黑色節點，但是當前N有了一個黑色兄弟，他的右兒子是紅色的，所以我們進入了情形6。N和它的父親都不受這個變換的影響。

刪除-情形4

情形6：S是黑色，S的右兒子是紅色，而N是它父親的左兒子。在這種情形下我們在N的父親上做左旋轉，這樣S成為N的父親（P）和S的右兒子的父親。我們接著交換N的父親和S的顏色，並使S的右兒子為黑色。子樹在它的根上的仍是同樣的顏色，所以性質3沒有被違反。但是，N當前增加了一個黑色祖先：要么N的父親變成黑色，要么它是黑色而S被增加為一個黑色祖父。所以，通過N的路徑都增加了一個黑色節點。

刪除-情形5

此時，如果一個路徑不通過N，則有兩種可能性：

• 它通過N的新兄弟。那么它以前和當前都必定通過S和N的父親，而它們只是交換了顏色。所以路徑保持了同樣數目的黑色節點。
• 它通過N的新叔父，S的右兒子。那么它以前通過S、S的父親和S的右兒子，但是當前只通過S，它被假定為它以前的父親的顏色，和S的右兒子，它被從紅色改變為黑色。合成效果是這個路徑通過了同樣數目的黑色節點。

在任何情況下，在這些路徑上的黑色節點數目都沒有改變。所以我們恢復了性質4。在示意圖中的白色節點可以是紅色或黑色，但是在變換前後都必須指定相同的顏色。

刪除-情形6

同樣的，函式調用都使用了尾部遞歸，所以算法是原地算法。此外，在旋轉之後不再做遞歸調用，所以進行了恆定數目（最多3次）的旋轉。