本系列文章同步分享於個人Blog → InformisTry-HankLee

前言

目前為止已經介紹了三種類別的演算法，每一種演算法都有其有趣的地方，今天我們要介紹另一個新的類別-Transform and Conquer。

跟Transformer沒關係啊～～～～～～

Transform and Conquer

Transform的重點就是要『變形』，這種狀況大概用在改變資料形式之後，問題就可以相對容易的被解決，這個時候就是使用Transform and Conquer的時機，其實在找處理Array的資料的時候，很多時候我們都會先去排序，而這個先去排序的動作就是Transform了，因為他改變了陣列的排序，就是改變了格式，然後再針對這個已經排序的陣列進行下一步，而這種可以算是分了『兩個步驟』在做，因此其時間複雜度也是兩個加起來算。舉個例子，從一個隨機排列的陣列中尋找某一個element，用Brute Force的selection sort排序，之後用Binary Search去找，此時時間複雜度為Ｏ(n^2) + Ｏ(㏒2 n) = Ｏ(n^2)。

AVL Tree

AVL Tree是一種Binary Search Tree，而他的重點在於每一個節點(Node)都會去計算Balance factor，計算後的結果必須是-1, 0, 1，僅有這三個結果才表示這個BST是平衡的，我們可以看看下面的GIF。

Balance Factor(node x) = height(left subtree of x) - height(right subtree of x), if subtree is empty, heigh = -1.

AVL Tree的Rotation

當針對AVL Tree進行Insertion的時候，是根據BST Insertion的方式進行（忘記的可以點這裏)，但是Insertion過後，需要重新計算每一個節點的balance factor，這樣才能確認這個AVL Tree是不是處在Balanced的狀態，如果因為Insertion後某一個Node變成Unbalanced時，就會針對這個Node進行Rotation，而整個Tree也會因此『變形』而使Tree最終呈現Balanced的狀態；Rotation可以分為四種：

1. Left Rotation:

由於Node Y本身已經有兩個child node，當Node Y被轉上去成為Node X的Parent Node時，表示原先Node Y的其中一個child node會斷開連結，而這時斷開連結的Node即為Node Y左邊的child node，而這個Node會被連接到Node X的右邊child node的位置，因為這樣才會符合BST的規則。

2. Right Rotation:

由於Node Y本身已經有兩個child node，當Node Y被轉上去成為Node X的Parent Node時，表示原先Node Y的其中一個child node會斷開連結，而這時斷開連結的Node即為Node Y右邊的child node，而這個Node會被連接到Node X的左邊child node的位置，因為這樣才會符合BST的規則。

3. Left-Right Rotation:

基本上就是上面兩種Rotation的合併，所以機制相同。

4. Right-Left Rotation:

與第三點的Left-Right Rotation機制相同，只是方向相反。

小結

1. Transform and Conquer的使用時機：在改變資料形式之後，問題就可以相對容易的被解決。
2. AVL Tree也是一種BST，只是多了要計算Balance factor的動作，才能確保AVL Tree是Balanced的狀態。
3. 若經過Insertion後有某一個Node的Balance factor不是-1, 0, 1其中之一，就需要針對這個Node進行Rotation。
4. Rotation有四種方式：Left Rotation, Right Rotation, Left-Right Rotation, Right-Left Rotation。

預告

明天我們再繼續介紹AVL Tree的Insertion。

References

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