---
# System prepended metadata
title: AVL Tree
tags: [Data Structure]
---
---
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
* 其實這四種情況大致可以分類成兩種 (個人分類)，分別是 **LR LL 及 RL RR**
* LR 需先 **向左單旋轉 ( Single Right Rotation )** 得 LL
* RL 需要 **向左單旋轉 ( Single Left Rotation )** 得 RR
* 而 LL 及 RR 在旋轉一次即可達到我們想要的平衡結果
* 整個關係就會像這樣
* 方向下面會開始討論還不用急著弄懂，記得我們的目標就是這個就行了
```graphviz
digraph graphname{
1[label=""]
2[label=""]
3[label=""]
1->2
1->3
}
```
---
### Rotation - 旋轉
* Single Rotation 單旋轉：將 LR 及 RL 下半旋轉
* Rotation 旋轉：將 LL 及 RR 整個節點旋轉
#### ==向左單旋轉 Single Left Rotation==
* 如下圖所示 ( 數字為 Index，方便理解用 )
* 將 2 替換到 4
* 將 3 替換到 2
這兩個動作一起就會像是一個左旋轉，
而這樣的動作在值域 (值的大小區分) 的判斷也是符合 Binary Tree 的定義
* 我們把 Index 換成 Data 來看
* 40 比 30 大，所以當 40 變成 Parent 的時候 30 自然是他的 Left Child ( 小於30 )
* 你要考慮的不僅僅如此而已，這兩個 Node 彼此都有可能自帶 Child
* 所幸我們只需要稍微理解一下 C Node 的關係，其餘的都挺直覺的
* **A Node** 的 Left Child 很直覺的跟著下去，並保持在左側
* **B Node** 的 Right Child 很直覺的跟著上去，並保持在右側
* **C Node** 我們代入值進去觀察，看起來可以放在 70 的 Right Child以及 90 的 Left Child
但是謹記著他們的 Parent 80，若放在 90 的 Left Child 代表著 75 > 80 ，所以我們只剩下 70 的 Right Child 可放
* 如圖所示
* 回過頭在看一次，所以當 B 有 Left Child 時，單旋轉完後它會變成 A 的 Right Child，Node C 程式部分即為 `A Node->RightChild = C Node`，其他的就照著直覺改動即可
---
#### ==向右單旋轉 Single Right Rotation==
* 由於是 **向左單旋轉** 的鏡像操作，細節不再贅述
* 如下圖所示 ( 數字為 Index )
* 將 2 替換到 4
* 將 3 替換到 2
這兩個動作一起就會像是一個右旋轉
* 我們把 Index 換成 Data 來看
* 同樣需理解一下 C Node 的關係
* 如圖所示
* 回過頭看，程式部分為 `A Node->LeftChild = C Node`
---
#### ==向左旋轉 Left Rotation==
* 旋轉的想法很簡單，如圖所示 ( 數字為 Index )
* 代入值進去探討
* 同樣考慮 Child 的關係
* 代入值進去
* 將 Child 放置正確位置，發現需要特別更動的，是原來 600 的 Left Child 550
* 回頭來看，關於 C Node 程式部分 `A Node->RightChild = C Node`
---
#### ==向右旋轉 Right Rotation==
* 同樣為 **向左旋轉** 的鏡像操作，如圖所示 ( 數字為 Index )
* 代入值進去探討
* 同樣考慮 Child 的關係
* 代入值進去，特別更動的是原來 50 的 Right Child 70
* 回頭來看，關於 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`