Table of Contents
前言
當在設計一個演算法的時候,倘若使用到了Tree這種資料結構,絕大部分的情況下都需要考慮到Tree的平衡問題,這樣才能確保比較好的執行效率,我們第一次接觸這個議題是在第14天介紹Binary Search Tree如何平衡(複習),BST的平衡比較像是事後補救,將原本已有的BST重新打散進行排列組合;前兩天介紹了另一種Tree-AVL Tree,AVL Tree則是透過Transform的方式,在進行Insertion的同時去做平衡的動作,因此一旦AVL Tree建構起來了,這個Tree本身也已經處於平衡狀態。
今天要再介紹另一種平衡Tree的方式 – 2-3 Trees。
2-3 Trees
2-3 Trees無疑也是一種Search Tree,但與前兩種提到BST和AVL Tree不同的地方是,2-3 Trees允許每一個Node至多存放兩個值,且可連結3個Children nodes
,因此下圖所示的兩種結構,在2-3 Trees的定義下都是合法的。
註:在右邊的3-node結構中,中間的child node所記錄的值是
介於V和X之間的值
。
2-3 Trees的Insertion範例
進行Insertion的步驟如下:
- 針對值進行大小比較。
- 將值安插至對應的Node中。
- 看看Node中的值的數量是否超過2個,若超過,則將中間值往上拉,加入或形成一個parent node。
- 若Node所連結的child node超過3個,進行分割。
透過GIF我們可以看到,當插入19時,第一個Node中的值來到了三個,因此進行分割而有了一個由三個Node組成的Tree,爾後插入4的時候,左下child node中的值來到了三個,因此再一次進行分割,形成上圖藍色的結構,最後插入14的時候,中間的child node也有了三個值,而針對這個Node進行分割,而將13移動至parent node,這時來到一個中介型態(parent node有三個值,且有四個children node),然後再進一步將這時的parent node分切,將13提出來形成一個新的parent node,而有了最後的結構。
2-3 Trees的時間複雜度
由於2-3 Trees本身還是承襲了Binary Search Tree的特性,因此無論是Search, Insert和Delete,其時間複雜度均為𝜪(㏒2 n)
。
小結
- 2-3 Trees的每一個Node可以包含最多兩個值,且每一個Node均允許有三個children node。
- 在Insertion的時候,若一個Node中新增了第三個值,就會將這個Node進行分割。
- Seach, Insert, Delete的時間複雜度均為
𝜪(㏒2 n)
。
預告
明天我們會介紹新的演算法類別-Time and Space Tradeoff。