# [資料結構] CH8. AVL Trees

## 簡介
* AVL Trees是屬於Binary Search Trees的一種，也就是說，它必須符合Binary Search Trees的所有特性。
* 除了Binary Search Trees的特性外，AVL還必須符合以下特性：

    * 因為上述特性，AVL Trees是一種**平衡樹**。
* 由於整個樹不會長歪，在搜尋時的速度會更快。
* 一個AVL的例子：

digraph AVL{
1 [label="45"];
2 [label="20"];
3 [label="66"];
4 [label="18"];
5 [label="22"];
6 [label="50"];
7 [label="67"];
8 [label="99"];

1 -> 2
1 -> 3
2 -> 4
2 -> 5
3 -> 6
3 -> 7
7 -> 8
}

## 實作AVL Trees
* 為了維持樹的平衡，在插入、刪除時需要進行調整。

### 插入

1.照一般Binary Search Trees的方法插入資料。
2.向上檢查高度是否符合AVL限制。
3.如果符合，結束。
4.如果不符合，旋轉。

* 前面的插入因為同前面章節的insert，故跳過。
* 從你插入資料的node開始檢查，如果到head node都沒問題就OK。
* 如發現該節點的子樹高度差>1，請往下找兩層，並根據這兩層的左右方向，進行LL/RR/LR/RL旋轉。

#### LL旋轉
* 下圖是一個LL旋轉的例子；插入一個新資料"6"之後，導致樹的不平衡。
* 經過向上檢查，18 OK、36 OK，然而在45的地方發現高度差大於一了。
* 檢查路徑後，因為走的路徑是左子樹+左子樹，判定該狀況為LL旋轉。

digraph AVL{
1 [label="45",color="red"];
2 [label="36"];
3 [label="63"];
4 [label="18"];
5 [label="22"];
6 [label="6(new data)"];

1 -> 2[label="L"]
1 -> 3
2 -> 4[label="L"]
2 -> 5
4 -> 6
}

* 觀察一下45、36、18三個node，因為路徑為LL，所以代表45的位置一定最大，36其次，18最小。我們要做的事情就是**將中間值往上提，較小較大放左右**。
* 如此一來，便完成了AVL了平衡。

digraph LL{
subgraph cluster_level1
{
1 [label="A"];
2 [label="B"];
3 [label="T3",shape="box"];
4 [label="T1(new data here)",shape="box"];
5 [label="T2",shape="box"];
}
2 -> 1[style="dashed",color="orange"]
4 -> 2[style="dashed",color="orange"]

1 -> 2[label="L"]
1 -> 3
2 -> 4[label="L"]
2 -> 5

1 -> 3[style="dashed",color="orange"]

subgraph cluster_level2
{
22 [label="B"];
23 [label="T1",shape="box"];
21 [label="A"];
24 [label="T2",shape="box"];
25 [label="T3",shape="box"];
}
22 -> 21
22 -> 23
21 -> 24
21 -> 25
}

#### RR、LR、RL旋轉
* 由於概念與上面的LL相似，在此就只簡單圖片表示。
* 特別注意，我們都是**將中間值往上提，較小較大放左右**（因為很重要再說一次）。

- RR

digraph RR{
subgraph cluster_level1
{
1 [label="A"];
3 [label="T1",shape="box"];
2 [label="B"];
4 [label="T2",shape="box"];
5 [label="T3 (new data here)",shape="box"];
}
1 -> 2[label="R"]
1 -> 3
2 -> 4
2 -> 5[label="R"]

5 -> 2[style="dashed",color="orange"]
2 -> 1[style="dashed",color="orange"]
1 -> 3[style="dashed",color="orange"]

subgraph cluster_level2
{
22 [label="B"];
21 [label="A"];
23 [label="T3",shape="box"];
24 [label="T1",shape="box"];
25 [label="T2",shape="box"];
}
22 -> 21
22 -> 23
21 -> 24
21 -> 25
}

- LR
    - A,B,C中，C是中間值！

digraph LR{
subgraph cluster_level1
{
1 [label="A"];
2 [label="B"];
4 [label="T1",shape="box"];
5 [label="T2 (new data here)",shape="box"];
3 [label="C"];
6 [label="T3",shape="box"];
7 [label="T4",shape="box"];
}

1 -> 2[label="L"]
1 -> 7
2 -> 4
2 -> 3[label="R"]
3 -> 5
3 -> 6

3 -> 1[style="dashed",color="orange"]
1 -> 7[style="dashed",color="orange"]
subgraph cluster_level2
{
22 [label="B"];
21 [label="A"];
24 [label="T1",shape="box"];
25 [label="T2",shape="box"];
23 [label="C"];
26 [label="T3",shape="box"];
27 [label="T4",shape="box"];
}
23->21
23->22
22->24
22->25
21->26
21->27
}

- RL
    - A,B,C中，C是中間值！
    - 該繪圖語言的某些關係，這張圖我畫不出虛線。

digraph RL{
subgraph cluster_level1
{
1 [label="A"];

7 [label="T1",shape="box"];
2 [label="B"];

3 [label="C"];
4 [label="T4",shape="box"];
5 [label="T2(new data here)",shape="box"];
6 [label="T3",shape="box"];
}

1 -> 2[label="R"]
1 -> 7
2 -> 3[label="L"]
2 -> 4
3 -> 5
3 -> 6

subgraph cluster_level2
{
21 [label="A"];
22 [label="B"];
24 [label="T3",shape="box"];
25 [label="T4",shape="box"];
23 [label="C"];
26 [label="T1",shape="box"];
27 [label="T2",shape="box"];
}
23->21
23->22
22->24
22->25
21->26
21->27
}

### 刪除
* 刪除掉元素一樣會導致樹不平衡，我們一樣利用旋轉來維持平衡。

1.照一般Binary Search Trees的規則去刪除。
2.找任意樹葉往上檢查左右子樹高度差。
3.如果都符合，結束。
4.不符合，旋轉。
5.再次檢查，如不符合，再次旋轉。

* 旋轉的方法都和上面插入時的一樣，故不討論。
* 特別注意，根據選擇的樹葉不同，可能導致旋轉完之後依然不平衡。
    * 我不確定這邊應該回到旋轉前的樣子，選擇其他樹葉旋轉，還是直接再次旋轉。
    * 因為畫那些圖很累，我不想畫例子了。

###### tags: `DS` `note`