iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 17
0

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

前言

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

跟Transformer沒關係啊~~~~~~


Transform and Conquer

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

AVL Tree -2


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:

AVL Tree-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:

AVL Tree-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:

AVL Tree-Left-Right Rotation

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

4. Right-Left Rotation:

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

上一篇
Day16 -- Divide and Conquer - Quick Sort
下一篇
Day18 -- Transform and Conquer - AVL Tree(下)
系列文
舌尖上的演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言