本系列文章同步分享於個人Blog → InformisTry-HankLee
當在設計一個演算法的時候,倘若使用到了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無疑也是一種Search Tree,但與前兩種提到BST和AVL Tree不同的地方是,2-3 Trees允許每一個Node至多存放兩個值,且可連結3個Children nodes
,因此下圖所示的兩種結構,在2-3 Trees的定義下都是合法的。
註:在右邊的3-node結構中,中間的child node所記錄的值是
介於V和X之間的值
。
進行Insertion的步驟如下:
透過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本身還是承襲了Binary Search Tree的特性,因此無論是Search, Insert和Delete,其時間複雜度均為?(㏒2 n)
。
?(㏒2 n)
。明天我們會介紹新的演算法類別-Time and Space Tradeoff。