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

前言

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

四種Insertion的使用情境

＊情境一：

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

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

＊情境二：

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

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

＊情境三：

這種情境可能就複雜一點，可以注意到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 Ｚ變成Root Node，因此這種情境是使用Right-Left Rotation。

＊情境四：

最後一個情境是情境三的相反，所以進行Rotation的順序是先Left-Rotation再Right-Rotation。

AVL Tree Insertion範例

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

在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