红黑树

**紅黑樹**（英語：Red–black tree）是一種自平衡二元搜尋樹，是在電腦科學中用到的一種資料結構，典型用途是實現關聯陣列。它在 1972 年由魯道夫・貝爾發明，被稱為「**對稱二元 B 樹**」，它現代的名字源於 Leo J. Guibas 和羅伯特・塞奇威克於 1978 年寫的一篇論文。紅黑樹的結構複雜，但它的操作有著良好的最壞情況執行時間，並且在實踐中高效：它可以在 ${\text{O}}(\log n)$ 時間內完成尋找、插入和刪除，這裡的 $n$ 是樹中元素的數目。

## 歷史

1972 年，魯道夫・拜爾發明了一種資料結構，那是一個 B 樹的四階特殊情況。此結構會維持所有從根到樹葉的路徑都具有相同數量的節點，創造了一個完美的平衡樹。然而，他們並不是二元搜尋樹。拜爾在他的論文中稱呼他們為「**對稱二元 B 樹**」（symmetric binary B-tree），後來他們以 2-3-4 樹或是 2-4 樹的形式開始流行。

在一篇 1972 年的論文〈A Dichromatic Framework for Balanced Trees〉中，Leonidas J. Guibas 和 Robert Sedgewick 從對稱二元 B 樹（symmetric binary B-tree）中推導出了紅黑樹。之所以選擇「紅色」是因為這是作者在帕羅奧多研究中心公司（Xerox PARC）工作時用彩色雷射列印機可以產生的最好看的顏色。另一種說法來自 Guibas，是因為紅色和黑色的筆是他們當時可用來繪製樹的顏色。

## 用途和好處

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

紅黑樹在函數式程式設計中也特別有用，在這裡它們是最常用的持久資料結構（persistent data structure）之一，它們用來構造關聯陣列和集合，每次插入、刪除之後它們能保持為以前的版本。除了 ${\text{O}}(\log n)$ 的時間之外，紅黑樹的持久版本對每次插入或刪除需要 ${\text{O}}(\log n)$ 的空間。

紅黑樹是 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 葉子」，如上圖所示，它不包含資料而只充當樹在此結束的指示。這些節點在繪圖中經常被省略，導致了這些樹好像同上述原則相矛盾，而實際上不是這樣。與此有關的結論是所有節點都有兩個子節點，儘管其中的一個或兩個可能是空葉子。

## 操作

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

### 插入

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

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

在下面的示意圖中，將要插入的節點標為 **N**，N 的父節點標為 **P**，N 的祖父節點標為 **G**，N 的叔父節點標為 **U**。在圖中展示的任何顏色要麼是由它所處情形這些所作的假定，要麼是假定所暗含（imply）的。

對於每一種情形，我們將使用 C 範例程式碼來展示。通過下列函式，可以找到一個節點的叔父和祖父節點：

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

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

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

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

注意插入實際上是原地演算法，因為上述所有呼叫都使用了尾端遞迴。

### 刪除

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

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

**需要進一步討論的是在要刪除的節點和它的兒子二者都是黑色的時候**，這是一種複雜的情況（這種情況下該節點的兩個兒子都是葉子節點，否則若其中一個兒子是黑色非葉子節點，另一個兒子是葉子節點，那麼從該節點通過非葉子節點兒子的路徑上的黑色節點數最小為 2，而從該節點到另一個葉子節點兒子的路徑上的黑色節點數為 1，違反了性質 5）。我們首先把要刪除的節點替換為它的兒子。出於方便，稱呼這個兒子為 **N**（在新的位置上），稱呼它的兄弟（它父親的另一個兒子）為 **S**。在下面的示意圖中，我們還是使用 **P** 稱呼 N 的父親，**SL** 稱呼 S 的左兒子，**SR** 稱呼 S 的右兒子。我們將使用下述函式找到兄弟節點：

我們可以使用下列程式碼進行上述的概要步驟，這裡的函式 `replace_node` 替換 `child` 到 `n` 在樹中的位置。出於方便，在本章節中的程式碼將假定空葉子被用不是 NULL 的實際節點物件來表示（在_插入_章節中的程式碼可以同任何一種表示一起工作）。

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

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

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

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

### C++ 範例程式碼

## 漸近邊界的證明

包含 _n_ 個內部節點的紅黑樹的高度是 ${\text{O}}(\log n)$ 。

**定義**：

 * $h(v)$ 表示以節點 $v$ 為根的子樹的高度。
* $bh(v)$ 表示從 $v$ 到子樹中任何葉子的黑色節點的數目（如果 $v$ 是黑色則不計數它，也叫做黑色高度）。

**引理**：以節點 $v$ 為根的子樹有至少 $2^{bh(v)}-1$ 個內部節點。

引理的證明（通過歸納高度）：

基礎： $h(v)=0$

如果 $v$ 的高度是零則它必定是 NIL，因此 $bh(v)=0$ 。所以：

$$
2^{bh(v)}-1=2^{0}-1=1-1=0
$$

歸納假設： $h(v)=k$ 的 $v$ 有 $2^{bh(v)-1}-1$ 個內部節點暗示了 h ( $v'$ ) = k+1 的 $v'$ 有 $2^{bh(v')}-1$ 個內部節點。

因為 $v'$ 有 h ( $v'$ )> 0 所以它是個內部節點。同樣的它有黑色高度要麼是 bh ( $v'$ ) 要麼是 bh ( $v'$ )-1（依據 $v$ 是紅色還是黑色）的兩個兒子。通過歸納假設每個兒子都有至少 $2^{bh(v')-1}-1$ 個內部接點，所以 $v'$ 有：

$$
2^{bh(v')-1}-1+2^{bh(v')-1}-1+1=2^{bh(v')}-1
$$

個內部節點。

使用這個引理我們現在可以展示出樹的高度是對數性的。因為在從根到葉子的任何路徑上至少有一半的節點是黑色（根據紅黑樹性質 4），根的黑色高度至少是 ${\frac {h(root)}{2}}$ 。通過引理我們得到：

$$
n\geqslant 2^{\frac {h(root)}{2}}-1\leftrightarrow \;\log {(n+1)}\geqslant {\frac {h(root)}{2}}\leftrightarrow \;h(root)\leqslant 2\log {(n+1)}
$$

因此根的高度是 ${\text{O}}(\log n)$ 。

## 參見

* AVL 樹
* B 樹
* dancing tree
* 伸展樹
* 2-3-4 樹
* Treap

## 參照

* Mathworld: Red-Black Tree （頁面存檔備份，存於網際網路檔案館）
* San Diego State University: CS 660: Red-Black tree notes （頁面存檔備份，存於網際網路檔案館）, by Roger Whitney
* Cormen, Leiserson, Rivest, Stein. _Introduction to Algorithms._ Massachusetts: The MIT Press, 2002. pp273-77. ISBN 0-07-013151-1

## 外部連結

* An applet + quick explanation （頁面存檔備份，存於網際網路檔案館）
* Red/Black Tree Demonstration （頁面存檔備份，存於網際網路檔案館）
* An example（animated GIF, 200KB）
* An example（static picture）
* Another explanation（pictures, source code, and Java interactive animation）
* Red-Black Tree Demonstration by David M. Howard
* RBT: A SmallEiffel Red-Black Tree Library （頁面存檔備份，存於網際網路檔案館）
* libredblack: A C Red-Black Tree Library （頁面存檔備份，存於網際網路檔案館）
* Red-Black Tree C++ Code
* Red-Black Trees by Thomas Niemann
* 紅黑樹的介紹和實現