一. 算法之變，結構爲宗

計算機在很多情況下被應用於檢索數據，比如航空和鐵路運輸業的航班信息和列車時刻表的查詢，都要求快速地找到用戶所需要的信息。所以，對於存儲大量信息的計算機來說，能 “大量存” 固然好，但同時還必須能 “快速取” 纔行。又比如，我們在使用 C++ 或者 Java 這樣的編程語言時，都會用到標準模版類庫，因爲它們簡潔高效，能提供動態增長的各類數據結構，極大地提高了開發效率，同時又保證了健壯性。那麼，再深入一點看這個問題，究竟是什麼 “神祕的力量”，在持續地彰顯這些卓越的“行爲” 呢？
答案是：“結構模式影響行爲”。

“當置身於同一個系統時，其中的事物無論有多大差別，都傾向於產生相似的行爲結果。”

所以你看，在這些高效卓越的檢索能力背後，一定存在着一個隱藏在事物表面以下的 “結構”，正是因爲這個內部結構的存在影響着外部行爲的表現，不同的結構產生不同的影響力，當然也就有好壞之分。

“萬變不離其宗”，很多時候我們在學習和積累的過程中，特別是遇到很多很 “複雜” 的問題時，總是有着一種深深的挫敗感，這種巨大的挫敗感，來自於我們無法把握瞬息萬變的外在行爲。變化的永遠是外部的行爲，不變的永遠是內部影響這些行爲的結構。因此，我們必須拋開讓人眼花繚亂的外部行爲，去洞察事物的內部結構，去把握這個“宗”，這往往有着意想不到的收穫。

爲了提高搜索效率，人們想到了用二叉搜索樹（Binary Search Tree）這樣的非線性數據結構來存儲數據，每次檢索數據時根據關鍵字的大小選擇是往左子樹走還是往右子樹走，這樣每次都少比較了一半的數據，這樣就比線性搜索效率高了。但是，採用 “樹” 的數據結構，就產生了這樣一種行爲影響：檢索的過程是跟着樹的路徑往下走的，因此樹的高度會對效率產生影響，如果恰巧某個搜索路徑比較“深”，那麼查找就比較費時間了，因此不能保證在所有情況下都有很好的效率，打個比方，如果將事先已排好序的序列作爲輸入建立一棵二叉搜索樹，那麼得到的結構可能就變成了圖 1 所示這個樣子：

如果在這樣的 BST 上搜索數據，其效率就變成了 O(n)，就變得很壞。那麼自然就有了一種想法：能不能在 BST 的結構上進行某種 “改進”，讓它的根結點到樹中任意葉結點的路徑都差不多一樣長呢？如果能做到這樣的優化結構，那麼其所表現出來的行爲（也就是搜索效率）必然會得到改善和提高。2-3-4 樹正是在這樣的背景下提出的。

二. 平衡之美：2-3-4 樹

2-3-4 樹有完美的平衡性能——根結點到任意葉子結點的路徑長度相等。“2-3-4 樹” 名稱的來歷是因爲這棵樹包含了三種結點：2-node、3-node 和 4-node。

• 2-node：有 1 個關鍵字，2 個子結點；

• 3-node：有 2 個關鍵字，3 個子結點；

• 4-node：有 3 個關鍵字，4 個子結點。

如圖 2-1，2-node 的左孩子關鍵字小於 W，右孩子關鍵字大於 W；圖 2-2 中孩子結點從左到右，分別是小於 C，介於 C 和 E 之間以及大於 E 的；圖 2-3 中的 4-node 類似。

2.1 2-3-4 樹的查找操作

先看查找操作，查找的過程就是比對關鍵字大小，然後沿着某一路徑向下搜索，直到找到對應結點，或者當找不到時返回 “空”，如圖 2-4 所示。

2.2 2-3-4 樹的插入操作

現在來看看插入操作：首先仍然是按照關鍵字大小沿着樹的路徑向下，當到達 2-node 或者 3-node 時，直接 “擴充” 這個結點——2-node 擴充成 3-node，3-node 擴充成 4-node，如圖 2-5，2-6，2-7，2-8 所示。

但是，如果插入的位置落在一個 4-node 內，就出現問題了，因爲我們既不能把 4-node 再擴充成 5-node，也不能把新加入的結點直接掛在這個 4-node 下，因爲這樣就破壞了 2-3-4 樹完美的平衡性質——根到任意葉結點的路徑相同，如圖 2-9 所示。

那麼遇到這種情況怎麼辦呢？我們的解決辦法是採取分解（split）策略——將 4-node 的 3 個關鍵字中間那個 “向上提”，把它合併到這個 4-node 的父結點中，這個 4-node 被分解爲兩個 2-node，如圖 2-10 所示。

然後，我們再將關鍵字爲 H 的結點插入，即得到了圖 2-11 所示的樣子，注意，此時 2-3-4 樹的完美性質仍然保持。

但是新的問題又產生了喔！仔細想想，如果圖 2-12 這種兩個 4-node 連接在一起的情況發生了該怎麼辦。

有兩種策略解決這個問題——分別稱爲 Top-down 和 Bottom-up。
Bottom-up 策略是，如果分解 4-node 時發現它的父結點仍然是 4-node，就繼續分解，如果有必要的話，這個過程一直持續往上走，直到到達根結點爲止，它是 “自底向上” 的分解策略。
Top-down 策略是，在執行插入操作時，沿樹往下走的路徑上，只要發現 4-node，就對其進行分解，並在底部插入新結點，它是 “自頂向下” 的策略。
這裏我們採用 Top-down 策略，也就是說，在沿着樹向下的過程中，只要發現 4-node 就將其分解，因此我們就保證了當前結點一定不是 4-node，這樣就保證了圖 8 這種情況不會出現，並且我們最後能落在 2-node 和 3-node 中，如圖 2-13 所示。

這樣的分解操作只涉及當前結點和其父結點，因此是局部的操作，不會將調整結點的影響擴散到其他地方，這裏的這個 “分解” 的概念很重要，一定要認真體會和理解，這牽涉到後面對紅黑樹很多調整操作的理解，其實紅黑樹的各種調整操作其本質都來源於 2-3-4 樹。
好了，寫到這裏，如果你真正理解了 “分解” 的概念以及爲什麼要分解，那麼我們就來看一個具體的例子，如圖 2-14，2-15 所示，輸入序列爲“ASERCDINBX”, 建立一棵 2-3-4 樹的過程，注意在插入 R，N，B 和 X 這四個關鍵字時都發生了 4-node 的分解，其中前三個關鍵字是因爲所插入的結點落在 4-node 中，必須分解；最後一個關鍵字是因爲在沿着樹根向下的過程中遇到 4-node 了，對其進行分解（還記得 Top-down 策略嗎）。

2.3 完美平衡的 2-3-4 樹

一棵稍微複雜一些的 2-3-4 樹如圖 2-16 所示，這種完美的平衡感，保證了根到任一葉結點的路徑不會比其他路徑長得太多，也就保證了搜索和插入操作能夠在對數時間內完成，最壞情況下（全是 2-node），其漸進時間複雜度爲 lgN，最好情況下（全是 4-node），其漸進時間複雜度爲 log4(N)=1/2lgN，10 到 20 次操作就能完成對 100，0000 個結點的搜索和插入操作。這就是 “優美” 的結構所產生的卓越能力。

但是，不要高興得太早了，凡事有得必有失，2-3-4 樹的性能雖然接近完美，但是實現起來卻很困難，原因很簡單——要實現這三種結點，還要實現三種結點之間的相互轉換相當困難。實際上，2-3-4 樹的理論意義要強於實際意義，因爲還有一種著名的數據結構也是從 2-3-4 樹衍生出來的，那就是在數據庫領域使用非常多的 “B 樹”，那麼，面對這樣一種完美的數據結構，我們是不是束手無策了呢？也不見得，下面，就輪到紅黑樹登場了。

三. 紅黑樹的崛起

從某種意義上說，紅黑樹是 2-3-4 樹的一種 “精神表達”，其實這也不奇怪，只有神才能創造出完美無瑕的事物，作爲人類，要將完美的東西變成現實，必須根據實際情況稍作修改和犧牲。不先弄懂 2-3-4 樹，是很難理解紅黑樹的各種操作的，但是如果理解了 2-3-4 樹，你就能明白，紛繁複雜的紅黑樹旋轉和顏色翻轉的操作其實就是爲了恢復因插入或刪除結點而造成的 2-3-4 樹性質的破壞，所以，在我們進入具體的紅黑樹討論之前，如果你對 2-3-4 樹還有什麼不瞭解的地方，請不要急躁，再回過頭去好好看看前面的敘述；如果你準備好了，那麼我們開始走進紅黑樹吧。

3.1 紅黑樹的基本性質

《算法導論》一書敘述了紅黑樹的經典五條性質：

“一棵二叉查找樹如果滿足下面的紅黑性質，則爲一棵紅黑樹：

1. 每個結點是紅的，或是黑的；

2. 根結點是黑的；

3. 每個葉結點（NIL）是黑的；

4. 如果一個結點是紅的，則它的兩個兒子都是黑的；

5. 對每個結點，從該結點到其子孫結點的所有路徑上包含相同數目的黑結點。”

其實，如果自己總結一下，紅黑樹的性質大概可以歸納成以下 4 條：

1. 要麼紅，要麼黑；

2. 一頭一尾都是黑；

3. 有紅必有黑；

4. 任意路徑上黑結點個數穩定。

你也許會認爲，這就是紅黑樹的本質了，的確《算法導論》一書對紅黑樹所有操作的敘述，其實就是在保持上面紅黑樹的五條性質，但是這本書卻沒有回答兩個問題：

1. 爲什麼要對結點進行染色？

2. 爲什麼染色後的二叉查找樹的效率就提高了？

3.2 紅黑樹的本質

不搞懂 2-3-4 樹，你永遠無從知曉這個問題的答案。現在，讓我來告訴你什麼是紅黑樹的本質。

紅黑樹的真正本質是要將 2-3-4 樹 “表達” 成二叉搜索樹，2-3-4 樹有三類不同的結點，二叉搜索樹只有一類結點——2-node，因此主要的問題，就是考慮怎麼把 3-node 和 4-node“表達”成 2-node，而 “紅邊” 的引入，使這個問題的解決成爲可能。事實上，在一棵紅黑樹中，結點是無所謂紅色還是黑色的，被染色的不是結點，而是連接結點的邊！，讀過《算法導論》的同學都知道，書上對紅黑樹的描述都是說對結點染色，但是真正的紅黑樹其實是對邊區分紅色和黑色，因爲我們在實現具體的數據結構時，主要是實現結點的數據域，而邊的關係是通過指針來描述的，因此就把邊的顏色值放到結點的域中。

• 當我們說一個結點是紅色時，實際上是指連接它的邊是紅色；

• 當我們說一個結點是黑色時，實際上是指連接它的邊是黑色。

3.3 紅黑樹與 2-3-4 樹的基本對應關係

好了，前面的鋪墊有了，我們回到正題——紅黑樹是怎麼把 2-3-4 樹中的 3-node 和 4-node 表達成 2-node 的？答案是：通過 “紅邊”。也就是說，紅邊是 “內部邊”，黑邊是 “外部邊”，紅黑樹中的黑邊與 2-3-4 樹中的邊一一對應；而紅黑樹中的紅邊在 2-3-4 樹中看不見——因爲紅邊是 3-node 和 4-node 的內部邊。這個概念很重要，後面還要再次提到它，所以請你把她記在心裏。引入紅邊後，3-node 和 4-node 就被表達成如圖 3-1，3-2 這樣的 BST 結構。

於是，通過紅邊和黑邊的幫助，我們就在紅黑樹和 2-3-4 樹之間建立了一個對應關係（請注意，只是對應關係，我沒有說是 “一一對應” 關係，其實如果細心觀察的話，這個從圖 3-1 中你就可以看出來了，這會引出後面一個問題的討論）。一棵 2-3-4 樹在經過紅黑邊的詮釋過後，就成了圖 3-3 中的這個樣子。

（* 注：我覺得這張圖是錯的，右子樹應該是 G 在上面，F 在左下，J 在右下才對，下圖也是同樣的問題，不過將就用吧，心裏有數就好了。）

這並不是唯一的表達方式，事實上，同一棵 2-3-4 樹還有以下三種表達，如圖 3-4 所示。

這可就麻煩了啊，2-3-4 樹和紅黑樹居然沒有一一對應！那得考慮多少種不同的等價情況啊，有的情況完全是左右對稱的——這也是《算法導論》一書讓人費解的原因，因爲大量的代碼都用來處理各種情況了，所以讀起來讓人甚是費解和疑惑。但是仔細觀察，這四種不同表達的關鍵因素在哪？就是紅邊！紅邊可以左斜（Left-Leaning），又可以右斜（Right-Leaning），所以導致 4 種情況的組合（根據概率論的乘法原理），所以，爲了消除這些不必要的複雜情況，我們只研究其中一種：左旋紅黑樹。

四. 左旋紅黑樹（LLRB）

於是左斜紅黑樹（Left-Leaning Red Black Tree）登場了。左斜紅黑樹中，所有的 3-node 其內部的紅邊都是向左傾斜的，這就是 LLRB 名稱的由來，如圖 4-1 所示。

這樣我們不僅保證了完美的黑邊平衡（因爲它本質上是 2-3-4 樹），同時也保證了 2-3-4 樹與其紅黑表示的一一對應關係，如圖 4-2 所示。

呃，讀到這裏大家肯定會有個疑問，2-3-4 樹看起來是挺漂亮的，但是咋一看紅黑樹裏的紅邊怎麼這麼扎眼啊？2-3-4 樹的紅黑表示似乎讓樹 “變高” 了，那麼同學們肯定會問：紅黑樹還能保持 2-3-4 樹的對數時間效率麼？

4.1 搜索效率的數學證明

讓我們用一點點數學分析來回答這個問題吧。
引理：一棵有 n 個內結點的紅黑樹的高度至多爲 2lg(n+1)。
這個定理由《算法導論》一書引出 ，看起來特別的抽象，不好理解，不過沒關係，下面就由我帶領各位來體驗一把書上的證明，我會把書上一些寫的不清不楚、一筆帶過的東西重新詮釋一下，這樣這個定理就不難理解啦！
那麼要證明這個定理呢，我們需要另外一個工具，描述如下：
“對以 x 爲根的子樹，它所包含的內部結點數至少爲 2^[bh(x)]-1（2 的 bh(x) 次方然後再減一）。” 這裏 bh(x) 被定義爲結點 x 的黑高度，就是說，從結點 x（不包括它本身）到它任一個葉結點的路徑上所有黑色結點的個數。
這裏我們用數學歸納法來證明這個工具。

1. 基本步：若 x 高度爲 0，那麼它就是一葉子結點，它確實至少包含 2^0-1=0 個內部結點，基本步證明完畢；

2. 歸納步：假設 x 爲紅黑樹的某一內部結點，且它高度 h>0，那麼它的黑高度就是 bh(x)，但是它的兩個孩子結點呢？這個就根據它們的顏色來判斷了：
   如果 x 有一個紅色的孩子 y，那麼 y 的黑高度 bh(y)=bh(x)，看看上面對黑高度的定義你就明白了——既然它是紅色的，那麼它的黑高度就應該和它父親的黑高度是一樣的；
   如果 x 有一個黑色的孩子 z，那麼 z 的黑高度 bh(z)=bh(x)-1，這個怎麼解釋呢，因爲它自己就是個黑結點，那麼在計算它的黑高度時，必須把它自己排除在外（還是根據定義），所以它是 bh(x)-1。
   現在關鍵的來了：x 的孩子結點所構成的子樹的高度肯定小於 x 這顆子樹，那麼對於這兩個孩子，不管它們顏色如何，一定滿足歸納假設的，所以，對 x 來說，它所包含的內部結點個數 “至少” 爲兩個孩子結點所包含的內部結點數，再加上它自己，於是就爲 2[bh(x)-1]-1+2[bh(x)-1]-1+1=2^[bh(x)]-1，歸納證明完畢。好了，工具拿到手上了。

現在該幹什麼呢？對！現在該完成對原引理的證明啦，不過在此之前，我們先來回顧一下紅黑樹的五個性質。

1. 每個結點或者是紅的，或者是黑的；

2. 根結點是黑的；

3. 每個葉結點（NIL）是黑的；

4. 如果一個結點是紅的，則它的兩個兒子都是黑的；

5. 對每個結點，從該結點到其子孫結點的所有路徑上包含相同數目的黑結點。

相信不斷地重複能讓人記得更牢，從特性 4）我們知道，如果有一個紅結點存在，那麼它的兩個子結點一定是黑的，最極端的情況下，該路徑上所有的結點就被紅、黑兩種結點給平分了，所以，我們可以說，對於任意一棵紅黑樹，從它根結點到任一葉結點的路徑上黑結點的個數至少佔到了一半，不知這個問題我解釋清楚沒有，因爲這是往下理解的關鍵。
如果一棵紅黑樹的高爲 h，那麼在這個高度上（不包括根結點本身）至少有 1/2h 的黑結點，再結合上面對 “黑高度” 的定義，我們說，紅黑樹根結點的黑高度至少是 1/2h，好了，現在拿出上面那個工具，設 n 爲該紅黑樹所包含的內部結點數，我們得出如下結論：
n>=2^(1/2h)-1

我們把它整理整理，就得到了 h<=2lg(n+1)，就是我們要證明的結論：紅黑樹的高度最多也就是 2lg(n+1)。

現在明白爲啥紅黑樹的效率還是很高了吧，因爲這些操作在一棵高度爲 h 的二叉查找樹上運行時間爲 O(h)，而包含 n 個結點的紅黑樹是高度爲 O(lgn) 的查找樹，所以相關的操作還是能在對數時間內完成，這下我們就可以放心了。

4.2 必須要避免的兩種情況

刻意地讓紅邊向左傾斜，就要考慮新結點插入後的邊的調整問題，因爲可能會產生兩種不允許的情況出現。稍後將會看到，每次插入的新結點都是用紅邊去連接它的（就是說插入的默認都是紅結點，然後再根據情況進行調整），那麼如果插入的結點恰好作爲其父結點的右子結點的話，樹中就有右斜的紅邊了，這是第一種不允許的情況，如圖 4-3 所示。

第二種不允許的情況是，如果插入的新結點，其父結點也是紅邊連接的，那麼在一條路徑上就出現了兩個連續的紅邊，這叫 “two reds in a row”，這也是不允許的（回憶一下《算法導論》一書經典的紅黑定義——紅結點的孩子必定是黑結點），四種不允許的情況如圖 4-4 所示。

好了，這裏總結一下，我們的 LLRB 是一棵特殊的紅黑樹結構，它不允許下面兩種情況出現：

1. 右斜的紅邊；

2. 兩個連續的紅邊出現在一條路徑上。

注意喔！標準的紅黑樹是允許情況 1 出現的，因爲這裏實現的是 LLRB，是紅邊向左傾斜的，所以這種情況也不允許了——這可以簡化很多對稱結構的討論！好了，理論準備足夠充分之後，我們下面要展開對具體編程實現的討論，在具體的編程語言實現中結合代碼來分析紅黑樹的各種旋轉和調整操作，在此之前，仍然希望你先看懂上面的討論，如果你準備好了，那麼我們繼續深入到代碼層吧！

五. LLRB 的 Go 語言實現

5.1 數據結構

我們先來看看紅黑樹的數據結構，這裏設計的紅黑樹的結點由 6 個域組成：鍵、值、顏色（紅或者黑）、父結點，左子結點和右子結點，即一個六元組 <key, value, color, parent, left, right>。其中爲了提高程序的通用性，我們把關鍵字和對應值的類型分別定義爲 KeyType 和 ValType，並將顏色值（RED 和 BLACK）和布爾值（TRUE 和 FALSE）定義成常量。然後我們使用一個 head 指針作爲整個紅黑樹的頭部，head 指針的右子結點指向紅黑樹的樹根。

type rbnode struct {
  key, value interface{}
  red bool
  left, right *rbnode
}

type RBTree struct {
  root *rbnode
  length int
  less func(a, b interface{}) bool
}

5.2 debug 方法論

只要跟編程打交道，就絕對少不了 debug，不論你考慮得再怎麼仔細，bug 總是存在的，不過呢，我們總是有方法來儘量減少 bug 的出現，儘量提高程序的健壯性，下面就來介紹一下我 debug 的三件法寶吧。

5.2.1 防禦性編程（Defensive Programming）

工程師最有力的武器，永遠是自己的大腦。不要急着編寫代碼，寫之前一定要仔細地考慮好，借用莫扎特那句名言：

“Everything has been composed, just not yet written down.”

思想應該是先在大腦中構思充分並反覆推敲之後，再考慮它在現實世界的成形。至少考慮好三件事，首先我這個函數要實現什麼功能？如果你發現你的函數完成了兩個或以上的功能，那還是重構一下好一些，最好一個函數只做好一件事，這符合 UNIX 的設計哲學；其次，這個函數的執行需要滿足什麼先決條件（precondition）？是不是一定要保證在某些指針變量不爲空的前提下執行？注意喔，在執行具體操作之前檢查先決條件就是防禦性編程的精髓！否則如果不滿足條件就執行，最後可能會得到一些莫名奇妙的結果，到時候再調試，你找都找不到問題出在哪兒，所以，考慮清楚先決條件不僅減少了很多不必要的麻煩，同時也爲後來的單元測試提供便利：認真檢查先決條件就是了；最後，就是後置條件（postcondition）——你這個函數執行了什麼改變？函數執行後得到什麼結果？把這三個因素都考慮清楚了，能極大地提高代碼的健壯性，一般呢，我會將函數的一個簡短的描述以及先決條件和後置條件寫成註釋放在函數的開頭。

func function(/* parameter list*/) {
  /*  * DESC: function described here  * PRE: function's preconditions  * POST: function's postconditions  */

  // CODE...
}

5.2.2 測試驅動開發（Test-Driven Development）

此方法來源於敏捷思想，具體地說，就是先寫測試，然後用測試來驅動開發。在構思好模塊的功能後，我們可以先將測試代碼寫出來，然後我們剩下的工作就是圍繞測試代碼來展開：編寫正確的代碼，使得測試通過。Bob 大叔在他的大作《敏捷軟件開發——原則、模式與實踐》一書中談到了 TDD 的好處有如下幾點：

程序中的每一項功能都有測試來驗證它的操作的正確性；
迫使我們站在調用者的觀察角度，關注功能的同時也關注了接口；
迫使自己把程序設計爲可測試的，可測試性使得程序與其他部分解耦合；
測試代碼是一種無價的文檔形式。

因此，往後對紅黑樹的討論就採取 TDD 的方法，先寫測試，再寫代碼，每完成一個功能就運行測試代碼看看結果，直到能夠正常結束並得到正確的結果爲止，然後再編寫新的測試和新的功能並與以前的測試代碼一起運行，這個過程一直持續到整個開發結束，這樣保證了新添加的功能不會影響到以前編寫的代碼，。

5.2.3 gdb 調試器

這個是每一個 Linux 程序員必知必會的強大工具了，使用它，可以反彙編、單步執行、設置斷點、設置觀察點.

5.2.4 創建紅黑樹、新建結點和判斷結點顏色

對於創建紅黑樹的操作，我們希望該樹在創建時是一棵 “空樹”。然後我們就着手編寫 NewRBTree() 的代碼吧，如下所示。

func NewRBTree(less func(a, b interface{}) bool) *RBTree {
  return &RBTree{
    less: less,
  }
}

然後是判斷結點顏色和創建紅黑樹結點的操作。要注意當相應結點爲 nil 時，返回 FALSE，這個 nil 結點代表葉子結點。本文中所畫的紅黑樹都是內結點，即含有鍵值對的結點，而真正的葉結點是空結點，不含鍵值對。回憶一下，按照紅黑樹的定義葉子結點必須是黑結點（性質 3），故返回 false。

func isRed(node *rbnode) bool {
  return node != nil && node.red
}

func newRBNode(k, v interface{}) *rbnode {
  return &rbnode{
    key: k,
    value: v,
  }
}

5.2.5 左旋、右旋和顏色翻轉

對紅黑樹的相關操作（如插入，刪除）本質上都是基於對二叉查找樹的操作，但是，在紅黑樹的上下文中，相關操作有可能會破壞紅黑性質，因此，必須對被破壞的性質進行 “修復”，而左旋（left-rotating）、右旋（right-rotating）和顏色翻轉（color flip）就是對紅黑樹進行修復的操作。但是修復並不是毫無章法的，對於不同的情況要採取不同的修復策略，相應情況和對應修復策略如圖 4-5 所示。

理解爲什麼要旋轉調整的關鍵，在於將 2-3-4 樹與其相應的紅黑表示聯繫起來看。這裏以插入操作爲例（刪除操作類似），圖 25 中紅圈所示情況爲我們有一個新插入的結點插入到了 2-node 的右孩子處，此時在對應的紅黑表示中紅邊被右旋，於是我們就用左旋操作來恢復 LLRB“紅邊左斜（left-leaning）” 的性質；當插入的結點作爲 3-node 的最左孩子時，對應的紅黑表示如圖中藍圈所示，此時我們只要將其右旋即可；而當新插入結點作爲 3-node 的中間孩子插入時，此時對應的紅黑表示如圖中黃圈所示，這時我們先執行一個左旋操作轉換成藍圈所示情況，然後再執行一個右旋即可。那麼爲什麼要執行顏色翻轉呢？回憶一下，上面我們在討論 2-3-4 樹的時候，談到了 4-node 的分解，而顏色翻轉的操作，就是爲 4-node 準備的。理解的關鍵，還是要把 2-3-4 樹和它對應的紅黑表示聯繫起來，如圖 4-6 所示。

顏色翻轉之後，圖 4-6 中原本由 M、E 和 Q 共同組成的 4-node 就被拆分了，E 和 Q 分別形成一個 2-node，而 M 結點由於被紅邊連接而 “融入” 到了上面的結點中——如果 M 的父結點是 2-node，則此時該父結點變成 3-node，這一共有 2 種情況；如果 M 的父結點是 3-node，那麼此時該父結點變成 4-node，這一共有 3 種情況，如圖 4-7、圖 4-8 所示。

好了，理論到此爲止，下面開始貼代碼，注意，旋轉操作只旋轉紅邊。

func rotateLeft(node *rbnode) *rbnode {
  rightChild := node.right
  node.right = rightChild.left
  rightChild.left = node
  rightChild.red = node.red
  node.red = true
  return rightChild
}

func rotateRight(node *rbnode) *rbnode {
  leftChild := node.left
  node.left = leftChild.right
  leftChild.right = node
  leftChild.red = node.red
  node.red = true
  return leftChild
}

func colorFlip(node *rbnode) *rbnode {
  node.red = !node.red
  if node.left != nil {
    node.left.red = !node.left.red
  }
  if node.right != nil {
    node.right.red = !node.right.red
  }
  return node
}

六. 紅黑樹的插入操作

有了上述的三個輔助函數，我們現在可以來討論一下紅黑樹的插入操作，紅黑樹的插入算法可以分成兩個基本部分：一是以二叉查找樹爲基礎的結點遞歸插入操作，這裏對已經存在的關鍵字更新其相應的值，而對於原來樹中沒有的關鍵字新建紅結點進行插入；二是對樹進行 “修復” 操作。

6.1 插入操作的分情況討論

爲了方便理解，還是把插入操作分解成以下六種情況吧：
情況 1：若新插入的紅黑結點關鍵字並不存在於原來的紅黑樹中，那麼將該結點插入到樹的底部（否則更新對應關鍵的值），如圖 6-1 所示；

情況 2：在沿樹根向下遞歸的過程中若發現當前結點是 4-node，則分解它，判斷當前結點是否爲 4-node，就是看它的左子和右子結點是不是都是紅色，如圖 6-2 所示；

情況 3：若新插入結點的關鍵字小於當前結點關鍵字，則插入其左子樹中（遞歸）；
情況 4：若新插入結點的關鍵字大於當前結點關鍵字，則插入其右子樹中（遞歸）；
情況 5：遇到向右傾斜的紅邊，將其向左旋轉，如圖 6-3 所示；

情況 6：遇到兩條紅邊在一條路徑上，對其進行平衡，如圖 6-4 所示；

這六種情況是按順序安排的——即我們的插入算法即按照情況 1 到情況 6 的先後順序來執行代碼的。

6.2 紅黑狀態修復

情況 2、情況 5 和情況 6 都是對插入新結點後紅黑樹性質的修復，考慮到後面的刪除操作也需要進行相應的修復操作，這裏就使用了一個小技巧，我們把 2，5 和 6 三種情況稍微調整一下順序，並重構到一個函數中，統稱爲 “fixUp”。

func fixUp(node *rbnode) *rbnode {
  if isRed(node.right) {
    node = rotateLeft(node)
  }
  if isRed(node.left) && isRed(node.left.left) {
    node = rotateRight(node)
  }
  if isRed(node.left) && isRed(node.right) {
    node = colorFlip(node)
  }
  return node
}

注意，這裏有一個非常重要的細節上的不同就產生了。本來，如果我們按照先前介紹的順序執行情況 1 到情況 6，那麼我們就是在自頂向下地邊插入新結點邊修復紅黑樹性質，而當我們將修復的操作重構成 fixUp()函數並在插入操作完成後執行，就變成了自底向上地 “事後修復” 紅黑性質了！非但如此，我們還引入了兩個細微但是至關重要的不同點，仔細觀察上面的代碼，你會發現兩個問題——首先是對 4-node 的拆分操作被放到了兩個旋轉調整操作的後面，這樣一來，我們的 LLRB 就不再是對 2-3-4 樹的表示了，而是對 2-3 樹的表示！因爲沿路徑向上的 4-node 全部被提前分解，不存在 4-node 了！這是隻看代碼不容易察覺的差別；然後就是多了個語句判斷該結點的父結點是不是 head，若是的話就將其染黑，這是因爲在我們沿路徑向上不斷修復紅黑性質的時候根結點有可能被染紅，而爲了防止這種情況的發生，我們在修復的最後都會強制染黑根結點。好了，前面鋪墊了這麼多分析，就是怕大家不好理解，看到這裏，插入算法也該隆重登場了，其實只有很簡單的幾行，只要結構組織得好，編寫的代碼就能體現出簡潔的美，如圖 40 所示。

func (r *RBTree) insert(node *rbnode, k, v interface{}) (*rbnode, bool) {
  ok := false
  if node == nil {
    return &rbnode{key: k, value: v, red: true}, true
  }
  if r.less(k, node.key) {
    node.left, ok = insert(node.left, k, v)
  } else if r.less(node.key, k) {
    node.right, ok = insert(node.right, k, v)
  } else {
    node.value = v
    ok = true
  }
  return fixUp(node), ok
}

相信我不用再做過多解釋，大家也能看懂它在做什麼了，無非是一個二叉插入操作，然後返回一個修復過的結點。如果插入操作弄懂了，下面我們就要進入，更加複雜的——刪除操作啦！

七. 紅黑樹的刪除操作

從這裏開始，我們就正式介紹 LLRB 的刪除操作，刪除操作比插入操作要複雜一些，但也不是完全沒有規律可循，我們甚至還可以從插入操作中獲得一些啓示，因此，對刪除操作的介紹分爲兩個部分：首先進行一下熱身，先給出刪除最大元素和刪除最小元素的實現，然後再正式討論刪除任意元素的操作。不過在展開介紹之前，先讓我們提綱挈領地討論一下紅黑樹的刪除操作，介紹一些基本的，起關鍵作用的思想，這樣能夠增進對後面所討論內容的理解。回想一下剛纔的插入操作，我們在插入新結點的時候最害怕什麼？最害怕紅黑樹性質的破壞，和碰到 4-node，對吧？紅黑樹性質被破壞了，我們就要採用相應措施修復，遇到 4-node 的時候，新結點根本插不進去——因爲 4-node 已經 “滿” 了，沒有空間插入新結點了——這也是我們不遺餘力地分解 4-node 的原因（還記得 “顏色翻轉” 嗎）。
刪除操作只不過是插入操作的 “反操作”，一個增加結點，一個減少結點，因此插入操作中肯定有東西值得刪除操作借鑑，因爲相互矛盾的事物往往又是相互聯繫的。首先很明顯的一點是，刪除操作也可能會破壞紅黑性質，特別是你刪到黑結點的時候，所以刪除之後還是要修復的，這也是爲什麼會有 fixUp() 函數的原因。其次，如果說當執行插入操作時，我們害怕遇到 4-node，那麼對稱地看，在刪除操作時，我們最怕遇到的是 2-node，因爲對於 3-node 和 4-node，刪除操作只是分別將它們變成 2-node 和 3-node，如圖 7-1 所示。

但是針對 2-node 刪除操作則把這個結點給刪沒了，更嚴重的是，刪除 2-node 就相當於刪除紅黑樹中的黑結點，這就會破壞紅黑樹的性質 5）。所以，刪除操作成功的關鍵就是看我們是否善於轉化——當我們遇到 2-node 時，將其轉化成 3-node 或 4-node？這本質上是一種數學思維（即將未解決的問題轉化成已經解決的問題）。怎麼轉化？答案是要麼進行 “合併”，要麼就 “借”。當遇到 2-node 時：

1. 如果 2-node 的兄弟結點是 2-node，那麼我們就把這兩個 2-node 合併成 4-node，如圖 7-2 所示；

2. 如果 2-node 的兄弟結點是 3-node 或者 4-node，那麼我們就向它們 “借” 一個結點過來將這個 2-node 轉化爲 3-node，如圖 7-3 所示。

這裏要提一點，我們要感謝偉大的 LLRB，正是因爲它向左傾斜紅結點的表示方法讓我們省去了很多對稱情況的討論，保持了代碼的簡潔高效，易於理解。

7.1 刪除最大關鍵字

好了，言歸正傳，讓我們用遞歸的思想來思考刪除紅黑樹最大關鍵字結點的過程，由於二叉查找樹本身的性質，要刪除一棵紅黑樹的最大關鍵字結點，就是刪除它的右子樹的最大關鍵字結點，然後這個過程又可以看成刪除右子樹的右子樹的最大關鍵字結點…… 就這麼一直遞歸下去，直到我們走到那個其右子樹爲 “空” 的結點，就是我們要刪除的結點了。可是剛纔說了，如果刪除了黑結點是會破壞紅黑性質的，且要刪除的結點右子樹爲空，並不代表左子樹就爲空，刪除結點的同時還要考慮其左結點的連接問題，怎麼辦呢？
這裏我們採用一個小技巧——把紅邊往右搬，即當我們在沿右子樹不斷遞歸向下的過程中, 遇到向左傾斜的紅邊（這是肯定會遇到的）就把它往右搬，並且當遇到 2-node 時，就按照上面所說的，或採用合併策略，或採用借取策略來將 2-node 轉化成 3-node 或 4-node，這樣最終能保證最後被刪除的結點是紅結點，並位於整棵樹的底端。具體說來，處理兩種情況：遇到向左傾斜的紅邊，就將其旋轉成向右傾斜（保證較大元素被 “推” 到右子樹去），如圖 7-4 所示。

若發現當前結點 h 的右子結點和右子結點的左子結點都是黑結點（注意，這說明當前結點的右子結點是 2-node），那麼：

1. 那麼，當 h 的左子結點的左子結點是黑結點時（這說明 h 的左子結點是 2-node），就採取合併策略，如圖 7-5 所示；

2. 否則，當 h 的左子結點的左子結點是紅結點時（這說明 h 的左子結點一定不是 2-node），就採取借取策略，如圖 7-6 所示。

這裏的情況 2 是有點複雜，不好理解，但是我反覆強調，理解紅黑樹的關鍵不在紅黑樹本身，而在 2-3-4 樹，因此，你把這兩種情況和圖 4-2，圖 4-3 對 2-3-4 樹較爲抽象的討論進行對比，就能理解爲什麼會這樣做了。好了，下面我們來看代碼。

func moveRedRight(node *rbnode) *rbnode {
  node = colorFlip(node)
  if node.left != nil && isRed(node.left.left) {
    node = rotateRight(node)
    node = colorFlip(node)
  }
  return node
}

如果看懂了上面的分析，理解這裏的代碼應該不是問題，由此看來，某些 “看上去簡單” 的代碼，其背後的原理不一定也簡單，所以，真正發自內心地掌握原理纔是理解和解決問題的關鍵。刪除紅黑樹中最大結點的代碼如下所示。

func deleteMax(node *rbnode) *rbnode {
  if isRed(node.left) {
    node = rotateRight(node)
  }
  if node.right == nil {
    return nil
  }
  if !isRed(node.right) && !isRed(node.right.left) {
    node = moveRedRight(node)
  }
  node.right = deleteMax(node.right)
  return fixUp(node)
}

有基本知識的讀者應該馬上就能發現，這是一個遞歸調用的函數，遞歸終結的條件就是當目標結點 h 的 right 指針指向的右子樹爲 “空”，此時 h 就是包含最大關鍵字的結點，故使用 deleteNode（）函數刪除之；否則在沿樹的右子樹不斷向下遞歸的過程中，若發現 h 結點左子樹是紅色，就右旋；發現 h 的右孩子是黑結點，就調用 moveRedRight() 進行處理，最後返回修復過的紅黑樹（注意，修復操作也是自底向上遞歸進行的）。圖 7-7 和圖 7-8 給出兩個刪除最大關鍵字結點的示例。

7.2 刪除最小關鍵字

弄明白了刪除最大關鍵字結點的操作，那麼刪除最小關鍵字結點的操作其實也很好理解——對稱地理解就可以了，根據 BST 的性質，最小關鍵字結點一定存在於左子樹中，我們要刪除最小關鍵字結點，只要沿左子樹一路遞歸向下即可。由於這裏討論的是 LLRB，所以紅邊本來就是向左傾斜的，所以如果跟上面刪除最大關鍵字結點要考慮的那兩種情況對比的話，情況 1 就不用考慮了，而情況 2 需要對稱地考慮如下。若發現當前結點 h 的左子結點和該左子結點的左子結點都是黑結點（注意，這說明當前結點的左子結點是 2-node），那麼：

1. 若 h 的右孩子的左孩子是黑結點，那麼採取 “合併” 策略，如圖 7-9 所示。

2. 否則，若 h 的右孩子的左孩子是紅結點，那麼採取 “借取” 策略，只不過這裏是從右邊往左邊 “借” 紅結點，跟上面的情況恰好相反，如圖 7-10 所示。

下面我們先來看關鍵的 moveRedLeft() 函數。

func moveRedLeft(node *rbnode) *rbnode {
  node = colorFlip(node)
  if isRed(node.right.left) {
    node.right = rotateRight(node.right)
    node = rotateLeft(node)
    node = colorFlip(node)
  }
  return node
}

不多做解釋了，直接看刪除最小結點的代碼，如圖 54 所示。

func deleteMin(node *rbnode) *rbnode {
  if node.left == nil {
    return nil
  }
  if !isRed(node.left) && !isRed(node.left.left) {
    node = moveRedLeft(node)
  }
  node.left = deleteMin(node.left)
  return fixUp(node)
}

圖 7-11 給出一個刪除操作的示例。

以上就是兩個刪除特殊元素的操作，算是一個熱身運動，因爲我們下面要開始分析真正的刪除操作了——即刪除任意元素的操作，在此之前一定要弄清楚上面兩個特殊過程，因爲下面的分析將會在上面兩個特殊情況的基礎上完成——本來就該這樣嘛，因爲從特殊到一般，是科學研究的基本方法。

7.3 一般刪除操作

如果說刪除最大關鍵字結點的操作是向右搬運紅邊，刪除最小關鍵字的操作是向左搬運紅邊，那麼刪除任意結點的操作，可以被稱爲 “混合搬運”——在查找被刪除結點的過程中沿樹向下遞歸，若是向左走，就把紅邊向左搬運，若是向右走，則把紅邊向右搬運，在刪除的時候考慮兩種情況：

1. 被刪除的結點沒有子結點——直接刪除；

2. 被刪除的結點有子結點——用該結點的直接後繼覆蓋它，然後刪除它的後繼元素（這裏跟二叉查找樹的操作相同）

func (r *RBTree) delete(node *rbnode, k interface{}) (*rbnode, bool) {
  ok := false
  if r.less(k, node.key) {
    if root.left != nil {
      if !isRed(node.left) && !isRed(node.left.left) {
        node = moveRedLeft(node)
      }
      node.left, ok = delete(node.left, k)
    }
  } else {
    if isRed(node.left) {
      node = rotateRight(node)
    }
    if !r.less(k, node.key) && !r.less(node.key, k) && node.right == nil {
      return nil, true
    }
    if node.right != nil {
      if !isRed(node.right) && !isRed(node.right.left) {
        node = moveRedRight(node)
      }
      if !r.less(k, node.key) && !r.less(node.key, k) {
        smallest = min(node.right)
        node.key = smallest.key
        node.value = smallest.value
        node.right = deleteMin(node.right)
        ok = true
      } else {
        node.right, ok = r.delete(node.right, k)
      }
    }
  }
  return fixUp(node), ok
}

func min(node *rbnode) *rbnode {
  for node.left != nil {
    node = node.left
  }
  return node
}

我們來分析一下這個過程：這個函數在一開始執行時傳遞給 h 指針的是紅黑樹的樹根，因此刪除操作是從樹根開始的。一開始先將 h 的關鍵字與 key 進行對比：1）若發現當前結點關鍵字大於 key，說明目標結點在其左子樹上，於是根據情況先將紅邊向左搬運，然後調用 h->left = delete(h->left, key) 向左遞歸這個過程；2）否則，若當前結點關鍵字不大於 key，那麼就是小於或等於 key 了，這就意味着下一步要麼向右子樹遞歸這個刪除過程（如果小於），要麼就地刪除這個結點（如果等於），所以，若 h 結點左子結點是紅色，就先將其往右傾斜（以防萬一），然後檢查它是不是有子結點，如果沒有，直接刪除並返回空，否則，將紅邊往右搬，最後根據情況 2）刪除它（此時被刪除的結點有子結點），並在函數的最後返回修復過的結點。這裏提醒一點，也許你會有疑問，爲啥判斷該結點是否有子結點只判斷了右子結點而不考慮左子結點？（if((key == h->key) && (h->right == NULL))），這是因爲左子結點已經被我們向右旋轉了，所以不用考慮，這裏一定要想明白。

八. 知行合一

好了，紅黑樹的基本操作，到這裏算是討論完了，這篇文章花了很大的篇幅，從 2-3-4 樹的完美平衡性開始介紹，再到後來的紅黑樹的各種性質和操作的分解討論，一點一點向你展示了紅黑樹的前因後果，爲什麼它有這麼高的效率。這裏，要感謝 Princeton 的 Sedgewick 教授，本文的所有截圖均來自於 Sedgewick 先生的 PPT 和《C 算法》一書，在此對您表示最爲誠摯的敬意！其實人的思維是無限的，想象力也是無限的，但是思維世界中近乎完美的事物在現實世界中是不容易構建的，它需要我們做出某種 “改造”，才能很好地和現實情況結合起來。我覺得紅黑樹對我最大的啓發就是——一個真正的理想主義者應該是面對現實的，我們既不該沉淪在自己的幻想中逃避現實；也不該讓外部世界成爲奴役心靈的囚籠。就像陽明先生說的，“知行合一”。

轉自：

jianshu.com/p/0319d7781814

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/SB3UsYi73BwFwLLbeY-nKQ