Splay Trees

定義

Splay Tree：一種二元搜尋樹 (BST)。
每次執行 Search / Insert / Delete 操作後，會對相關節點做 splay (伸展)，也就是透過一連串旋轉，將該節點移到樹根。
目標：利用平攤分析 (amortized analysis)，保證平均操作時間為 O(log n)。

敘述對於起始節點 \(q\)，單次 splay 的平攤成本至多為 \(3(\log_2 n - r(q)) + 1\)

位能法公式

\text{Amortized cost} = (\text{actual cost}) + (\Phi_i - \Phi_{i-1})

其中：

分情況討論

1. Zig

2. Zig（有父無祖父）

實際成本 = \(1\)。
位能變化：\(\Delta \Phi = \Phi_i - \Phi_{i-1} = (r'(p) + r'(q)) - (r(p) + r(q))\)。
單調性：
- \(p\) 的子樹變小：\(s'(p) \le s(p) \;\Rightarrow\; r'(p) \le r(p)\)。
- \(q\) 的子樹變大：\(s'(q) \ge s(q) \;\Rightarrow\; r'(q) \ge r(q)\)。
由性質可得：\(\text{Amortized cost}=1+\Delta \Phi \leq 1 + (r'(q) - r(q))\)。

3. Zig-Zig / Zig-Zag

\Delta \Phi = r'(q) + r'(p) + r'(gp) - r(q) - r(p) - r(gp)

\text{Amortized cost} \leq 3(r'(q) - r(q)) - 1

綜合各情形得 Access Lemma：\(\text{amortized cost} \le 3\big(r(\text{root}) - r(q)\big) + 1 \le 3(\log_2 n - r(q)) + 1\)。因此為 \(O(\log n)\)，且給出更精確的常數界。

敘述在一棵空的 splay tree 上進行 \(n\) 次操作（search, insert, delete），總時間為 \(O(n \log n)\)。

推導

T_i = (\text{amortized cost}) + (\Phi_{i-1} - \Phi_i)

T = \sum_{i=1}^n T_i = \sum_{i=1}^n (\text{amortized cost}) + (\Phi_0 - \Phi_n)

T \leq \sum_{i=1}^n (\text{amortized cost})

T \leq O(n \log n)

結論 : n 次操作的總時間複雜度為 \(O(n \log n)\)。

Zig
- 條件：節點 q 有父節點 p，但沒有祖父節點 gp。
- 動作：對 p 和 q 做單次旋轉。
- 註解：只需一步旋轉就能將節點提到根．
Zig-Zig
- 條件：節點 q 有父節點 p 和祖父節點 gp，且 q 和 p 在同一方向（LL 或 RR）。
- 動作：先旋轉 gp-p，再旋轉 p-q。
- 註解：連續兩次同方向旋轉，像「之」字往同一邊彎，稱為 Zig-Zig。
Zig-Zag
- 條件：節點 q 有父節點 p 和祖父節點 gp，但 q 和 p 在不同方向（LR 或 RL）。
- 動作：先旋轉 p-q，再旋轉 gp-q。
- 註解：方向交錯，先往一邊再往另一邊，像「之」字折返，稱為 Zig-Zag。

\Phi \,=\, r(1)+r(9)+r(8)+r(2)+r(7)+r(6)+r(3)+r(4)+r(5)\,\approx\,18.4691

資料結構	調整方式	單次最壞情況	平攤時間
AVL Tree	高度平衡	\(O(log n)\)	\(O(log n)\)
Red-Black Tree	弱平衡	\(O(log n)\)	\(O(log n)\)
Splay Tree	自我調整	\(O(n)\)	\(O(log n)\)