# BST的退化與解決方法

## BST的退化
當我們使用BST時，通常會希望節點的分佈是平均的，也就是理想情況下BST任一節點的左右子樹大小越接近越好，這樣樹的深度可以盡可能減小。

然而在最壞的情況下，樹上每個節點可能只有左或右子節點，導致樹的深度即是樹的大小，讓BST退化成一個Linked-List，讓一些複雜度與樹高有關的操作的複雜度從$O(logn)$變成$O(n)$，大幅降低了效率。因此，我們需要維持BST的平衡來防止此事的發生。

上圖是一個退化成Linked-List的樹([圖源](https://www.sonake.com/2019/11/26/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%AD%E7%9A%84%E6%A0%91/))

## 二元樹的平衡

二元樹的平衡主要有兩種方法：基於樹旋轉與基於隨機平衡，還有其他不常見的方法，在此處不多做介紹。兩種方法各有其優缺點，以下是兩種方法的介紹：

### 基於隨機

透過隨機來平衡二元樹的方法，最典型的即是樹堆(Treap)，顧名思義，是由樹(Tree)與堆積(Heap)所組成。Treap是針對二分搜尋樹(BST)做的改良，利用隨機的priority與heap的性質來達成期望$O(logn)$的深度。[treap複雜度的嚴謹證明](https://web.archive.org/web/20070706050244/http://www.ischool.berkeley.edu/~aragon/pubs/rst96.pdf)

#### 先備知識：max-heap的性質
max-heap是個二元樹，每個節點都有一個priority，對於每個節點，自身的priority皆$\geq$所有小孩的priority。min-heap的話就是$\leq$自己的所有小孩。

#### BST+heap

紅色是key，藍色是priority，key滿足BST，priority滿足max-heap。
> 圖源：實中資研講義：進階資料結構
#### 實作概述

Treap僅需要實作兩個操作:
- merge: 將兩個treap合併，其中一個Treap的所有key要小於另一個Treap的所有key
- split: 將一顆treap根據key K切開，左邊treap的所有key$\leq$K$\leq$右邊的所有key

其他的操作都是由這兩個操作所組成

##### 優缺點
###### 優點
* 實作複雜度低，非常容易用於競賽(根據大佬PixelCat所述)
* code短
* 隨機不香嗎
###### 缺點
* 相較其他資料結構決定性的$O(logn)$深度，Treap僅有期望的$O(logn)$深度，運氣太差還是會退化(不過幾乎不會)

### 基於樹旋轉

在介紹基於樹旋轉的平衡樹以前，我們先介紹何謂樹旋轉操作。
#### 樹旋轉
一言以蔽之，樹旋轉在做的就是「換根」，將根的左或右孩子提升到根的高度。
> 圖源：wiki: 樹旋轉

上面的動畫演示了樹的「右旋」，反過來做逆時針旋轉稱作「左旋」。
觀察旋轉前後的結果，我們可以觀察到以下性質：
1. 旋轉過後的中序走訪順序不變，也就是葉節點的順序是不會變的。
2. 旋轉後BST的性質仍會維持，左子樹還是小於根，右子樹還是大於根。

為了維護以上的特性，我們要針對特別的的情況改變子樹的父親(參考上方動畫中的$\beta$)。

由於樹旋轉僅是針對5個節點的操作，樹旋轉的複雜度為$O(1)$

### 樹旋轉資料結構
介紹完樹旋轉，我們來介紹一些基於樹旋轉的資料結構：
#### AVL Tree
AVL Tree是最早被發明的自平衡BST，在任一節點中，左子樹和右子樹的差$\leq1$，如果超過就要利用樹旋轉來平衡。

##### 實作概述

AVL Tree需要實現的操作如下:

1. 平衡：AVL樹的平衡即是左元和右旋的組合，在左左與右右需要一次樹旋轉，左右與右左需要兩次。以下是四種情況的旋轉方式：

> 圖源：wiki:AVL Tree

2. 刪除：葉節點直接$O(1)$刪除即可，其他的節點在刪除後要做$O(logn)$次的旋轉來平衡。

3. 搜尋:與普通的BST相同，由於AVL樹一定是平衡的，複雜度為$O(logn)$，搜尋操作不同於splay，不會更改到本身的資料。

#### Splay Tree

Splay Tree是一種基於伸展(Splay)操作達成均攤$O(logn)$的插入、尋找、修改與刪除動作的自平衡樹。

#### 實作概述
##### Splay操作
在節點x被存取後，splay操作會把x旋轉至靠近根節點的位置，如此可以得到期望均攤$O(logn)$的深度

其他的操作如下：
1. 連接：將兩棵樹S與T連結，其中S的所有元素小於T的所有元素
2. 分割：給予一個樹和元素x，分割樹兩個樹S,T，其中S的所有元素$\leq x<$t的所有元素
3. 插入：依據BST的性質往下找到空節點插入，最後做一次splay操作。
4. 尋找：即是一般BST的尋找方法。

##### 優缺點
###### 優點
* 決定性的均攤$O(logn)$複雜度
* 不用維護樹的額外資訊
###### 缺點
* 實作複雜度比treap高
* 有時會退化成一條鍊，然而均攤複雜度還是$O(logn)$

## 參考資料
https://hackmd.io/ANeKKDYOSjS4PVrMXhBTZw
https://zh.wikipedia.org/wiki/%E5%B9%B3%E8%A1%A1%E6%A0%91
https://zh.wikipedia.org/wiki/%E4%BC%B8%E5%B1%95%E6%A0%91
https://zh.wikipedia.org/wiki/AVL%E6%A0%91
https://zh.wikipedia.org/wiki/%E6%A0%91%E5%A0%86