AVL Tree
Def
- Height Balance BST
- Root 之左右子樹高度差 1 <=> $|{H_L-H_R}|\leq1$
- 左右子樹皆為AVL Tree
Node Balance Factor
Node 的 左子樹高度-右子樹高度
Note: 只有 0,-1,1
Unbalance Situation
- LL
- LR
- RL
- RR
- 由Insert New Node之後，向上看最近一個 Balance Factor不為 0,-1,1的點在往New Node前進兩層(LL,LR,RL,RR)
操作
- Delete X
- 以BST方式刪除
- 調整(由下而上)
Theorem
- 形成高 h 之AVL Tree
$Minimal\ Node=F_{h+2}-1$