tree_splay.cpp

/*
 * ============================================================================
 *  Splay Tree（伸展樹）— 完整實作
 *  File: tree_splay.cpp
 *
 *  Splay Tree 由 Sleator & Tarjan 於 1985 年提出。
 *  這是一棵 BST，每次存取（search / insert / delete）後會把該節點
 *  透過一連串旋轉「伸展」(splay) 到 root，使常被存取的節點靠近 root。
 *
 *  特性：
 *    - 不需平衡資訊（無 height、無 color）
 *    - 單次操作最壞 O(N)
 *    - 任意 m 次操作攤還 O(m log N) → 攤還複雜度 O(log N)
 *    - 利用「最近存取」局部性：working-set 性質
 *
 *  涵蓋操作：
 *    1.  節點結構（含 parent 指標）
 *    2.  左旋 / 右旋
 *    3.  Splay 主函式（Zig / Zig-Zig / Zig-Zag 三種情況）
 *    4.  Search（找到或沒找到都 splay）
 *    5.  Insert（插入後把新節點 splay 到 root）
 *    6.  Delete（先 splay 到 root，再合併左右子樹）
 *    7.  Split / Join
 *    8.  Inorder / Preorder / Level-order traversal
 *    9.  視覺化輸出
 *   10.  互動式 demo
 *
 *  Compile: g++ -std=c++11 -Wall -o tree_splay tree_splay.cpp
 *  Run:     ./tree_splay
 * ============================================================================
 */

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>

using namespace std;

/* ============================================================================
 *  1. 節點結構
 *
 *  與普通 BST 比，多存一個 parent 指標。
 *  原因：splay 需要從某個節點往「上」走（找 parent / grandparent）。
 *  注意：parent 必須在每次旋轉後正確維護，否則會壞掉。
 * ============================================================================ */
struct SplayNode {
    int data;
    SplayNode* left;
    SplayNode* right;
    SplayNode* parent;

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

/* ============================================================================
 *  輔助：判斷 x 是否為其 parent 的左/右子
 * ============================================================================ */
bool isLeftChild(SplayNode* x) {
    return x->parent && x->parent->left == x;
}

/* ============================================================================
 *  2. 旋轉
 *
 *  rotateLeft(x)：x 是 parent 的右子，把 x 旋轉到 parent 的位置。
 *  rotateRight(x)：x 是 parent 的左子，把 x 旋轉到 parent 的位置。
 *
 *  注意：旋轉一律「以 x 為主角」，呼叫者要保證 x 有 parent。
 *  維護重點：
 *    - x 與 p 之間的 parent/child 關係
 *    - 轉移子樹的 parent 指標
 *    - 若 p 原本是 root，要更新 root
 * ============================================================================ */

/*
 * Right Rotation：x 是 p 的左子
 *
 *        p                  x
 *       / \                / \
 *      x   C    →         A   p
 *     / \                    / \
 *    A   B                  B   C
 */
void rotateRight(SplayNode*& root, SplayNode* x) {
    SplayNode* p = x->parent;
    SplayNode* B = x->right;            // x 的右子（將轉移給 p）

    // 1. p 接收 B 為新的左子
    p->left = B;
    if (B) B->parent = p;

    // 2. x 取代 p 在祖父的位置
    x->parent = p->parent;
    if (!p->parent) {
        root = x;                       // p 原本是 root → x 變成新 root
    } else if (p == p->parent->left) {
        p->parent->left = x;
    } else {
        p->parent->right = x;
    }

    // 3. x 接 p 為自己的右子
    x->right  = p;
    p->parent = x;
}

/*
 * Left Rotation：x 是 p 的右子
 *
 *      p                       x
 *     / \                     / \
 *    A   x         →         p   C
 *       / \                 / \
 *      B   C               A   B
 */
void rotateLeft(SplayNode*& root, SplayNode* x) {
    SplayNode* p = x->parent;
    SplayNode* B = x->left;             // x 的左子（將轉移給 p）

    p->right = 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->left  = p;
    p->parent = x;
}

/* ============================================================================
 *  3. Splay 主函式 — 把節點 x 旋轉到 root
 *
 *  分三種情況（依 x、parent、grandparent 的相對位置）：
 *
 *    Case 1 — Zig：parent 是 root（無 grandparent）→ 對 parent 做一次旋轉
 *
 *    Case 2 — Zig-Zig：x、p 同方向（都左或都右）
 *        關鍵：先轉 grandparent，再轉 parent
 *        若反過來會破壞攤還分析的位能下降
 *
 *    Case 3 — Zig-Zag：x、p 不同方向
 *        先轉 parent，再轉 grandparent（順序與 Zig-Zig 相反）
 * ============================================================================ */
void splay(SplayNode*& root, SplayNode* x) {
    if (!x) return;

    while (x->parent) {
        SplayNode* p = x->parent;
        SplayNode* g = p->parent;

        if (!g) {
            // === Case 1: Zig === (p 是 root)
            if (isLeftChild(x)) rotateRight(root, x);
            else                rotateLeft (root, x);
        }
        else if (isLeftChild(x) && isLeftChild(p)) {
            // === Case 2a: Zig-Zig (Left-Left) ===
            //   先對 g 右旋，再對 p 右旋（注意此時 p 已是 g 的位置）
            rotateRight(root, p);
            rotateRight(root, x);
        }
        else if (!isLeftChild(x) && !isLeftChild(p)) {
            // === Case 2b: Zig-Zig (Right-Right) ===
            rotateLeft(root, p);
            rotateLeft(root, x);
        }
        else if (!isLeftChild(x) && isLeftChild(p)) {
            // === Case 3a: Zig-Zag (Left-Right) ===
            //   先對 p 左旋（x 上去），再對 g 右旋
            rotateLeft (root, x);
            rotateRight(root, x);
        }
        else { // isLeftChild(x) && !isLeftChild(p)
            // === Case 3b: Zig-Zag (Right-Left) ===
            rotateRight(root, x);
            rotateLeft (root, x);
        }
    }
}

/* ============================================================================
 *  4. Search（搜尋）
 *
 *  - 找到：splay 該節點到 root，回傳 true
 *  - 沒找到：splay 最後拜訪的節點到 root，回傳 false
 *    （這是 splay tree 的特色：失敗的搜尋也會調整樹的結構）
 * ============================================================================ */
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;
    }
    if (last) splay(root, last);
    return false;
}

/* ============================================================================
 *  5. Insert（插入）
 *
 *  Step 1: 像普通 BST 找到應插入的位置
 *  Step 2: 建立新節點接上去
 *  Step 3: splay 新節點到 root
 *
 *  若 key 已存在 → 不插入，但仍 splay 該節點到 root
 * ============================================================================ */
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 後返回
            splay(root, cur);
            return;
        }
    }

    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);
}

/* ============================================================================
 *  6. Delete（刪除）
 *
 *  Step 1: search(key) 把 key splay 到 root
 *  Step 2: 若 root->data != key → 不存在，返回
 *  Step 3: 拆下 root，分成 L 和 R 兩棵子樹
 *  Step 4: 在 L 中把 max splay 到 root → max 沒有右子
 *  Step 5: 把 R 接在 L 的 root 右邊
 * ============================================================================ */
void erase(SplayNode*& root, int key) {
    if (!search(root, key)) return;        // 不存在
    if (root->data != key)  return;        // 雙重保險

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

    if (!L) {
        root = R;
        if (R) R->parent = nullptr;
        return;
    }

    L->parent = nullptr;

    // 在 L 中找 max（最右節點），splay 到 L 的 root
    SplayNode* m = L;
    while (m->right) m = m->right;
    splay(L, m);                           // 之後 m == L，且 m->right == nullptr

    L->right = R;
    if (R) R->parent = L;
    root = L;
}

/* ============================================================================
 *  7. Split / Join
 *
 *  split(T, x)：分裂為 (L, R)，L 中所有值 < x，R 中所有值 >= x
 *  join(L, R)：L 中所有值 < R 中所有值，合併為一棵
 * ============================================================================ */
void splitTree(SplayNode* T, int x, SplayNode*& L, SplayNode*& R) {
    if (!T) { L = R = nullptr; return; }

    // 把最接近 x 的節點 splay 到 root
    SplayNode* root = T;
    search(root, x);

    if (root->data < x) {
        L = root;
        R = root->right;
        if (R) R->parent = nullptr;
        L->right = nullptr;
    } else {
        R = root;
        L = root->left;
        if (L) L->parent = nullptr;
        R->left = nullptr;
    }
}

SplayNode* joinTrees(SplayNode* L, SplayNode* R) {
    if (!L) return R;
    if (!R) return L;
    // 在 L 中把 max splay 到 root
    SplayNode* m = L;
    while (m->right) m = m->right;
    splay(L, m);
    L->right  = R;
    R->parent = L;
    return L;
}

/* ============================================================================
 *  8. Traversals
 * ============================================================================ */
void inorder(SplayNode* node, vector<int>& out) {
    if (!node) return;
    inorder(node->left, out);
    out.push_back(node->data);
    inorder(node->right, out);
}

void preorder(SplayNode* node, vector<int>& out) {
    if (!node) return;
    out.push_back(node->data);
    preorder(node->left,  out);
    preorder(node->right, out);
}

void levelOrder(SplayNode* root) {
    if (!root) { cout << "(empty)\n"; return; }
    queue<SplayNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = (int)q.size();
        while (sz--) {
            SplayNode* n = q.front(); q.pop();
            cout << n->data << " ";
            if (n->left)  q.push(n->left);
            if (n->right) q.push(n->right);
        }
        cout << "\n";
    }
}

/* ============================================================================
 *  9. 視覺化輸出（橫向印出樹）
 *      右子樹在上，左子樹在下，類似 Linux tree 的轉 90 度版本。
 * ============================================================================ */
void printTreeHelper(SplayNode* node, string prefix, bool isRight, bool hasSibling) {
    if (!node) return;
    if (node->right) {
        printTreeHelper(node->right,
                        prefix + (isRight ? "        " : " |      "),
                        true,
                        node->left != nullptr);
    }
    cout << prefix;
    if (node->parent) cout << (isRight ? " /----- " : " \\----- ");
    cout << node->data << "\n";
    if (node->left) {
        printTreeHelper(node->left,
                        prefix + (isRight ? " |      " : "        "),
                        false,
                        false);
    }
    (void)hasSibling;
}

void printTree(SplayNode* root) {
    if (!root) { cout << "  (empty tree)\n"; return; }
    cout << "----------------------------------------\n";
    printTreeHelper(root, "", true, false);
    cout << "----------------------------------------\n";
}

/* ============================================================================
 *  輔助：清除整棵樹
 * ============================================================================ */
void clearTree(SplayNode* node) {
    if (!node) return;
    clearTree(node->left);
    clearTree(node->right);
    delete node;
}

void printInorder(SplayNode* root) {
    vector<int> v;
    inorder(root, v);
    cout << "  Inorder: ";
    for (int x : v) cout << x << " ";
    cout << "\n";
}

/* ============================================================================
 *  Demo 1：逐步插入示範
 * ============================================================================ */
void demoStepByStepInsert() {
    cout << "\n========================================\n";
    cout << "  Demo 1: 逐步插入 10, 20, 30, 40, 25\n";
    cout << "========================================\n";

    SplayNode* root = nullptr;
    int seq[] = {10, 20, 30, 40, 25};

    for (int x : seq) {
        cout << "\n>>> Insert " << x << "（之後 splay 到 root）\n";
        insert(root, x);
        printTree(root);
        printInorder(root);
    }

    clearTree(root);
}

/* ============================================================================
 *  Demo 2：Search 示範（找到 vs 沒找到）
 * ============================================================================ */
void demoSearch() {
    cout << "\n========================================\n";
    cout << "  Demo 2: Search 示範\n";
    cout << "========================================\n";

    SplayNode* root = nullptr;
    int seq[] = {50, 30, 70, 20, 40, 60, 80, 10, 35, 45, 65, 75};
    for (int x : seq) insert(root, x);

    cout << "\n初始樹（依序插入後 splay 的結果）：\n";
    printTree(root);
    printInorder(root);

    cout << "\n>>> Search(35)（存在）\n";
    bool ok = search(root, 35);
    cout << "  found = " << boolalpha << ok << "\n";
    printTree(root);

    cout << "\n>>> Search(55)（不存在）— 應 splay 最接近 55 的節點\n";
    ok = search(root, 55);
    cout << "  found = " << boolalpha << ok << "\n";
    printTree(root);

    cout << "\n>>> Search(80)（存在）\n";
    ok = search(root, 80);
    cout << "  found = " << boolalpha << ok << "\n";
    printTree(root);

    clearTree(root);
}

/* ============================================================================
 *  Demo 3：Delete 示範
 * ============================================================================ */
void demoDelete() {
    cout << "\n========================================\n";
    cout << "  Demo 3: Delete 示範\n";
    cout << "========================================\n";

    SplayNode* root = nullptr;
    int seq[] = {50, 30, 70, 20, 40, 60, 80, 10, 35, 45, 65, 75};
    for (int x : seq) insert(root, x);

    cout << "\n初始樹：\n";
    printTree(root);
    printInorder(root);

    int delSeq[] = {40, 50, 80, 99 /* not exists */};
    for (int x : delSeq) {
        cout << "\n>>> Delete " << x << "\n";
        erase(root, x);
        printTree(root);
        printInorder(root);
    }

    clearTree(root);
}

/* ============================================================================
 *  Demo 4：Split / Join 示範
 * ============================================================================ */
void demoSplitJoin() {
    cout << "\n========================================\n";
    cout << "  Demo 4: Split / Join 示範\n";
    cout << "========================================\n";

    SplayNode* T = nullptr;
    for (int x : {10, 20, 30, 40, 50, 60, 70, 80, 90}) insert(T, x);

    cout << "\n原始樹：\n";
    printTree(T);
    printInorder(T);

    cout << "\n>>> split(T, 50)：分為 L (< 50) 和 R (>= 50)\n";
    SplayNode *L = nullptr, *R = nullptr;
    splitTree(T, 50, L, R);

    cout << "\nL：\n"; printTree(L); printInorder(L);
    cout << "\nR：\n"; printTree(R); printInorder(R);

    cout << "\n>>> join(L, R)：重新合併\n";
    SplayNode* M = joinTrees(L, R);
    printTree(M);
    printInorder(M);

    clearTree(M);
}

/* ============================================================================
 *  Demo 5：互動模式
 * ============================================================================ */
void demoInteractive() {
    cout << "\n========================================\n";
    cout << "  Demo 5: 互動模式\n";
    cout << "  指令：\n"
         << "    i <num>   插入\n"
         << "    s <num>   搜尋\n"
         << "    d <num>   刪除\n"
         << "    p         印出樹\n"
         << "    o         印出 inorder\n"
         << "    l         level-order\n"
         << "    q         離開\n"
         << "========================================\n";

    SplayNode* root = nullptr;
    string line;
    while (true) {
        cout << "\n> ";
        if (!getline(cin, line)) break;
        if (line.empty()) continue;

        stringstream ss(line);
        char op; ss >> op;
        int x;

        if (op == 'q') break;
        else if (op == 'i' && (ss >> x)) {
            insert(root, x);
            printTree(root);
        }
        else if (op == 's' && (ss >> x)) {
            cout << "  found = " << boolalpha << search(root, x) << "\n";
            printTree(root);
        }
        else if (op == 'd' && (ss >> x)) {
            erase(root, x);
            printTree(root);
        }
        else if (op == 'p') {
            printTree(root);
        }
        else if (op == 'o') {
            printInorder(root);
        }
        else if (op == 'l') {
            levelOrder(root);
        }
        else {
            cout << "  unknown command\n";
        }
    }

    clearTree(root);
}

/* ============================================================================
 *  Main
 * ============================================================================ */
int main(int argc, char** argv) {
    cout << "================================================\n";
    cout << "  Splay Tree (伸展樹) — 完整實作 demo\n";
    cout << "  by Sleator & Tarjan, 1985\n";
    cout << "================================================\n";

    demoStepByStepInsert();
    demoSearch();
    demoDelete();
    demoSplitJoin();

    // 加上 --interactive 旗標才進入互動模式
    if (argc > 1 && string(argv[1]) == "--interactive") {
        demoInteractive();
    } else {
        cout << "\n(若想進入互動模式，請使用：./tree_splay --interactive)\n";
    }

    return 0;
}