[Datastructure Cheat sheet] — AVL Tree

Balance is important :)

一棵Binary Search Tree若滿足 "左右子樹高相差不超過1"，則稱為 AVL Tree。

因為若使用Binary Search Tree，worst case有可能會形成一棵Skew Tree ，造成每次Search,Insert,Delete會得到O(N)的執行時間。

為改善此情形，AVL 能動態地維持高度之最小化(平衡化)使高度維持在O(logN)。

1. Height Balanced Binary Search Tree
2. Some theorem about AVL tree
3. AVL Tree Operation
4. Comparision with other search structure

Height Balanced Binary Search Tree

Defination

Tree T為Height Balanced Binary Search Tree(高度平衡樹)，若T不為空，則須滿足以下條件 :

• ‖ H_L-H_R ‖ ≤1，其中H_L , H_R 表示左右子樹之樹高
• T 之左右子樹也是AVL Tree

Balance factor

我們定義 H_L - H_R (左子樹高-右子樹高)為Balance factor，所以根據上述高度平衡樹的定義，可以推得 Balance factor 在AVL Tree中僅可能為 -1 , 0, 1

Theorem about AVL Tree

1.形成高度為H之AVL Tree，所需的最”少”node數為 : F(H+2)-1

// F() is Fibonacci function，H is tree height.

Prove by induction

dasda

2 .形成高度為H之AVL Tree，所需的最”多”node數為 : (2^H) -1

//為 full tree 之情形

3. Recursive form

N(H)表示為高度為H的AVL Tree的最少Node數，由AVL Tree的定義可得 :

N(H)=N(H-1)+N(H-2)+1

因為其左右子樹亦為AVL Tree，故可以保證其中一棵子樹擁有N(H-2)的最少Node數，所以另一棵樹就有N(H-1)的最少Node數(因為為高度平衡樹)，再加上Root，所以整棵樹便有

N(H-1)+N(H-2)+1 的Node數。

解出此遞迴方程式，可得 "求出高度為H的AVL Tree的最少Node數"

時間複雜度 為 Θ(Φ^H) , Φ=(1+ √5)/2。

AVL Tree’s operation

Insert

起初，和一般BST Insert一樣，將該節點放入適當位置。為了使整棵Tree保持著高度平衡的結構，所以每次做 Insert完時，都需要往root向上檢查是否存在不平衡(由每個節點balanced factor判斷，如果有-1,0,1之外的情況，表示不平衡)，若有則需要做 “ Rotation ”.

Rotation

新插入的節點有可能使某個離它最近的節點變成不平衡，”看此新點在此不平衡之處的哪個方向 “ (只看兩層子樹)，可以分成4種case來做調整 :

• LL(single rotaion)
• RR(single rotaion)
• LR(double rotaion)
• RL(double rotaion)

Rotation principle

1.中間key value往上拉，小的放左邊，大的放右邊

2.孤立之子樹依其 key value連結至適當位置

Example

Time complexity

O(logN)。因為每次Insert都有可能需要調整，而每次檢查都與高度息息相關。

Delete

如BST的delete般，如果遇刪除的節點為Leaf Node則直接刪除。否則，欲刪除的節點則為”Internal Node”，我們有兩種選擇，

從該點的 :

1. 左子樹中選擇最大的點來取代
2. 右子樹中選擇最小的點來取代

最後還需一路往上檢查，看是否有不平衡之情形，並使用Rotation矯正之.

Time complexity

O(logN)。因為每次Delete也都有可能需要調整，而每次檢查都與高度息息相關。