本系列文章同步分享於個人Blog → InformisTry-HankLee
目前為止已經介紹了三種類別的演算法,每一種演算法都有其有趣的地方,今天我們要介紹另一個新的類別-Transform and Conquer。
跟Transformer沒關係啊~~~~~~
Transform的重點就是要『變形』,這種狀況大概用在改變資料形式之後,問題就可以相對容易的被解決,這個時候就是使用Transform and Conquer的時機,其實在找處理Array的資料的時候,很多時候我們都會先去排序,而這個先去排序的動作就是Transform了,因為他改變了陣列的排序,就是改變了格式,然後再針對這個已經排序的陣列進行下一步,而這種可以算是分了『兩個步驟』在做,因此其時間複雜度也是兩個加起來算。舉個例子,從一個隨機排列的陣列中尋找某一個element,用Brute Force的selection sort排序,之後用Binary Search去找,此時時間複雜度為O(n^2) + O(㏒2 n) = O(n^2)
。
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進行Insertion的時候,是根據BST Insertion的方式進行(忘記的可以點這裏),但是Insertion過後,需要重新計算每一個節點的balance factor,這樣才能確認這個AVL Tree是不是處在Balanced的狀態,如果因為Insertion後某一個Node變成Unbalanced時,就會針對這個Node進行Rotation
,而整個Tree也會因此『變形』而使Tree最終呈現Balanced的狀態;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的規則。
由於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的規則。
基本上就是上面兩種Rotation的合併,所以機制相同。
與第三點的Left-Right Rotation機制相同,只是方向相反。
-1, 0, 1
其中之一,就需要針對這個Node進行Rotation。明天我們再繼續介紹AVL Tree的Insertion。