【舌尖上的演算法】Day19 -- Transform and Conquer - 2-3 Trees

2020 IT邦鐵人賽

Posted by Hank Lee on Saturday, September 26, 2020

3 Minutes Read

Table of Contents

本系列文章同步分享於IT邦幫忙第12屆鐵人賽

前言

當在設計一個演算法的時候,倘若使用到了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的定義下都是合法的。

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 Tree-Insertion


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