# AVL Tree
是一種 Binary Search 的實作方式，在 insert 或 delete 資料的階段會平衡樹的結構，讓BST不會過度傾斜，其利用計算 Balance Factor(BF) 去比較目前BST是否有傾斜，如有傾斜並旋轉

## Balance Factor
BF(T) < -1: 右邊的subtree比較重，將右邊的節點往左邊移動
-1 < BF(T) < 1: 目前Tree平衡
BF(T) > 1: 左邊的subtree比較重，將左邊的節點往右邊移動

#### 先計算節點的高度
沒有子節點時高度為-1，左右都有子節點時取最大高度，最後再+1


#### 計算 Balance Factor(BF)
BF = 左邊節點-右邊節點
)

## 平衡樹節點

#### Left Rotation
將B節點左邊設為A的右節點，將A節點設為B的左節點


#### Right Rotation
將B節點右邊設為A的左節點，將A節點設為B的右節點


### 旋轉類型
共有四種旋轉類型，都是上述方法的變化組合

#### LL
對A做 Right Rotation
#### LR
先對B做 Left Rotation
再對A做 Right Rotation

#### RR
對A做 Left Rotation

#### RL
先對B做 Right Rotation

再對A做 Left Rotation

## 參考
* https://josephjsf2.github.io/data/structure/and/algorithm/2019/06/22/avl-tree.html
* https://hackmd.io/@sysprog/linux-rbtree

## Thank you! :dash:

You can find me on

- GitHub: https://github.com/shaung08
- Email: [e-mail]