我畫了 20 張圖，給女朋友講清楚紅黑樹

2019 年 12 月 31 日
筆記

作者：CJW

紅黑樹是一種常見的自平衡二叉查找樹，常用於關聯數組、字典，在各種語言的底層實現中被廣泛應用，Java的TreeMap和TreeSet就是基於紅黑樹實現的。本篇分享將為讀者講解紅黑樹的定義、創建和用途。

一.紅黑樹的定義

每個節點或者是黑色，或者是紅色。
根節點是黑色。
每個葉子節點是黑色。
如果一個節點是紅色的，則它的子節點必須是黑色的
從任意一個節點到葉子節點，經過的黑色節點是一樣的。

這段關於 紅黑樹 的描述來源於《演算法導論》，你看完這段話可能一臉懵逼。本文希望能夠由淺入深地、漸進式地引導讀者了解紅黑樹，因此我們會先從紅黑樹的意義說起，為什麼我們需要一棵紅黑樹。

二. 平衡二叉查找樹

我們以這樣一個數組為例 [42，37，18，12，11，6，5] 構建一棵二叉搜索樹，由於數組中任意一點都可以作為二叉搜索樹的根節點，因此這棵二叉搜索樹並不唯一，我們來看一個極端的例子（以42作為根節點，順序插入元素）

在這個例子中，二叉搜索樹退化成了鏈表，搜索的時間複雜度為 O(n)，失去了作為一棵二叉搜索樹的意義。

為了讓二叉搜索樹不至於太「傾斜」，我們需要構建一棵平衡二叉搜索樹。

可以看出，平衡二叉搜索樹的搜索時間複雜度為O(logn)，避免了因為隨機選取根節點構建二叉搜索樹而可能造成的退化成鏈表的情況。下面再抄一段平衡二叉搜索樹的官方定義：

平衡二叉查找樹：簡稱平衡二叉樹。是由前蘇聯的數學家 Adelse-Velskil和 Landis 在 1962 年提出的高度平衡的二叉樹，根據科學家的英文名也稱為 AVL 樹。它具有如下幾個性質：性質1. 可以是空樹。性質2 假如不是空樹，任何一個結點的左子樹與右子樹都是平衡二叉樹，並且高度之差的絕對值不超過 1

（如果讀者還不清楚平衡二叉搜索樹的概念，可以先查閱前文動畫：什麼是平衡二叉樹，本文不再詳細介紹平衡二叉搜索樹）

三. 2-3樹

經過上面的例子，我們可以知道，構建一棵平衡的二叉搜索樹的關鍵在於選取「正確」的根節點，那麼我們如何在每次構建平衡二叉搜索樹時都能選取合適的根節點呢，這裡就要用到另一種重要的樹：2-3樹（讀作二三樹），2-3樹和紅黑樹是等價的，理解2-3樹對理解紅黑樹以及B類樹都有很大的幫助。

2-3樹的基本概念

所謂2-3樹，即滿足二叉搜索樹的性質，且節點可以存放一個元素或者兩個元素，每個節點有兩個或三個孩子的樹。

性質1：滿足二叉搜索樹的性質
性質2：節點可以存放一個或兩個元素
性質3：每個節點有兩個或三個子節點

2-3樹本質上也是一棵搜索樹，和二叉搜索樹的區別在於，2-3的節點可能存放 2 個元素，而且每個節點可能擁有 3 個子節點。2-3樹存在以下兩種節點：2-節點（存在兩個子節點）和3-節點（存在3個子節點）

2-3樹的創建

下面我們來看如何創建一棵2-3樹，創建2-3樹的規則如下：

規則1. 加入新節點時，不會往空的位置添加節點，而是添加到最後一個葉子節點上規則2. 四節點可以被分解三個2-節點組成的樹，並且分解後新樹的根節點需要向上和父節點融合

我們依然使用上面的示例數組[42，37，18，12，11，6，5]，依然使用順序插入的方式來構建2-3樹，看看是否會出現退化成鏈表的情況。

我們可以注意到，在創建2-3樹的每一步中，整棵樹始終保持平衡。

既然2-3樹已經能夠保持自平衡，為什麼我們還需要一棵紅黑樹呢，這是因為 2-3樹這種每個節點儲存1~2個元素以及拆分節點向上融合的性質不便於程式碼操作，因此我們希望通過一些規則，將2-3樹轉換成二叉樹，且轉換後的二叉樹依然能保持平衡性。

2-3樹和紅黑樹的等價性

本小節我們以一棵2-3樹為例，將其從2-3樹轉換成為一棵紅黑樹，從而學習了解2-3樹和紅黑樹的轉換規則，並體會2-3樹和紅黑樹之間的等價性。

對於2-3樹中的2-節點來說，本身就和二叉搜索樹的節點無異，可以直接轉換為紅黑樹的一個黑節點，但是對於3-節點來說，我們需要進行一點小轉換：

將3-節點拆開，成為一棵樹，並且3-節點的左元素作為右元素的子樹
將原來的左元素標記為紅色（表示紅色節點與其父節點在2-3樹中曾是平級的關係）

我們來轉換一棵複雜點的2-3樹，根據上邊的兩條轉換規則，我們將2-節點直接轉換為黑色節點，將3-節點拆成一棵子樹，並給左元素標上紅色，這個過程應該不難理解，另外我們可以注意到，由於紅色節點是由3-節點拆分而來，因此所有的紅色節點都只會出現在左子樹上。

四. 紅黑樹的性質和複雜度分析

紅黑樹基本性質分析

在完成了2-3樹到紅黑樹的轉換之後，我們重新審視紅黑樹的五條性質：

(1) 每個節點或者是黑色，或者是紅色

這是紅黑樹的定義，沒什麼好說的。

(2) 根節點是黑色

根節點要麼對應2-3樹的2-節點或者3-節點，而這兩者的根節點都是黑色的，因而根節點必然是黑色。從上圖2-3樹節點和紅黑樹節點對應關係就能很容易看出來

(3) 每個葉子節點是黑色

注意，這裡的葉子是指的為空的葉子節點，上圖的紅黑樹的完整形式應該是這樣的：

(4) 如果一個節點是紅色的，則它的子節點必須是黑色的

由於紅黑樹的每個節點都由2-3樹轉換而來，紅色節點連接的節點必然是一個2-節點或者3-節點，而無論是2-節點還是3-節點，其根節點都是黑色的，因此紅色節點的子節點必然是黑色的

(5) 從任意一個節點到葉子節點，經過的黑色節點是一樣多的

這是紅黑樹最重要的一條性質，也是紅黑樹的價值所在。由於紅黑樹是由2-3樹轉換而來，因此每一個黑色節點必然對應2-3樹的某個2-節點或者3-節點，因此紅黑樹的黑節點也能擁有2-3樹的平衡性。如果對這條性質還不夠理解，可以對著上文2-3樹和紅黑樹的轉換圖再理解理解。

紅黑樹時間複雜度分析

網上有很多使用數學歸納法來計算紅黑樹時間複雜度的證明了，這裡就不再贅述。我們可以簡單思考一下，對於一棵普通的平衡二叉搜索樹來說，它的搜索時間複雜度為O(logn)，而作為紅黑樹，存在著最壞的情況，也就是查找的過程中，經過的節點全都是原來2-3樹里的3-節點，導致路徑延長兩倍，時間複雜度為O(2logn)，由於時間複雜度的計算可以忽略係數，因此紅黑樹的搜索時間複雜度依然是O(logn)，當然，由於這個係數的存在，在實際使用中，紅黑樹會比普通的平衡二叉樹（AVL樹）搜索效率要低一些。

既然紅黑樹的效率比AVL樹的效率低，那麼紅黑樹的優勢體現在哪呢？事實上，紅黑樹的優勢體現在它的插入和刪除操作上，紅黑樹的插入和刪除相較於AVL樹的性能會高一些，在後續紅黑樹的創建章節中，讀者應該能夠體會到紅黑樹在調整樹平衡操作上的優勢。

五. 紅黑樹的創建

上文中我們講解了如何由2-3樹轉換一棵紅黑樹，下面我們就來看看如何不經過2-3樹直接創建一棵紅黑樹，畢竟我們寫程式碼的時候不能先創建一棵2-3樹再轉化成紅黑樹吧。我們回想一下2-3樹的創建規則：

簡單來說，2-3樹的創建分為「融合」和「拆分」兩步，為了實現這兩步，我們需要在創建二叉樹的基礎操作上增加另外幾個操作，分別是：

保持根節點黑色
左旋轉
右旋轉
顏色翻轉

保持根節點黑色和左旋轉

由於我們往2-3樹插入節點時做的都是融合，因此新加入的節點和原位置的節點是平級關係，所以我們往紅黑樹里增加節點的時候，增加的都是紅色節點。

我們插入第一個紅色節點42，哦吼，第一步就與紅黑樹的性質2「根節點是黑色」衝突，為了解決這種衝突，我們將根節點變成黑色。

下面我們繼續插入節點37，同樣的，新插入的節點都為紅色

這裡我們要思考一下，如果我們顛倒順序，先插入 37 再插入 42 呢，是直接把 42 加到 37 的右子樹上么，這顯然是錯誤的，因為在前邊2-3樹轉紅黑樹的過程中，我們已經了解到，所有的紅色節點都只會出現在左子樹上，因此我們需要進行左旋轉，將節點的位置和顏色旋轉過來。

上面是兩個獨立的節點，如果節點擁有左右子樹，在旋轉後仍然能滿足二叉搜索樹的性質嗎，我們需要推廣到一般情形。

我們來看一個例子：

經過以上幾步，我們就完成了一般情形下的左旋轉，我們可以對應地寫幾句偽程式碼，這裡把 37 稱作node，42 稱作 target

function leftRotate(node) {      node.right = target.left      target.left = node      target.color = node.color      node.color = RED  }

顏色翻轉

上一小節我們介紹了左旋轉的情形，其實左旋轉的情形就對應著2-3樹中生成3-節點的情形，也就是從2-節點到3-節點這一步，那麼從3-節點到4-節點，再到拆分4-節點的這一步又對應紅黑樹的什麼操作呢，我們來看一個簡單的例子。

我們以一棵已經擁有兩個節點的紅黑樹為例，現在這一紅一黑兩個節點就對應了2-3樹的3-節點[37 42]，我們加入新的紅色節點 66 ，節點 66 按照二叉搜索樹的原則，暫時加在節點 42 的右子樹上。

之前我們說過，紅色節點表示該節點與其父節點在2-3樹中是平級關係，也就是說這種左右子節點都是紅色節點的情況其實對應了2-3樹中臨時的4-節點。當然，我們知道紅色的節點是只能出現在左子樹上，所以我們需要進行一些變形。

我們應該如何把這棵臨時的不規範的紅黑樹轉換成一棵正確的紅黑樹呢，回想2-3樹拆分4-節點的過程：4-節點被拆分為3個2-節點，拆分後的子樹的根節點向上融合。由於2-節點對應著紅黑樹中的黑色節點，因此我們直接把左右子樹上的37和66直接翻轉為黑色，此即顏色翻轉。由於根節點還需要向上融合，因此我們把根節點再標記為紅色（相當於加入新節點）

我們寫兩句程式碼，畢竟這些翻來覆去的操作不是給人看的，是給機器看的。

程式碼非常簡單，就是把根節點變成紅色，左右子元素變成黑色。當然只有像上圖這種樹結構（根節點黑色而左右子元素紅色）才適用這種顏色翻轉。

function flipColors(node) {      node.color = RED      node.left.color = BLACK      node.right.color = BLACK  }

右旋轉

我們剛才插入了節點66，66比42大，因此被加入到了節點42的右子樹上，然後我們使用顏色翻轉就完成了轉換。然而節點並不總是被添加到右子樹上，比如說插入節點12，12小於37，因此節點12被加入到37的左子樹上：

對於這種情況，我們需要進行右旋轉，我們直接以一般情況來講解：

經過以上幾步，我們就完成了一般情形下的右旋轉，我們可以對應地寫幾句偽程式碼，這裡把 37 稱作target，42 稱作 node。

function rightRotate(node) {      node.left = T1      target.right = node      target.color = node.color      node.color = RED  }

其他情況

我們通過顏色翻轉和右旋轉，解決了往3-節點添加節點的兩種情況，分別是大於b節點情況，小於a節點的情況，那麼如果插入的節點大於 a 而小於 b 呢。

對於上圖的第三種情況，我們需要結合左旋轉、右旋轉、顏色翻轉等子過程來調整成為一棵正確的紅黑樹，下面以[37 40 42]作為例子：

流程總結

我們總結一下以上三種情形，會發現其實紅黑樹插入節點不過五種形式

1. 插入到一個2-節點，且節點小於該2-節點

2. 插入到一個2-節點，且節點大於該2-節點

3. 插入到一個3-節點，且插入節點小於3-節點的兩個節點

4. 插入到一個3-節點，且插入節點大於3-節點的兩個節點

5. 插入到一個3-節點，且插入節點在3-節點的兩個節點之間

其實這五種形式都可以用一個邏輯鏈條來表示，我們回顧一下6.4里，插入的節點小於a大於b的轉換過程，出於通用性，我把具體數字隱去了。

我們發現，這個流程已經包含了以上五種情況，如果我們插入的節點大於a也大於b，那麼我們可以直接跳到第四步，然後進行顏色翻轉；如果我們插入的節點小於a也小於b，那麼跳到第三步；如果插入節點在ab之間，那麼就對應第二步。

有了這個邏輯流程，我們的程式碼一下子清晰起來，我們只需要通過幾個條件判斷，就能描述紅黑樹所有旋轉方式，下面我們來寫一段程式碼：

function add(node) {      //如果右節點為紅色,左節點為黑色, 那麼進行左旋轉, 對應情況2      if(isRed(node.right) && !isRed(node.left)) node = leftRotate(node)        //如果左節點為紅色,左節點的左節點也為紅色, 那麼進行右旋轉, 對應情況3      if(isRed(node.left) && isRed(node.left.left)) node = rightRotate(node)        //如果左右節點都為紅色, 那麼進行顏色翻轉, 對應情況4      if(isRed(node.left) && isRed(node.right)) flipColors(node)    }

到這裡，我們就實現了紅黑樹的所有平衡操作，從這個過程中，我們還能得出一個重要結論，即紅黑樹任何不平衡，都能在3次旋轉內得到解決，這也就是紅黑樹相較AVL樹的優勢所在。

六. 紅黑樹和AVL樹的比較

1. AVL樹比紅黑樹更為平衡，其搜索效率也好於紅黑樹, 經過我們之前的分析可以知道, 紅黑樹在最壞的情況下搜索時間複雜度為2logn，大於AVL樹的logn。AVL樹是嚴格平衡，紅黑樹只能達到「黑平衡」，即從任意節點出發到葉子節點經過的黑節點數量相同，但經過的紅色節點數量不確定，最差的情況下，經過的紅色節點和黑色節點一樣多。

2. 紅黑樹增刪節點的性能優於AVL樹，當我們往紅黑樹增加節點或刪除節點引起紅黑樹不平衡，我們只需要最多三次旋轉就能解決，而相同條件下，AVL樹的旋轉次數要多於紅黑樹，因此紅黑樹在增刪節點上相較於AVL樹更優

七.總結

最後做個概括，紅黑樹是以犧牲部分搜索性能換取增刪性能的折中方案，用非嚴格的平衡，換取旋轉次數的減少。在實際使用中，如果所維護的樹需要頻繁增刪節點，紅黑樹會更加合適，反之，則適合AVL樹。