跳至內容

2-3-4樹

維基百科,自由的百科全書
2–3–4樹
類型
大O符號表示的時間複雜度
算法 平均 最差
空間
搜尋
插入
刪除

2-3-4樹(英語:2–3–4 tree)在計算機科學中是階為4的B樹

大體同B樹,2-3-4樹是一種自平衡數據結構,可用於實作字典。它可以在時間內查找、插入和刪除,這裏的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樹上的插入和刪除操作也等價於在紅黑樹中的顏色翻轉和旋轉。這使得它成為理解紅黑樹背後的邏輯的重要工具。