平衡樹的世界不是只有「嚴格保證」一條路。有時候你要的不是最壞情況的鐵飯碗，而是好寫、好擴展。
為什麼還需要它們？AVL / 紅黑樹不夠嗎？
AVL 和紅黑樹確實保證每次操作 O(log n)，理論上無懈可擊。問題在實作：你有沒有真的手寫過紅黑樹的刪除？那個「兄弟節點是紅是黑、姪子在內側還是外側」的 case 分析，能寫到你懷疑人生，而且一個 case 漏掉就是難 debug 的隱性 bug。
更麻煩的是區間操作。想在一個平衡序列裡「把第 3 到第 7 個元素整段翻轉」，AVL 和紅黑樹那套嚴格旋轉幾乎沒辦法優雅擴展。
Treap 和 Splay Tree 是兩條「不硬幹」的路，各自放棄了一點東西換來簡潔：
- Treap 放棄「確定的平衡」，改用隨機——期望 O(log n)，但實作只需 split / merge 兩招。
- Splay Tree 乾脆連平衡都不主動維護，改成「每次用完就把節點搬到根」的自我調整——單次不保證，但均攤 O(log n)。
Treap：把平衡交給骰子
Treap 的招數是讓每個節點多抽一張隨機號碼牌（priority）。key 遵守 BST 性質（左 < 根 < 右），priority 遵守 Heap 性質（父 > 子）。兩個約束一疊加，樹的形狀就等同於「照隨機順序插入的 BST」——期望樹高 O(log n)。
節點 = (key, priority)
key 走 BST：左 < 根 < 右
pri 走 Heap：父 > 子
(30,91)
/ \
(20,45) (50,72)
/
(10,23)
中序遍歷 key：10, 20, 30, 50 ✓（BST 成立）
父 pri > 子 pri：91>45, 91>72, 45>23 ✓（Heap 成立）隨機的 priority 就是平衡的來源：你沒辦法刻意構造一組輸入把它搞歪，因為歪不歪是骰子決定的，跟你的插入順序無關。
一切都是 Split 與 Merge
Treap 的美在於：插入、刪除全都由兩個基礎操作拼出來。
- Split(root, k)：把樹按 key 拆成兩棵——左樹所有 key ≤ k，右樹 key > k。
- Merge(L, R)（要求 L 所有 key < R 所有 key）：比較兩根的 priority，大的當新根，遞迴合併剩下的。
// 插入 = split + 建新節點 + merge 兩次
void insert(int key) {
Node[] parts = split(root, key);
Node newNode = new Node(key); // priority 隨機生成
root = merge(merge(parts[0], newNode), parts[1]);
}
// 刪除 = split 兩次挖出目標 + merge 把兩側接回（中間丟掉）
void delete(int key) {
Node[] leftMid = split(root, key - 1);
Node[] midRight = split(leftMid[1], key);
// midRight[0] 就是 key 那個節點，直接丟棄
root = merge(leftMid[0], midRight[1]);
}隱式鍵 Treap：Treap 真正的殺手鐧
把 key 拿掉，改用子樹大小來隱式定義「第幾個元素」，Treap 就變成一個支援 O(log n) 分裂／合併的序列：
[1, 2, 3, 4, 5] 上可以 O(log n) 做：
- 在任意位置插入 / 刪除
- 區間翻轉（reverse 第 i~j 個）
- 區間搬移這是很多競程題的核心武器，也是 AVL / 紅黑樹再怎麼硬旋都做不漂亮的地方。
Splay Tree：常用的自己浮上來
Splay Tree 的比喻是桌上那疊書：每次抽一本看完，順手放回最上面。常翻的自然浮到頂，下次一伸手就拿到。它什麼平衡資訊都不存（沒有高度、沒有顏色），只有一條鐵律：
每次 search / insert / delete 後，把操作的那個節點「伸展」到根。
它不保證單次 O(log n)，但保證連續 m 次操作均攤 O(m log n)。真正的甜蜜點是存取不均勻的工作負載——符合 80/20 法則時，那 20% 常用資料自動快取在根附近。
伸展的三種姿勢
把節點 x 一路旋到根，看它跟父、祖父的相對位置分三種：
Zig（x 是根的直接子）：單旋一次就到頂
Zig-Zig（x 與父同側）：先旋祖父、再旋父
Zig-Zag（x 與父異側）：先旋父、再旋祖父（等同兩次單旋）為什麼 Zig-Zig 不能拆成兩次 Zig？
這是整個 Splay Tree 均攤分析的命門。如果 Zig-Zig 你圖方便做成「連兩次單旋」，在一條歪成鏈狀的樹上，均攤會退化回 O(n)——等於白忙。先旋祖父再旋父這個順序，才能讓路徑上的節點深度整體減半，撐住均攤 O(log n)。這一步是 Splay Tree 唯一「反直覺但不能省」的地方。
// Split：splay(key) 後根就是 key，左右子樹天然分好
Node[] split(int key) {
splay(findNode(key));
Node right = root.right;
root.right = null;
return new Node[]{root, right};
}兩棵樹放在一起看
| Treap | Splay Tree | AVL / 紅黑樹 | |
|---|---|---|---|
| 平衡怎麼來 | 隨機 priority | 每次存取後伸展到根 | 嚴格旋轉 / 著色 |
| 時間保證 | 期望 O(log n) | 均攤 O(log n) | 確定 O(log n) |
| 單次最壞 | O(n)（機率極低） | O(n) | O(log n) |
| 實作難度 | 簡單（split/merge） | 中等 | 複雜 |
| 殺手應用 | 隱式鍵做區間操作 | 存取不均、Link-Cut Tree 的基礎 | 系統函式庫、穩定保證 |
選型的一句話：要最壞情況的鐵保證去用紅黑樹；要好寫又能玩區間用 Treap；要吃到存取局部性的紅利用 Splay。三者不是誰取代誰，是三種對「平衡」這件事的不同妥協。
🎬 互動視覺化：Treap 與 Splay Tree 動畫 — 看 Treap 的隨機 priority 怎麼自動把樹壓矮、Splay 的 zig-zig/zig-zag 怎麼把剛存取的節點一路旋到根，比讀旋轉圖快得多。
嚴格平衡樹像考試作答，每一步都要對；Treap 和 Splay 像實戰——一個賭機率、一個賭局部性，賭對了就又快又好寫。
接下來往哪走
- AVL Tree 自平衡二元搜尋樹 — 對照組：靠嚴格旋轉硬保證平衡的那條路
- Red-Black Tree 紅黑樹 — 系統函式庫最愛，也是「手寫刪除懷疑人生」的主角
- Fibonacci Heap 與 Link-Cut Tree — Splay Tree 的伸展技巧正是 Link-Cut Tree 的核心零件