跳至內容

2-3樹

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書
2-3樹
類型
發明時間1970
發明者約翰·霍普克洛夫特
大O符號表示的時間複雜度
算法 平均 最差
空間
搜尋
插入
刪除

計算機科學中,2–3樹(英語:2–3 tree)是一種樹型數據結構,由約翰·霍普克洛夫特於1970年發明[1]

2–3樹中的內部節點可以有2個子節點和1個數據元素、或有3個子節點和2個數據元素,葉子節點有1至2個數據元素。

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中的所有數據元素。

操作

2–3樹的查找元素操作與二叉搜索樹的查找類似。因為節點中的數據元素都是有序的,所以查找函數可以據此進入正確的子樹進行查找,最終找到正確的節點。

進行插入操作時,可以先通過查找操作確定合適的位置,然後將數據插入對應節點。如果插入後的節點變成4節點(包含三個數據元素),則需將該節點拆分為兩個2節點,中間的數據元素進入父節點。這樣一來,該父節點也可能也會因此變成4節點,則該父節點也會拆分為兩個2節點,中間的數據元素進入該父節點的父節點,以此類推,直到修改後的父節點不需要分裂,或者被拆分的是根節點,此時中間數據元素就會單獨形成2節點,成為新的根節點。

2-3樹插入操作的三種情況

外部連結

參考文獻

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