通過2-3-4樹了解

紅黑樹是非常經典且實用的資料結構，本文通過它的等同——2-3-4樹，避開顔色因素的影響，以一種更簡單的方式介紹了紅黑樹插入删除操作的實作。文章附帶 PHP 和 Java 版紅黑樹源碼。

前言

紅黑樹是資料結構中比較複雜的一種，最近與它交集頗多，于是花了一周的空閑時間跟它死磕，終于弄明白并實作了紅黑樹。寫文總結一下，希望能給試圖了解紅黑樹的同學一些靈感，也讓我能記得更深刻。

在研究紅黑樹時吃了不少苦頭，原因有二：

• 紅黑樹的插入和删除非常複雜，很多人并沒有了解或完全實作，或實作了的沒有任何注釋，讓人很難參考；
• 網絡上紅黑樹的了解方式較為單一，一般是

  雙黑、caseN

  法，而插入和删除的情況很多，每種都有對應的處理方式，如果死記硬背的話，再過一段時間再回憶各種情況可能就一頭霧水了。

網絡上講紅黑樹的實作多來源于《算法導論》一書，直接講紅黑樹的實作，需要處理顔色和高度兩種屬性限制，比較晦澀。本文通過紅黑樹的等同—— 2-3-4樹，避開顔色屬性限制，也弱化了高度的影響，以另一種方式去了解紅黑樹，雖然并不能完全降低它的複雜度，但自認為較之普遍實作，更易記一些。

文章最前面先放上紅黑樹的實作源碼，代碼在 Github 上，一開始實作時使用我最熟練的 PHP，後續添加了 Java 版，代碼都可以直接運作。源碼連結：

GitHub-枕邊書-RBTree

，歡迎

star

。

文章歡迎轉載，請注明出處：http://www.cnblogs.com/zhenbianshu/p/8185345.html。

紅黑樹

定義

紅黑樹是一種結點帶有顔色屬性的二叉查找樹，但它在二叉查找樹之外，還有以下要求：

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

下圖就是一個典型的紅黑樹：

但實作上我省略了其中的 Nil 結點，一般如下圖，大家了解時也可以忽略它們。

優勢和用途

我們知道二叉查找樹在不停地添加或删除結點後，可能會導緻結點情況如下：

這種情況下，二叉查找樹的查找效率最壞會降低為

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樹（來自維基百科）：

2-3-4樹的查詢操作像普通的二叉搜尋樹一樣，非常簡單，但由于其結點元素數不确定，在一些程式設計語言中實作起來并不友善，實作一般使用它的等同——紅黑樹。

對應紅黑樹

至于為什麼說紅黑樹是 2-3-4樹的一種等同呢，這是因為 2-3-4樹的每一個結點都對應紅黑樹的一種結構，是以每一棵 2-3-4樹也都對應一棵紅黑樹，下圖是 2-3-4樹不同結點與紅黑樹子樹的對應。

而上文中的 2-3-4樹也可以轉換成一棵紅黑樹：

由紅黑樹的性質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 結點；

如上圖所示，雖然向紅黑樹中插入了一個新結點，但由于旋轉和變色，子樹的高度保持不變。

删除結點

紅黑樹的删除要比插入要複雜一些，我們還是類比 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()

  方法，實時列印樹結構，确定代碼問題再分析；

由于紅黑樹相對其他樹實在較為複雜，隻通過思考就完全了解不太現實，還需要自己去試着畫，試着實作，我畫了 5 張 A4 紙的正反面才算了解了紅黑樹，即便如此，在寫這篇文章時還發現了代碼中的可優化點。

而且代碼實作比畫圖還略複雜，理論中的一個

旋轉

就包含了

左旋/右旋/先左旋再右旋/先右旋再左旋

幾種情況，雖然有一定規律，還是自己實作一下印象最深刻。

關于本文有什麼問題可以在下面留言交流，如果您覺得本文對您有幫助，可以點選下面的

推薦

支援一下我，部落格一直在更新，歡迎

關注