Table of Contents
前言
目前為止已經介紹了三種類別的演算法,每一種演算法都有其有趣的地方,今天我們要介紹另一個新的類別-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機制相同,只是方向相反。
小結
- Transform and Conquer的使用時機:在改變資料形式之後,問題就可以相對容易的被解決。
- AVL Tree也是一種BST,只是多了要計算Balance factor的動作,才能確保AVL Tree是Balanced的狀態。
- 若經過Insertion後有某一個Node的Balance factor不是
-1, 0, 1
其中之一,就需要針對這個Node進行Rotation。 - Rotation有四種方式:Left Rotation, Right Rotation, Left-Right Rotation, Right-Left Rotation。
預告
明天我們再繼續介紹AVL Tree的Insertion。