本頁使用了標題或全文手工轉換

2-3樹

維基百科,自由的百科全書
跳至導覽 跳至搜尋
2-3樹
類型
發明時間 1970
發明者 約翰·霍普克洛夫特
大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樹是一種樹型數據結構,內部節點(存在子節點的節點)要麼有2個孩子和1個數據元素,要麼有3個孩子和2個數據元素,葉子節點沒有孩子,並且有1個或2個數據元素。

2–3樹由約翰·霍普克洛夫特於1970年發明。[1]

2–3樹和AA樹等距同構的,意味着它們是同一種數據結構。換句話說,對於每個2–3樹,都至少有1個AA樹和它的元素排列是相同的。2–3樹是平衡樹,意味着右邊,左邊,中間的子樹的元素數量都是相同或接近的。

定義[編輯]

如果一個內部節點擁有一個數據元素、兩個子節點,則此節點為2節點

如果一個內部節點擁有兩個數據元素、三個子節點,則此節點為3節點

若且唯若以下敘述中有一條成立時,T為2–3樹:

  • T為空。即T不包含任何節點。
  • T為擁有數據元素a的2節點。若T的左孩子為L、右孩子為R,則
    • LR是等高的非空2–3樹;
    • a大於L中的所有數據元素;同時
    • a小於等於R中的所有數據元素。
  • T為擁有數據元素ab的3節點,其中a < b。若T的左孩子為L、中孩子為M、右孩子為R,則
    • LM、和R是等高的非空2–3樹;
    • a大於L中的所有數據元素,並且小於等於M中的所有數據元素;同時
    • b大於M中的所有數據元素,並且小於等於R中的所有數據元素。

連結[編輯]

參考文獻[編輯]

  1. ^ Cormen, Thomas. Introduction to Algorithms. London: The MIT Press. 2009: 504. ISBN 978-0262033848.