2-3樹
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
2-3樹 | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
類型 | 樹 | ||||||||||||||||||||
發明時間 | 1970 | ||||||||||||||||||||
發明者 | 約翰·霍普克洛夫特 | ||||||||||||||||||||
用大O符號表示的時間複雜度 | |||||||||||||||||||||
|
電腦科學中,2–3樹(英語:2–3 tree)是一種樹型資料結構,由約翰·霍普克洛夫特於1970年發明[1]。
2–3樹中的內部節點可以有2個子節點和1個資料元素、或有3個子節點和2個資料元素,葉子節點有1至2個資料元素。
-
2節點
-
3節點
2–3樹和AA樹是等距同構的,意味著它們是同一種資料結構。換句話說,對於每個2–3樹,都至少存在1種AA樹和它的元素排列是相同的。2–3樹是平衡樹,意味著右邊,左邊,中間的子樹的元素數量都是相同或接近的。
定義
如果一個內部節點擁有一個資料元素、兩個子節點,則此節點為2節點。
如果一個內部節點擁有兩個資料元素、三個子節點,則此節點為3節點。
若且唯若以下敘述中有一條成立時,T為2–3樹:
- T為空。即T不包含任何節點。
- T為擁有資料元素a的2節點。若T的左子節點為L、右子節點為R,則:
- L和R是等高的2–3樹;
- a大於L中的所有資料元素;同時
- a小於等於R中的所有資料元素。
- T為擁有資料元素a和b的3節點,其中a < b。若T的左子節點為L、中子節點為M、右子節點為R,則:
- L、M、和R是等高的2–3樹;
- a大於L中的所有資料元素,並且小於等於M中的所有資料元素;同時
- b大於M中的所有資料元素,並且小於等於R中的所有資料元素。
操作
2–3樹的尋找元素操作與二元搜尋樹的尋找類似。因為節點中的資料元素都是有序的,所以尋找函式可以據此進入正確的子樹進行尋找,最終找到正確的節點。
進行插入操作時,可以先通過尋找操作確定合適的位置,然後將資料插入對應節點。如果插入後的節點變成4節點(包含三個資料元素),則需將該節點拆分為兩個2節點,中間的資料元素進入父節點。這樣一來,該父節點也可能也會因此變成4節點,則該父節點也會拆分為兩個2節點,中間的資料元素進入該父節點的父節點,以此類推,直到修改後的父節點不需要分裂,或者被拆分的是根節點,此時中間資料元素就會單獨形成2節點,成為新的根節點。
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/4/44/2-3_insertion.svg/800px-2-3_insertion.svg.png)
外部連結
- 2–3 Trees Complete Description
- 2–3 Tree Java Applet
- 2–3 Tree In-depth description(頁面存檔備份,存於網際網路檔案館)
- 2–3 Tree in F#(頁面存檔備份,存於網際網路檔案館)
- 2–3 Tree in Python(頁面存檔備份,存於網際網路檔案館)
參考文獻
- ^ Cormen, Thomas. Introduction to Algorithms. London: The MIT Press. 2009: 504. ISBN 978-0262033848.
|
|