目錄

  1. Splay Tree 簡介與動機
  2. 基本性質與設計理念
  3. 基本旋轉（Left / Right Rotation）
  4. Splaying 操作 — 三種情況 - 4.1 Zig（單旋） - 4.2 Zig-Zig（同向雙旋） - 4.3 Zig-Zag（異向雙旋）
  5. Search（搜尋）
  6. Insert（插入）
  7. Delete（刪除）
  8. Join 與 Split（合併與分裂）
  9. 完整推演範例
  10. 攤還分析（Amortized Analysis）
  11. 複雜度總表
  12. Splay Tree vs AVL vs Red-Black
  13. 實際應用
  14. C++ 完整實作
  15. 程式碼參照

1. Splay Tree 簡介與動機

Splay Tree（伸展樹） 由 Daniel Sleator 與 Robert Tarjan 在 1985 年提出，是一種自我調整的二元搜尋樹（Self-adjusting BST）。

核心思想

每次存取（search / insert / delete）一個節點後，就把該節點透過一連串旋轉「伸展」到 root。

為什麼這樣做？

  • 局部性原理（Locality of reference）：剛剛存取的節點，極可能在不久後再次被存取。
  • 把熱點節點放在靠近 root 的位置，下一次存取會更快。
  • 不需要儲存任何額外資訊（無 height、無 color、無 BF）— 比 AVL 與 RBT 都節省記憶體。

與其他 BST 的最大差別

特性 BST AVL RBT Splay
嚴格平衡 否 是 是（弱平衡） 否
額外資訊 無 height color 無
單次操作最壞 O(N) O(log N) O(log N) O(N)
攤還複雜度 O(N) O(log N) O(log N) O(log N)

Splay Tree 單次操作可能達到 O(N)，但連續 m 次操作的攤還時間是 O(m log N)。

2. 基本性質與設計理念

2.1 是 BST

Splay Tree 仍然滿足 BST 的性質：

左子樹所有值 < node->data < 右子樹所有值

2.2 沒有平衡限制

樹可能很不平衡，但只要不斷被存取就會被「攤平」。

2.3 操作後一定會 splay

操作 Splay 哪個節點到 root？
Search(x) — 找到 x
Search(x) — 沒找到 最後拜訪的節點（接近 x 的那個）
Insert(x) 新插入的 x
Delete(x) 被刪節點的 parent

3. 基本旋轉（Left / Right Rotation）

Splay Tree 使用與 AVL 相同的旋轉，但目的不同：AVL 是為了平衡，Splay 是為了把節點推往 root。

3.1 Right Rotation（右旋）

        P                    X
       / \                  / \
      X   C        →       A   P
     / \                      / \
    A   B                    B   C

X 上升為 P 的位置，P 變成 X 的右子，B（X 的原右子）變成 P 的左子

3.2 Left Rotation（左旋）

      P                       X
     / \                     / \
    A   X         →         P   C
       / \                 / \
      B   C               A   B

X 上升為 P 的位置，P 變成 X 的左子，B（X 的原左子）變成 P 的右子

3.3 旋轉的不變量

不管哪種旋轉，中序遍歷的結果不變 ⇒ BST 性質保持。

4. Splaying 操作 — 三種情況

設要 splay 的節點為 X，其父親為 P，祖父為 G。

依 X、P、G 的相對位置，分為三種情況：

Case 條件 旋轉方式
Zig P 是 root（無 G） 單旋 1 次
Zig-Zig X 與 P 同方向（都左或都右） 先轉 G，再轉 P（同方向 2 次）
Zig-Zag X 與 P 不同方向（一左一右） 先轉 P，再轉 G（兩個方向）

⚠️ 關鍵差異： Zig-Zig 與普通的「兩次單旋」不同！順序是 先處理祖父，再處理父親，這是 Splay 攤還複雜度為 O(log N) 的關鍵。

4.1 Zig（單旋）

條件： X 的父親 P 已經是 root（X 沒有祖父）。

情況 A：X 是 P 的左子 → 對 P 右旋

       P                  X
      / \                / \
     X   C    →         A   P
    / \                    / \
   A   B                  B   C

情況 B：X 是 P 的右子 → 對 P 左旋（鏡像）

只在最後一步可能發生（樹高為奇數時的最頂端）。

4.2 Zig-Zig（同向雙旋）

條件： X 是 P 的左子且 P 是 G 的左子（左-左），或 X 是 P 的右子且 P 是 G 的右子（右-右）。

Left-Left 形狀

         G                       P                            X
        / \                     / \                          / \
       P   D                   X   G          →             A   P
      / \           →         / \   \                          / \
     X   C                   A   B   D                        B   G
    / \                                                          / \
   A   B                                                        C   D

Step 1: 對 G 右旋  →  P 上升一層
Step 2: 對 P 右旋  →  X 上升到頂

Right-Right 形狀（鏡像）

     G                      P                            X
    / \                    / \                          / \
   A   P                  G   X         →              P   D
      / \      →         / \ / \                      / \
     B   X              A  B C   D                   G   C
        / \                                         / \
       C   D                                       A   B

Step 1: 對 G 左旋
Step 2: 對 P 左旋

💡 為何「先 G 再 P」？ 若先轉 P 再轉 G，會得到「鋸齒狀」結果，無法把 X 推到 root；同時也破壞了攤還分析所需的「位能下降」性質。

4.3 Zig-Zag（異向雙旋）

條件： X 與 P 的方向相反（X 在 P 的內側）。

Left-Right 形狀（P 是 G 的左子，X 是 P 的右子）

         G                  G                              X
        / \                / \                           /   \
       P   D              X   D                         P     G
      / \      →         / \           →               / \   / \
     A   X              P   C                         A   B C   D
        / \            / \
       B   C          A   B

Step 1: 對 P 左旋  →  X 上去成為 G 的左子
Step 2: 對 G 右旋  →  X 變成新 root

Right-Left 形狀（鏡像）

     G                   G                              X
    / \                 / \                           /   \
   A   P               A   X            →            G     P
      / \      →          / \                       / \   / \
     X   D               B   P                     A   B C   D
    / \                     / \
   B   C                   C   D

Step 1: 對 P 右旋
Step 2: 對 G 左旋

演算法

search(root, key):
    cur = root
    last = NULL
    while cur != NULL:
        last = cur
        if key < cur->data:  cur = cur->left
        elif key > cur->data: cur = cur->right
        else: break             # 找到了

    if cur != NULL:
        splay(cur)              # 把找到的節點 splay 到 root
        return true
    else:
        if last != NULL: splay(last)   # 沒找到 → splay 最後拜訪的節點
        return false

重點

  • 找到 vs 沒找到都要 splay（差別在 splay 哪個節點）。
  • Splay 的副作用：讓最近被搜尋的元素跑到 root。

範例

搜尋 4：

       8                            4
      / \                          / \
     3   9        Search(4)       3   8
      \           ─────────→    /     \
       6                       NIL     6
      / \                              \
     4   7                              9
                                       /
                                      7
                                     ...

6. Insert（插入）

演算法

insert(root, key):
    1. 像普通 BST 一樣插入新節點 N
    2. splay(N)         # 把新節點 splay 到 root

步驟詳解

原樹:                    BST 插入 5:               splay(5):
       8                       8                        5
      / \                     / \                      / \
     3   9       Insert(5)   3   9     splay         3   8
      \         ────────→    \              →       /   / \
       6                      6                    4   6   9
      /                      / \                        \
     4                      4   7                        7
      \                      \
       7                      5

變形：合併法（先 split 再 join）

可以用 split：把樹依 key 分成 L (< key) 和 R (> key)，建立新 root = key，左右接 L 和 R。

7. Delete（刪除）

演算法（標準寫法）

delete(root, key):
    1. search(key)        # 把 key splay 到 root
    if root->data != key: return  # 不存在

    2. L = root->left
    3. R = root->right
    4. 刪掉 root

    if L == NULL: root = R
    else:
        # 在 L 中 splay max → max 變成 L 的新 root，且其右子為 NULL
        L = splay(L, max(L))
        L->right = R
        root = L

圖示

要刪除 8：

       8                          5            刪 8 後：              7
      / \                        / \             L      R           / \
     3   9       Search(8)      3   8         /-----\ /---\        5   9
      \         ─────────→       \   \      3        9    →       / \
       5                          7   9      \                   3   8(刪)
      / \                        /            7                   \
     4   7                      6            / \                   ...
        /                                   6   --
       6
                                  → 對 L 中的 max(7) splay 到 L 的 root
                                  → 把 R 接在 L 的 root 右邊

變形：直接用前驅替代

也可以像 BST：找前驅 (predecessor) 替代被刪節點，再 splay parent。

8. Join 與 Split（合併與分裂）

Splay Tree 支援高效的 Split / Join，這在許多進階資料結構中很有用（如 Link-Cut Tree）。

8.1 Split

給定樹 T 和 key x，將 T 分裂為 (L, R)：L 中所有值 < x，R 中所有值 ≥ x。

split(T, x):
    splay x（或最接近 x 的節點）to root
    if root->data < x:
        L = T;  R = T->right;  L->right = NULL
    else:
        R = T;  L = T->left;   R->left = NULL
    return (L, R)

時間：O(log N) 攤還。

8.2 Join

給定兩棵樹 L 和 R，且 L 中所有值 < R 中所有值，合併成一棵樹。

join(L, R):
    if L == NULL: return R
    if R == NULL: return L
    對 L 中的 max splay 到 L 的 root  → L 的 root 沒有右子
    L->right = R
    return L

時間：O(log N) 攤還。

9. 完整推演範例

依序插入 10, 20, 30, 40, 25：

Insert 10:                Insert 20:                 splay(20):
   10                          10                          20
                                 \                        /
                                  20                     10

Insert 30:               splay(30):                 之後狀態:
     20                        30                        30
    /  \                      /                         /
   10   30                   20                        20
                            /                         /
                           10                        10

Insert 40:                splay(40):                 之後狀態:
       30                        40                        40
      /  \                      /                         /
     20   40                   30                        30
    /                         /                         /
   10                        20                        20
                            /                         /
                           10                        10

Insert 25:
依 BST 規則 25 應插入在 30 的左子：
       40
      /
     30                       Insert 25 後（暫時）:
    /                                40
   20                               /
  /                                30
 10                               /  \
                                 20  ?  ←  25 應在 20 的右子
                                /
                               10

實際:
      40
     /
    30
   /
  20
 / \
10  25

接著對 25 執行 splay：

Step 1: 25 與 20 是 zig-zag (Right-Left in 30)？
        其實 25 是 20 的右子，20 是 30 的左子 → Left-Right 形狀

       40                40                    40
      /                 /                     /
     30        →       30           →        25
    /                 /                     /  \
   20                25                    20   30
   / \              /  \                  /
  10  25           20   --              10
                  /
                 10

Step 1 (對 20 左旋):
   30                  30
   /                   /
   20      →          25
   / \                /
  10  25             20
                     /
                    10

Step 2 (對 30 右旋):
   30                  25
   /                  /  \
   25       →        20   30
   /                  /
   20                10
   /
  10

Step 3: 25 的父親是 40 (root) → 還需要一次 zig（對 40 右旋）

   40                       25
   /                       /  \
   25         →           20   40
  /  \                   /     /
  20  30                10    30
  /
  10

Final 樹:
        25
       /  \
      20   40
     /     /
    10    30

10. 攤還分析（Amortized Analysis）

10.1 什麼是攤還？

平均每個操作的成本（在最壞的操作序列下）。

對於 Splay Tree，單次操作最壞 O(N)，但任意 m 次操作的總成本 ≤ O(m log N)。

10.2 位能函數（Potential Function）

定義：

size(x)  = 以 x 為根的子樹節點數
rank(x)  = log₂(size(x))
Φ(T)     = Σ rank(x)   對所有節點 x

10.3 攤還成本

amortized cost = actual cost + ΔΦ

關鍵定理（Access Lemma）：

對節點 x 的單次 splay，攤還成本 ≤ 3 × (rank(root) − rank(x)) + 1 = O(log N)

證明分別考慮 Zig、Zig-Zig、Zig-Zag 三種情況的位能變化（複雜，這裡略）。

10.4 結論

  • 單次 splay 的攤還成本：O(log N)
  • 因此 search / insert / delete 的攤還成本都是 O(log N)

10.5 Splay Tree 的進階性質

性質 說明
Balance Theorem m 次操作總成本 O((m + N) log N)
Static Optimality 若已知存取頻率，splay tree 最多比最佳靜態 BST 慢常數倍
Static Finger 從某固定指標 f 出發查 x：O(log |x − f|) 攤還
Working Set 最近存取過的元素查得快
Dynamic Optimality (猜想) 可能比任何動態 BST 都好（仍未證明）

11. 複雜度總表

操作 最壞單次 攤還 空間
Search O(N) O(log N) O(N)
Insert O(N) O(log N) O(N)
Delete O(N) O(log N) O(N)
Split O(N) O(log N) O(N)
Join O(N) O(log N) O(N)

12. Splay Tree vs AVL vs Red-Black

項目 AVL Red-Black Splay
平衡條件 |BF| ≤ 1 五條顏色規則 無（自我調整）
單次最壞 O(log N) O(log N) O(N)
攤還 O(log N) O(log N) O(log N)
節點額外空間 int (4B) height 1 bit color 無
實作複雜度 中 高 較簡單（只有三種 splay case）
常數因子 小 中 大（每次都要 splay）
熱點存取 無加速 無加速 顯著加速
適用場景 查詢頻繁、平衡需求嚴格 通用（STL） 存取分布不均

何時選 Splay Tree？

✓ 存取有強烈局部性（90/10 規則） ✓ 需要實作 Split / Join / Merge ✓ 想要簡單實作、不想存平衡資訊 ✓ 構建更複雜的資料結構（如 Link-Cut Tree、Tango Tree）

✗ 嚴格要求單次操作 O(log N) ✗ 多執行緒並發（splay 改動結構，不利並發）

13. 實際應用

應用 說明
Linux Kernel 部分子系統用過（如早期的 Process scheduler）
Sleator-Tarjan Link-Cut Tree Splay tree 是其核心元件
Tango Tree 一種 O(log log N)-competitive 的 BST
編輯器 / Cache 利用 working-set 性質加速近期操作
Network routing 路由表的快速查找

14. C++ 完整實作

下面是核心程式碼。完整可執行版本在 tree_splay.cpp。

14.1 節點結構

struct SplayNode {
    int data;
    SplayNode* left;
    SplayNode* right;
    SplayNode* parent;   // splay 需要往上走，所以記 parent

    SplayNode(int val)
        : data(val), left(nullptr), right(nullptr), parent(nullptr) {}
};

💡 與 AVL/RBT 不同，Splay 通常記 parent 指標方便 splay。也可以用「自頂向下 (top-down) splay」省掉 parent 指標。

14.2 旋轉

// 左旋：x 上升，x 的 parent 下降為 x 的左子
void rotateLeft(SplayNode*& root, SplayNode* x) {
    SplayNode* p = x->parent;
    SplayNode* B = x->left;       // 將要轉移給 p

    // 1. p 與 B 連接
    p->right = B;
    if (B) B->parent = p;

    // 2. x 取代 p 在祖父中的位置
    x->parent = p->parent;
    if (!p->parent)               root = x;        // p 是 root
    else if (p == p->parent->left) p->parent->left  = x;
    else                           p->parent->right = x;

    // 3. x 與 p 連接
    x->left  = p;
    p->parent = x;
}

// 右旋（鏡像）
void rotateRight(SplayNode*& root, SplayNode* x) {
    SplayNode* p = x->parent;
    SplayNode* B = x->right;

    p->left = B;
    if (B) B->parent = p;

    x->parent = p->parent;
    if (!p->parent)               root = x;
    else if (p == p->parent->left) p->parent->left  = x;
    else                           p->parent->right = x;

    x->right = p;
    p->parent = x;
}

14.3 Splay 主函式

void splay(SplayNode*& root, SplayNode* x) {
    while (x->parent) {
        SplayNode* p = x->parent;
        SplayNode* g = p->parent;

        if (!g) {
            // === Zig：P 是 root ===
            if (x == p->left) rotateRight(root, x);
            else              rotateLeft (root, x);
        }
        else if (x == p->left && p == g->left) {
            // === Zig-Zig（左-左）：先 G 再 P ===
            rotateRight(root, p);
            rotateRight(root, x);
        }
        else if (x == p->right && p == g->right) {
            // === Zig-Zig（右-右）===
            rotateLeft(root, p);
            rotateLeft(root, x);
        }
        else if (x == p->right && p == g->left) {
            // === Zig-Zag（左-右）：先 P 再 G ===
            rotateLeft (root, x);
            rotateRight(root, x);
        }
        else { // x == p->left && p == g->right
            // === Zig-Zag（右-左）===
            rotateRight(root, x);
            rotateLeft (root, x);
        }
    }
}

bool search(SplayNode*& root, int key) {
    SplayNode* cur  = root;
    SplayNode* last = nullptr;

    while (cur) {
        last = cur;
        if      (key < cur->data) cur = cur->left;
        else if (key > cur->data) cur = cur->right;
        else break;
    }

    if (cur)         { splay(root, cur);  return true; }
    else if (last)   { splay(root, last); return false; }
    else             { return false; }
}

14.5 Insert

void insert(SplayNode*& root, int key) {
    SplayNode* cur  = root;
    SplayNode* parent = nullptr;

    while (cur) {
        parent = cur;
        if      (key < cur->data) cur = cur->left;
        else if (key > cur->data) cur = cur->right;
        else { splay(root, cur); return; } // 已存在 → 直接 splay
    }

    SplayNode* node = new SplayNode(key);
    node->parent = parent;
    if (!parent)               root = node;
    else if (key < parent->data) parent->left  = node;
    else                         parent->right = node;

    splay(root, node);
}

14.6 Delete

void erase(SplayNode*& root, int key) {
    if (!search(root, key)) return;       // 不存在 → 直接返回
    // 此時 key 已 splay 到 root

    SplayNode* L = root->left;
    SplayNode* R = root->right;
    delete root;

    if (!L) {
        root = R;
        if (R) R->parent = nullptr;
    } else {
        L->parent = nullptr;
        // 在 L 中找 max（最右節點）並 splay 到 L 的 root
        SplayNode* m = L;
        while (m->right) m = m->right;
        splay(L, m);                       // m 變成 L 的 root，且 m->right == NULL
        m->right = R;
        if (R) R->parent = m;
        root = L;
    }
}

15. 程式碼參照

檔案 內容
tree_splay.cpp Splay Tree 完整實作：Insert, Search, Delete, Split, Join, 三種 splay case 視覺化, 逐步示範

編譯與執行

g++ -std=c++11 -Wall -o tree_splay tree_splay.cpp
./tree_splay

程式提供的功能

  1. 逐步插入示範：展示每次 splay 後的樹結構
  2. Search 示範：找到與沒找到的不同 splay 行為
  3. Delete 示範
  4. Split / Join 示範
  5. 互動模式：手動輸入指令操作樹

附錄：Top-Down Splay（進階）

上面實作是 Bottom-Up Splay：先走到底，再從下往上 splay（需要 parent 指標）。

另一種叫 Top-Down Splay：邊往下走邊 splay，不需要 parent 指標。它會維護兩棵暫存樹 L、R，在搜尋過程中把節點分到 L、R，最後組裝起來。Top-Down 版本常數更小，但邏輯較難理解。

兩種寫法的攤還複雜度都是 O(log N)。

參考文獻： - Sleator, D. D., & Tarjan, R. E. (1985). Self-adjusting binary search trees. Journal of the ACM. - CLRS, Chapter 17 (Amortized Analysis), Chapter 12 (BST).