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.