---
title: 'Splay Tree'
disqus: hackmd
---
[TOC]

## Splay Tree - 伸展樹
* **Def**

* 是一種能夠自我平衡的二元搜尋樹，它能在均攤 $O(log_n)$ 的時間內完成基於伸展（Splay）操作

假設想對一個 BST 執行一系列的尋找操作，為了使整個尋找時間更小，
被查頻率高的那些 $Node$ 就應該在靠近樹根的位置。

因此 $Splay\ Tree$ 被發明出來，它會沿著從某個節點到樹根之間的路徑，通過一系列的旋轉把這個節點搬移到樹根去。

它的優勢在於不需要記錄用於平衡樹的冗餘資訊。

* 與 Binary Tree 差異：最差時間下的操作都能保持在 $O(log_n)$
* 唯一導致 Splay Tree 產生最差時間 $O(n)$ 的是以 `非遞減順序` 操作資料
:::success
非遞減順序：1,2,3,4,4,5...
:::

---

### Rotation 旋轉

* 這裡的 Rotation 與 AVL Tree 有一點不同
<br>
#### ==向右旋轉 Right Rotation==
<br><br><br>
#### ==向左旋轉 Left Rotation==

* 綠色 Node 都是 Search 或 Find 的點，所以很明顯的他在往 Root 移動，單旋轉的部分就跟 AVL Tree 一模一樣
<br><br><br>
#### ==向右單旋轉 Single Right Rotation==
* 記住要接著做 ==AVL== 的左旋轉 (Left Rotation)
<br><br><br>
#### ==向左單旋轉 Single Left Rotation==
* 記住要接著做 ==AVL== 的右旋轉 (Right Rotation)
:::danger
切記當我們搜尋、插入到 Node 後再往上判斷是哪一個情形，再進行旋轉
旋轉完未到 Root 的也是在以該 Node 往上判斷旋轉，直到 Root
:::

###### tags: `Data Structure`

左偏樹（leftist tree或leftist heap）
是一種 Pirority Queue 在 greedy 問題會出現

leftist tree 的合併操作的最壞情況複雜度為O(log n)，
而 complete binary heap 為O(n)，
所以 leftist tree 適合基於合併操作的情形。

由於 leftist tree 已經不是完全二元樹，因此不能用陣列儲存表示，需要用連結結構