2-3-4樹

2-3-4 樹在計算機科學中是階為4 的B樹。大體上同B樹一樣，2-3-4 樹是可以用做字典的一種自平衡資料結構。

基本介紹

• 中文名：2-3-4樹
• 性質：自平衡資料結構
• 方法：查找、插入和刪除
• 目的：數據存儲

它可以在O(log n)時間內查找、插入和刪除，這裡的 n 是樹中元素的數目。2-3-4 樹在多數程式語言中實現起來相對困難，因為在樹上的操作涉及大量的特殊情況。紅黑樹實現起來更簡單一些，所以可以用它來替代。

2-3-4樹

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

2-節點，就是說，它包含 1 個元素和 2 個兒子；

3-節點，就是說，它包含 2 個元素和 3 個兒子；

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

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

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

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