2-3-4樹

2–3–4樹
類型	樹
用大O符號表示的時間複雜度
算法 平均 最差 空間 $O(n)$ $O(n)$ 搜尋 $O(\log n)$ $O(\log n)$ 插入 $O(\log n)$ $O(\log n)$ 刪除 $O(\log n)$ $O(\log n)$

2-3-4樹（英語：2–3–4 tree）在計算機科學中是階為4的B樹。

大體同B樹，2-3-4樹是一種自平衡數據結構，可用於實作字典。它可以在${\text{O}}(\log n)$時間內查找、插入和刪除，這裡的n是樹中元素的數目。

2-3-4樹在多數編程語言中實現起來相對困難，因為在樹上的操作涉及大量特殊情況。紅黑樹實現起來更簡單一些，所以可以用它來替代。

背景

2-3-4樹把數據存儲在叫做元素的單獨單元中。它們組合成節點，每個節點都是下列之一

• 2-節點，就是說，它包含1個元素和2個子節點，
• 3-節點，就是說，它包含2個元素和3個子節點，
• 4-節點，就是說，它包含3個元素和4個子節點。

2-節點

3-節點

4-節點

每個子節點（可能為空）都是一個子2-3-4樹。根節點是其中沒有父親的那個節點；它在遍歷樹的時候充當起點，因為從它可以到達所有的其他節點。葉子節點是有至少一個空子節點的節點。

同B樹一樣，2-3-4樹是有序的：每個元素必須大於或等於它左邊的和它的左子樹中的任何其他元素。每個子節點因此成為了由它的左和右元素界定的一個區間。

2-3-4樹是紅黑樹的一種等同，這意味着它們是等價的數據結構。換句話說，對於每個2-3-4樹，都存在着至少一個數據元素是相同次序的紅黑樹。在2-3-4樹上的插入和刪除操作也等價於在紅黑樹中的顏色翻轉和旋轉。這使得它成為理解紅黑樹背後的邏輯的重要工具。