【舌尖上的演算法】Day18 -- Transform and Conquer - AVL Tree(下)

2020 IT邦鐵人賽

Posted by Hank Lee on Friday, September 25, 2020

3 Minutes Read

Table of Contents

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

前言

昨天介紹了AVL Tree和當針對AVL Tree進行Insertion的時候可能會需要進行的Rotation,而今天會再針對Rotation這件事情提出四種情境,以及如何從一個Array變成一個AVL Tree的過程,那我們就繼續吧~


四種Insertion的使用情境

*情境一:

AVL-Tree-Scenario-1-1

如上圖所示,Node Y是Node X的右邊子節點,而這個新增的Node D成為Node Y右邊subtree的子節點,此時就需要經過Left-Rotation使之呈現Balanced Tree的狀態。

AVL-Tree-Scenario-1-2

從範例可以看到,Rotation過後,其Tree還是符合BST Tree的要求。

*情境二:

AVL-Tree-Scenario-2-1

如上圖所示,Node Y是Node X的左邊子節點,而這個新增的Node D成為Node Y左邊subtree的子節點,此時就需要經過Right-Rotation使之呈現Balanced Tree的狀態。

AVL-Tree-Scenario-2-2

這個算是情境一的反向而已,應該還算可以理解。

*情境三:

AVL-Tree-Scenario-3-1

這種情境可能就複雜一點,可以注意到Node X仍為Node Y的parent node,而Node Z為Node Y的左邊子節點,此時若將Node D加到Tree 2或Tree 3時,Node X的balance factor會超過合法範圍,因此需要進行Rotation,而此時是先針對Node Y進行Right-Rotation,將Node Z往上轉一個層級後,再針對Node X進行Left-Rotation,將Node Z變成Root Node,因此這種情境是使用Right-Left Rotation

AVL-Tree-Scenario-3-2

*情境四:

AVL-Tree-Scenario-4-1

最後一個情境是情境三的相反,所以進行Rotation的順序是先Left-RotationRight-Rotation

AVL-Tree-Scenario-4-2


AVL Tree Insertion範例

現在,我們就來針對一個隨機排列的陣列進行AVL Tree Insertion吧~

AVL Tree-example

在GIF中有幾個情況下需要進行Rotation:

  1. 新增Node 19的時候,因為Node 13的Balance factor為-2,又此情況屬於上方所提的情境一,因此進行Left Rotation
  2. 新增Node 4的時候,又是Node 13的Balance factor變成2,而此情況屬於情境二,因此進行Right Rotation
  3. 新增Node 10的時候,Node 15的Balance factor為2,此情況為情境四,因此進行Left-Right Rotation
  4. 新增Node 17時,Node 15的Balance factor為-2,為情境三,故進行Right-Left Rotation

以上即為AVL Tree Insertion的過程,希望還算可以理解。


小結

  1. AVL Tree Insertion有四種情境。
  2. Insertion過程中,若某一個Node的Balance factor不是-1, 0, 1其中之一,就需要針對這個Node進行Rotation。

預告

明天我們將會介紹另一種Tree - 2-3 Tree。


References

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