Table of Contents
前言
昨天介紹了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：
- 新增
Node 19的時候，因為Node 13的Balance factor為-2，又此情況屬於上方所提的情境一，因此進行Left Rotation。 - 新增
Node 4的時候，又是Node 13的Balance factor變成2，而此情況屬於情境二，因此進行Right Rotation。 - 新增
Node 10的時候，Node 15的Balance factor為2，此情況為情境四，因此進行Left-Right Rotation。 - 新增
Node 17時，Node 15的Balance factor為-2，為情境三，故進行Right-Left Rotation。
以上即為AVL Tree Insertion的過程，希望還算可以理解。
小結
- AVL Tree Insertion有四種情境。
- Insertion過程中，若某一個Node的Balance factor不是
-1, 0, 1其中之一，就需要針對這個Node進行Rotation。
預告
明天我們將會介紹另一種Tree - 2-3 Tree。