2-3-4 樹
本頁介紹 2-3-4 樹。在計算機科學中，2–3–4 樹（也稱為 2–4 樹）是一種自平衡的樹，所有的葉子節點都位於同一深度。2-3-4 樹是 4 階 B 樹，與一般的 B 樹一樣，2-3-4 樹可以實現在 \(O(\log n)\) 時間內進行搜索、插入和刪除操作。
2-3-4 樹是對 2-3 樹的概念擴展，包括了 4 節點的使用。
2–3–4 樹與紅黑樹是等價的。對於每個 2–3–4 樹，恰好存在一個相同順序的紅黑樹。此外，對 2–3–4 樹進行插入和刪除操作，導致節點擴展、分裂和合並的過程與紅黑樹中的顏色翻轉和旋轉等效。2–3–4 樹的操作中涉及大量特殊情況，在大多數編程語言中的實現可能會比較困難。而紅黑樹的實現較為簡單，因此更常被使用。
定義
2-3-4 樹的節點分為三種，2 節點，3 節點和 4 節點，分別包含一個、兩個或三個數據元素。
性質
- 每個節點（葉節點或內部節點）可以是 2 節點、3 節點或 4 節點，分別包含一個、兩個或三個數據元素。
- 所有的葉子節點都處於同一深度（最底層）。
- 所有數據都有序存儲。
- 在 2-3-4 樹的最壞情況下高度是 \(\log N\)，在最好的情況下高度是 \(1/2 \log N\)（所有節點都是 4 節點）。
操作
由於 2-3-4 樹上的元素是按一定順序存儲的，所以查找與二叉搜索樹類似。插入和刪除都會保持平衡性，即葉節點的深度相同。
插入
2-3-4 樹的插入只會發生在葉節點，而不會發生在內部節點。在葉節點上插入一個值，會讓 2 節點變成 3 節點，3 節點變成 4 節點，而 4 節點就沒有空間了。為了解決這個問題，這裏有兩種思路。
- 自底向上，從 4 葉節點開始分裂（上溢），如果分裂後其父節點也是 4 節點，繼續向上分裂，直到到達根節點。如果根節點也是 4 節點，分裂後樹的高度 + 1。
- 自頂向下，從根節點到插入所在的葉節點路徑上，遇到 4 節點就將其分裂。
本文采用自底向上，將插入操作分為兩部分，首先根據搜索樹的性質在葉節點的位置插入，形成暫時的 5 節點，然後根據插入節點及相關節點的狀態進行平衡的維護。
下面是 2-3-4 樹插入的例子。
首先插入值 \(25\)。從根節點 \((10,20)\) 開始查找，找到包括 \(25\) 的區間 \((20,\infty)\)，進入右子節點 \((22,24,29)\)。
由於節點 \(（22, 24, 29）\) 是一個 4 節點，先將 \(25\) 插入形成暫時的 5 節點。
由於 \(（22, 24, 25, 29）\) 超出了 4 節點，需要將第二個元素上溢。即將 \(24\) 與父節點合併形成 \((10,20,24)\)。
然後插入 \(30\)。
插入 \(31\)。形成 5 節點 \((25,29,30,31)\)。
第二個元素 \(29\) 上溢，發現父節點也形成 5 節點 \((10,20,24,29)\)。
5 節點 \((10,20,24,29)\) 中第二個元素 \(20\) 繼續上溢，最終調整完成。
刪除
從 2-3-4 樹中刪除一個元素需要根據待刪除元素的位置分情況討論。刪除操作只發生在葉節點上。下面介紹從 2–3–4 樹中刪除一個元素的過程：
- 查找需要刪除某個元素的節點。
- 如果節點是葉子節點（3 節點或 4 節點），則從該節點中刪除所需的值，並將數據元素減少 1。
- 如果節點不是葉子節點，則：
- 查找該節點的後繼節點。節點的後繼是其中大於它的最小元素或小於它的最大元素。
- 用後繼節點交換當前節點，並在葉子中刪除該節點。
但如果葉節點是一個 2 節點，刪除該節點可能會導致下溢（underflow)。為了避免這種情況，我們在從上到下移動到要刪除的節點的路徑上遇到 2 節點時，會先執行以下調整操作，使找到的葉子節點不是 2 節點。這樣，在之後的交換和刪除後，不會出現一個空的葉節點。
Case 1
如果當前節點的兄弟節點之一是 3 節點或 4 節點，則將當前節點與那個兄弟節點一起進行以下旋轉操作：
- 選擇一個與當前節點最接近的鍵值的兄弟節點。
- 將該兄弟節點的鍵值上移到當前節點的父節點中，使父節點變成一個 3 節點。
- 原來兄弟節點的孩子現在成為當前節點的孩子。
下圖在 2-3-4 樹中刪除元素 \(10\)。
Case 2
如果父節點是 2 節點並且兄弟節點也是 2 節點。在這種情況下，父節點是根節點。所以將這三個 2 節點合併成一個新的 4 節點，並縮短樹的高度。
下圖在 2-3-4 樹中刪除元素 \(50\)。
Case 3
如果兄弟節點是 2 節點，但父節點是 3 節點或 4 節點：
- 將相鄰的兄弟節點和俯視兩個兄弟節點的父鍵融合成一個 4 節點（下溢）。
- 將兄弟節點的子節點移到該節點。
下圖在 2-3-4 樹中刪除元素 \(50\)。
與紅黑樹的關係
2-3-4 樹和紅黑樹是同構的，任意一棵紅黑樹都唯一對應一棵 2-3-4 樹。在 2-3-4 樹上的插入和刪除操作導致節點的擴展、分裂和合並，相當於紅黑樹中的變色和旋轉。下圖是 2-3-4 樹的 2 節點、3 節點和 4 節點對應的紅黑樹節點。注意到 2-3-4 樹的 3 節點對應紅黑樹中紅色節點左偏和右偏兩種情況，所以一棵紅黑樹可能對應多棵 2-3-4 樹。
下圖是一棵紅黑樹和與之對應的 2-3-4 樹。將紅黑樹中的紅色節點上移到父節點的左右兩側，形成一個 B 樹節點，就可以得到與之對應的 2-3-4 樹。可以發現，紅黑樹的節點數等於 2-3-4 樹的節點個數。
下面用上圖對比紅黑樹和 2-3-4 樹的插入和刪除操作。
紅黑樹的插入
下面根據插入節點，父節點以及祖父節點的情況將插入分為以下 3 類情況，每類情況均包含 4 種。
- 插入節點的父節點是黑色，可以直接插入，無需調整。
- 插入節點的叔父節點但不為紅色（不存在或者為黑色），需要進行變色 + 旋轉（單旋或雙旋）。
- 插入節點的叔父節點是紅色，需要進行變色並將祖父節點上溢，遞歸處理。
Case 1
插入節點的父節點是黑色，可以直接插入，不需要進行調整。這種情況插入新節點後形成 2-3-4 樹的 3 節點或 4 節點。如下圖插入 \(9、22、28、40\) 都屬於這種情況。
Case 2
插入節點的父節點是紅色，祖父節點是黑色，叔父節點不為紅色（不存在或者為黑色）。這種情況插入後形成 2-3-4 樹的 4 節點，但是違反紅黑樹的性質（出現兩個連續紅色節點）。按照父節點和祖父節點的位置可以分成 LL、RR、LR、RL 四種情況。其中 LL 和 RR 需要進行一次染色和單旋（左旋或右旋）。LR 和 RL 則需要進行染色和雙旋。
如下圖插入節點 \(11、13、16、19\) 都屬於這種情況。其中插入節點 \(13\) 和 \(16\) 為 RR 型和 LL 型，\(11\) 和 \(19\) 為 RL 型和 LR 型。
以插入節點 \(13\) 舉例，按照 2-3-4 樹的插入方式中應將 \(13\) 插入 \(12\) 的右側，但出現兩個連續紅色節點 \(12\) 和 \(13\)，因此需要先將父節點 \(12\) 染成黑色，將祖父節點 \(10\) 染成紅色並左旋祖父節點 \(10\)，調整後滿足紅黑樹的性質。調整後的結果如下圖所示。
Case 3
插入節點的父節點和叔父節點是紅色，祖父節點是黑色。這種情況其實是形成了一個 2-3-4 樹的 5 節點。需要將父節點和叔父節點染為黑色，將祖父節點染為紅色並上溢到父節點，然後遞歸處理。如下圖插入節點 1、3、5、7 都屬於這種情況。
下圖以插入節點 \(1\) 為例，形成的 5 節點為 \((1,2,4,6)\)。將父節點 \(2\) 和叔父節點 \(6\) 染為黑色，將祖父節點 \(4\) 染為紅色並上溢。可以發現節點 \(4\) 上溢後仍需要按照 Case 3 處理，此處省略具體步驟。其他三種情況的調整方式與之類似。
紅黑樹的刪除
紅黑樹內部節點的刪除，會轉換為其前驅或後繼節點的刪除。所以紅黑樹節點的刪除，最終都會轉換為 2-3-4 樹中最後一行節點的刪除（對應紅黑樹最後兩行節點的刪除）。
Case 1
待刪除節點為紅色，可以直接刪除，因為刪除最後一層的紅色節點不會違反紅黑樹的性質。
Case 2
待刪除的節點為黑色，需要進行調整才能滿足紅黑樹的黑平衡。其中黑色節點可以分為以下三種情況。
Case 2.1
待刪除的黑色節點有兩個紅色子節點的黑色節點（2-3-4 樹的 4 節點）。刪除該節點會轉換為其前驅或後繼節點的刪除，所以此處不做考慮。
Case 2.2
待刪除的黑色節點有一個紅色子節點的黑色節點（2-3-4 樹的 3 節點）。需要用唯一的紅色子節點替代被刪除的節點，並將該紅色子節點染為黑色。如下圖刪除節點 \(10\)，需要用唯一的紅色子節點 \(12\) 替代，並將其染為黑色。
調整完的結果如下圖所示。
Case 2.3
待刪除的黑色節點為黑色葉節點（對應 2-3-4 樹刪除葉子 2 節點導致下溢的情況），需要進行調整，具體可以分為以下三種情況。
Case 2.3.1
待刪除節點為根節點，當前只有一個節點，可以直接刪除。
Case 2.3.2
待刪除節點的兄弟節點為黑色。
-
兄弟節點有紅色子節點（分為三種，有一個左紅色子節點，或有一個右紅色子節點，或兩個紅色子節點），需要借用兄弟節點的子節點進行調整。下圖以刪除節點 \(36\)，其有一個紅色的左子節點 \(18\) 為例，這種情況需要進行旋轉和染色。觀察到待刪除節點的父節點、兄弟節點、兄弟節點的子節點的關係為 LL 型，只需要右旋一次，並將中間節點 \(20\) 染為紅色，兩個子節點 \(18\) 和 \(25\) 染為黑色。
下圖是調整後的結果。其他兩種情況，有一個紅色的右子節點的情況需要進行雙旋和染色，有兩個紅色的子節點的情況可以任選其中一個進行調整。
-
兄弟節點沒有紅色子節點，需要將兄弟節點染紅，父節點染黑。如果父節點原來就為黑色，需要把父節點當作已被刪除的節點處理，然後向上遞歸調整。
如下圖所示，待刪除節點 \(36\)，其兄弟節點 \(20\) 沒有紅色子節點，父節點 \(25\) 為紅色，需要將父節點下溢（對應 2-3-4 樹中刪除葉子 2 節點將父節點下溢的情況，在紅黑樹中無需操作）並染黑，將 \(20\) 染紅。
下圖是待刪除節點的父節點原來就為黑色的情況。調整後由於父節點 \(25\) 發生了下溢，需要把父節點 \(25\) 當作一個刪除的節點向上遞歸調整。
Case 2.3.3
待刪除節點的兄弟節點為紅色，需要轉變為兄弟節點為黑色的情況進行處理。具體操作是將父節點旋轉，將兄弟節點染黑，父節點染紅，然後轉換成待刪除節點的兄弟節點為黑色的情況繼續進行調整。如下圖所示，待刪除待刪除節點 \(36\)，其兄弟節點 \(15\) 為紅色，根據位置關係可知需要將父節點右旋，並將父節點染紅，兄弟節點染黑，轉換成待刪除節點的兄弟節點為黑色的情況。
參考資料
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用