定義

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

Splay Tree Lemma 與 Theorem 證明整理

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

位能法公式 $$ \text{Amortized cost} = (\text{actual cost}) + (\Phi_i - \Phi_{i-1}) $$
- 其中：
  - $r(i) = \log_2s(i)$，$s(i)$ 是以節點 $i$ 為根的子樹大小。
  - 位能 $\Phi = \sum_i r(i)$。

分情況討論

Zig：
- $q$ 為 root 或無祖父。
- 成本 $=1$，位能不變。
- Amortized cost $=1$。
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))$
Zig-Zig / Zig-Zag：
- 影響節點 $q, p, gp$。
- 位能變化： $$ \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。

04-範例 05-範例

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