---
title: 'AVL Tree'
disqus: hackmd
---
[TOC]

## AVL Tree

* 在 BST 裡最佳時間為 $O(log_2n)$ 最差時間為 $O(n)$ 相距甚遠，
此章所探討正是為了使 $BST$ 能夠穩定的成長方法
使用高度平衡 $(Height\ Balanced)$： 使得最差情況下仍然是 $O(log_2n)$

* $BST\ +\ Heighted\ Balanced\ = AVL\ Tree$

**Def：**
1. 是一顆 $Height\ Balanced\ Binary\ Search\ Tree$ ( 高度平衡二元搜尋樹 )
2. 任意 $Node$ 之 $Left\ Subtree$ 與 $Right\ Subtree$ 高度差：左子樹高度 $-$ 右子樹高度為 $-1,0,1$，也就是說 $|H_L-H_R|\leq 1$
3. 因為是 $BST$ 所以記得以 $Root$ 為基準的值，大小會在不同邊


---

### Unbalanced Condition - 未平衡狀況

* 若出現以下四種情況需要調整，L 及 R 代表 Left、Right Child

1. LL

3. LR

5. RL

7. RR

<br><br><br>

* 其實這四種情況大致可以分類成兩種 (個人分類)，分別是 **LR LL 及 RL RR**
<br>
* LR 需先 **向左單旋轉 ( Single Right Rotation )** 得 LL

* RL 需要 **向左單旋轉 ( Single Left Rotation )** 得 RR

* 而 LL 及 RR 在旋轉一次即可達到我們想要的平衡結果

<br><br>
* 整個關係就會像這樣

* 方向下面會開始討論還不用急著弄懂，記得我們的目標就是這個就行了

digraph graphname{
  1[label=""]
  2[label=""]
  3[label=""]
  1->2
  1->3
}

---

### Rotation - 旋轉
* Single Rotation 單旋轉：將 LR 及 RL 下半旋轉


* Rotation 旋轉：將 LL 及 RR 整個節點旋轉


<br><br><br>
#### ==向左單旋轉 Single Left Rotation==
* 如下圖所示 ( 數字為 Index，方便理解用 )
* 將 2 替換到 4
* 將 3 替換到 2

這兩個動作一起就會像是一個左旋轉，
而這樣的動作在值域 (值的大小區分) 的判斷也是符合 Binary Tree 的定義

<br><br><br>
* 我們把 Index 換成 Data 來看

* 40 比 30 大，所以當 40 變成 Parent 的時候 30 自然是他的 Left Child ( 小於30 )

<br><br><br>
* 你要考慮的不僅僅如此而已，這兩個 Node 彼此都有可能自帶 Child


<br><br><br>
* 所幸我們只需要稍微理解一下 C Node 的關係，其餘的都挺直覺的

<br><br><br>

* **A Node** 的 Left Child 很直覺的跟著下去，並保持在左側
<br><br><br>
* **B Node** 的 Right Child 很直覺的跟著上去，並保持在右側
<br><br><br>

* **C Node** 我們代入值進去觀察，看起來可以放在 70 的 Right Child以及 90 的 Left Child
但是謹記著他們的 Parent 80，若放在 90 的 Left Child 代表著 75 > 80 ，所以我們只剩下 70 的 Right Child 可放

<br><br><br>
* 如圖所示
<br><br><br>
* 回過頭在看一次，所以當 B 有 Left Child 時，單旋轉完後它會變成 A 的 Right Child，Node C 程式部分即為 `A Node->RightChild = C Node`，其他的就照著直覺改動即可

---

#### ==向右單旋轉 Single Right Rotation==
* 由於是 **向左單旋轉** 的鏡像操作，細節不再贅述
* 如下圖所示 ( 數字為 Index )
* 將 2 替換到 4
* 將 3 替換到 2

這兩個動作一起就會像是一個右旋轉
<br><br><br>
* 我們把 Index 換成 Data 來看
<br><br><br>
* 同樣需理解一下 C Node 的關係
<br><br><br>
* 如圖所示
<br><br><br>
* 回過頭看，程式部分為 `A Node->LeftChild = C Node`
<br><br><br>

---

#### ==向左旋轉 Left Rotation==

* 旋轉的想法很簡單，如圖所示 ( 數字為 Index )
<br><br><br>
* 代入值進去探討
<br><br><br>
* 同樣考慮 Child 的關係
<br><br><br>
* 代入值進去
<br><br><br>
* 將 Child 放置正確位置，發現需要特別更動的，是原來 600 的 Left Child 550
<br><br><br>
* 回頭來看，關於 C Node 程式部分 `A Node->RightChild = C Node`


---

#### ==向右旋轉 Right Rotation==

* 同樣為 **向左旋轉** 的鏡像操作，如圖所示 ( 數字為 Index )

<br><br><br>
* 代入值進去探討


<br><br><br>
* 同樣考慮 Child 的關係


<br><br><br>
* 代入值進去，特別更動的是原來 50 的 Right Child 70

<br><br><br>

* 回頭來看，關於 C Node 程式部分 `A Node->LeftChild = C Node`


:::warning
旋轉的部分請熟悉，之後 Red-Black Tree 的 **Node調整** 就是倚靠旋轉而來
:::

---

### 形成高為 n 的 AVL Tree 所需最少 Nodes

* 使用費式數列，其值恰為 $F_{n+2}-1$


* 例：高度為 5 之 AVL Tree = $F_{5+2}-1=13-1=12$

:::success
證明：數學歸納法
:::

###### tags: `Data Structure`