本系列文章同步分享於個人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

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的步驟如下：

1. 針對值進行大小比較。
2. 將值安插至對應的Node中。
3. 看看Node中的值的數量是否超過2個，若超過，則將中間值往上拉，加入或形成一個parent node。
4. 若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)。

小結

1. 2-3 Trees的每一個Node可以包含最多兩個值，且每一個Node均允許有三個children node。
2. 在Insertion的時候，若一個Node中新增了第三個值，就會將這個Node進行分割。
3. Seach, Insert, Delete的時間複雜度均為?(㏒2 n)。

預告

明天我們會介紹新的演算法類別-Time and Space Tradeoff。

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin