前言
紅黑樹是數據結構中比較複雜的一種，花了一週的空閒時間跟它死磕，終於弄明白並實現了紅黑樹。寫文總結一下，希望能給試圖理解紅黑樹的同學一些靈感，也讓我能記得更深刻。
在研究紅黑樹時吃了不少苦頭，原因有二：
- 紅黑樹的插入和刪除非常複雜，很多人並沒有理解或完全實現，或實現了的沒有任何註釋，讓人很難參考；
- 網絡上紅黑樹的理解方式較為單一，一般是 雙黑、caseN 法，而插入和刪除的情況很多，每種都有對應的處理方式，如果死記硬背的話，再過一段時間再回憶各種情況可能就一頭霧水了。
網絡上講紅黑樹的實現多來源於《算法導論》一書，直接講紅黑樹的實現，需要處理顏色和高度兩種屬性約束，比較晦澀。本文通過紅黑樹的等同—— 2-3-4樹，避開顏色屬性約束，也弱化了高度的影響，以另一種方式去理解紅黑樹，雖然並不能完全降低它的複雜度，但自認為較之普遍實現，更易記一些。
紅黑樹
定義
紅黑樹是一種結點帶有顏色屬性的二叉查找樹，但它在二叉查找樹之外，還有以下要求：
- 節點是紅色或黑色。
- 根是黑色。
- 所有葉子都是黑色（葉子是NIL節點）。
- 每個紅色節點必須有兩個黑色的子節點。（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點。）
- 從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點。
下圖就是一個典型的紅黑樹：
更多C/C++學習資料，請私信我“代碼”，即可獲取
但實現上我省略了其中的 Nil 結點，一般如下圖，大家理解時也可以忽略它們。
更多C/C++學習資料，請私信我“代碼”，即可獲取
優勢和用途
我們知道二叉查找樹在不停地添加或刪除結點後，可能會導致結點情況如下：
更多C/C++學習資料，請私信我“代碼”，即可獲取
這種情況下，二叉查找樹的查找效率最壞會降低為 O(n)。
而紅黑樹由於在插入和刪除結點時都會進行變色旋轉等操作，在符合紅黑樹條件的情況下，即使一邊子樹全是黑色結點，另一邊子樹全是紅黑相間，兩子樹的高度差也不會超過一半。一棵有 n 個結點的紅黑樹高度至多為 2log(n+1)，查找效率最壞為 O(log(n))。
所以紅黑樹常被用於需求查找效率穩定的場景，如 Linux 中內核使用它管理內存區域對象、Java8 中 HashMap 的實現等，所以瞭解紅黑樹也很有意義。
下面介紹一下紅黑樹的等同 2-3-4樹。
2-3-4樹
定義
2-3-4樹是四階的 B樹(Balance Tree)，它的結構有以下限制：
- 所有葉子節點都擁有相同的深度。
- 節點只能是 2-節點、3-節點、4-節點之一。
- 2-節點：包含 1 個元素的節點，有 2 個子節點；
- 3-節點：包含 2 個元素的節點，有 3 個子節點；
- 4-節點：包含 3 個元素的節點，有 4 個子節點；
- 元素始終保持排序順序，整體上保持二叉查找樹的性質，即父結點大於左子結點，小於右子結點；而且結點有多個元素時，每個元素必須大於它左邊的和它的左子樹中元素。
下圖是一個典型的 2-3-4樹（來自維基百科）：
更多C/C++學習資料，請私信我“代碼”，即可獲取
2-3-4樹的查詢操作像普通的二叉搜索樹一樣，非常簡單，但由於其結點元素數不確定，在一些編程語言中實現起來並不方便，實現一般使用它的等同——紅黑樹。
對應紅黑樹
至於為什麼說紅黑樹是 2-3-4樹的一種等同呢，這是因為 2-3-4樹的每一個結點都對應紅黑樹的一種結構，所以每一棵 2-3-4樹也都對應一棵紅黑樹，下圖是 2-3-4樹不同結點與紅黑樹子樹的對應。
更多C/C++學習資料，請私信我“代碼”，即可獲取
而上文中的 2-3-4樹也可以轉換成一棵紅黑樹：
更多C/C++學習資料，請私信我“代碼”，即可獲取
由紅黑樹的性質5，和 2-3-4樹的性質1，為了便於理解紅黑樹和 2-3-4樹的對應關係，我們可以把紅黑樹從根結點到葉子結點的黑色結點個數定義為高度。
紅黑樹和 2-3-4樹的結點添加和刪除都有一個基本規則：避免子樹高度變化，因為無論是 2-3-4樹還是紅黑樹，一旦子樹高度有變動，勢必會影響其他子樹進行調整，所以我們在插入和刪除結點時儘量通過子樹內部調整來達到平衡，2-3-4樹實現平衡是通過結點的旋轉和結點元素數變化，紅黑樹是通過結點旋轉和變色。
下面來對照著 2-3-4樹說一下紅黑樹結點的添加和刪除：
結點插入
2-3-4樹中結點添加需要遵守以下規則：
- 插入都是向最下面一層插入；
- 升元：將插入結點由 2-結點升級成 3-結點，或由 3-結點升級成 4-結點；
- 向 4-結點插入元素後，需要將中間元素提到父結點升元，原結點變成兩個 2-結點，再把元素插入 2-結點中，如果父結點也是 4-結點，則遞歸向上層升元，至到根結點後將樹高加1；
而將這些規則對應到紅黑樹裡，就是：
- 新插入的結點顏色為紅色，這樣才可能不會對紅黑樹的高度產生影響。
- 2-結點對應紅黑樹中的單個黑色結點，插入時直接成功（對應 2-結點升元）。
- 3-結點對應紅黑樹中的黑+紅子樹，插入後將其修復成 紅+黑+紅 子樹（對應 3-結點升元）；
- 4-結點對應紅黑樹中的紅+黑+紅子樹，插入後將其修復成紅色祖父+黑色父叔+紅色孩子子樹，然後再把祖父結點當成新插入的紅色結點遞歸向上層修復，直至修復成功或遇到 root 結點；
更多C/C++學習資料，請私信我“代碼”，即可獲取
如上圖所示，雖然向紅黑樹中插入了一個新結點，但由於旋轉和變色，子樹的高度保持不變。
刪除結點
紅黑樹的刪除要比插入要複雜一些，我們還是類比 2-3-4樹來講：
- 查找最近的葉子結點中的元素替代被刪除元素，刪除替代元素後，從替代元素所處葉子結點開始處理；
- 降元：4-結點變 3-結點，3-結點變 2-結點；
- 2-結點中只有一個元素，所以借兄弟結點中的元素來補充刪除後的造成的空結點；
- 當兄弟結點中也沒有多個元素可以補充時，嘗試將父結點降元，失敗時向上遞歸，至到子樹降元成功或到 root 結點樹高減1；
將這些規則對應到紅黑樹中即：
- 查找離當前結點最近的葉子結點作為替代結點（左子樹的最右結點或右子樹的最左結點都能保證替換後保證二叉查找樹的結點的排序性質，葉子結點的替代結點是自身）替換掉被刪除結點，從替代的葉子結點向上遞歸修復；
- 替代結點顏色為紅色（對應 2-3-4樹中 4-結點或 3-結點）時刪除子結點直接成功；
- 替代結點為黑色（對應 2-3-4樹中 2-結點）時，意味著替代結點所在的子樹會降一層，需要依次檢驗以下三項，以恢復子樹高度：
- 兄弟結點的子結點中有紅色結點（兄弟結點對應 3-結點或 4-結點）能夠“借用”，旋轉過來後修正顏色；
- 父結點是紅色結點（父結點對應 3-結點或 4-結點，可以降元）時，將父結點變黑色，自身和兄弟結點變紅色後刪除；
- 父結點和兄弟結點都是黑色時，將子樹降一層後把父結點當作替代結點遞歸向上處理。
完整代碼，以及更多學習資料，私信“代碼“獲取
如上圖，刪除的要點是 找到替代結點，如果替代結點是黑色，遞歸向上依次判斷侄子結點、父結點是否可以補充被刪除的黑色，整體思想就是將刪除一個黑色結點造成的影響侷限在子樹內處理。
小結
當然實現過程中調試也佔了很大一部分，我使用了兩項方法幫助調試：
- 由於插入多個結點時，無法確定是處理哪個結點時出了問題，於是我給紅黑樹類添加了 debug 屬性，用二分法設置此屬性來找到問題結點；
- 給紅黑樹類添加了 printTree() 方法，實時打印樹結構，確定代碼問題再分析；
由於紅黑樹相對其他樹實在較為複雜，只通過思考就完全理解不太現實，還需要自己去試著畫，試著實現，加油。
閱讀更多 C語言基礎 的文章
