# AVL Tree

###### tags: `MIT` `面試準備`

我們從 Binary Search Tree 開始，一般的BST有這個constraint:
> 在該節點左邊的子樹所有node的value都小於自身value
> 在該節點右邊的子樹所有node的value都大於自身value

然而我們的tree在建立的過程中，因為insert的順序會影響到樹的長相
我們希望看到的是balanced BST:

digraph graphname { 
		4 -> 2; 
		2 -> 1;
        2 -> 3;
		4 -> 6;
        6 -> 5;
        6 -> 7;
	}

以下就是一個unbalanced的極端案例，這樣的樹會讓搜尋的時間拉長

digraph graphname { 
		1 -> 2; 
		2 -> 3;
		3 -> 4;
	}

為了製造出平衡的樹，有很多作法:

## AVL tree

我們接著定義一些名詞:

**height of node** : length of longest path from node to leaf
**height of tree** : height of root

有時候我們會直覺地覺得tree的高度就是 $log_2 n$ ，其實不然，要看它是否為平衡樹

<br>

**Requirment of AVL Tree** : height of left and right children of **each** node differ by at roost $\pm1$

也就是說每個節點的左右子結點的高不能差超過1: $|h_r-h_l| \leq 1$

digraph graphname { 
        {
        left [shape=triangle]
        right [shape=triangle]
        }
		root -> left; 
		root -> right;

	}

一個高是 $h$ 的BST能容納的節點是 $2^h$ 個，那AVL Tree是否有很極端的例子讓他可能長的很差嗎? 我們試著分析AVL tree的容量:

$N_h$ = **min number of nodes in an AVL tree of height h**

我們可以用遞迴式去描述:

> $N_h = 1 + N_{h-1} + N_{h-2}$

長得很像Fibonacci Sequence，根據這個思路，可以做出不等式

> $N_h > F_h \approx 1.440 \times log_h$

其實也可以很簡單的做下界線:

> $N_h \geq 1 + N_{h-2} + N_{h-2} \approx 2N_{h-2}$

> $h \geq 2logN$

### **AVL Insertion**

做新節點的插入其實和一般的 BST 無異，但必須多做 balance 讓所有 node 符合 height constraint。

調整 AVL tree 的方式有兩種 rotation:

**1. Left Rotation**


**2. Right Rotation**


而我們做 insertion 時實際上會遇到 unbalanced 的情形有四個：


我們以 LR 做例子： LR 會先轉換 LL 再做一次 Right Rotation


其餘的三種情況也都是以此類推

| Function | 時間複雜度 |
| -------- | -------- |
| Search | $O(log_2n)$ |
| Insert | $O(log_2n)$ |
| Delete | $O(log_2n)$ |

MIT 課程中也提到， AVL tree 會是以下 abstract 的實做資料結構 (也可以用 heap)

Abstract Data Type:
- insert / delete
- min
- successor / pred

### 延伸閱讀

Red-Black Tree: [link](http://alrightchiu.github.io/SecondRound/red-black-tree-insertxin-zeng-zi-liao-yu-fixupxiu-zheng.html)