tree_red_black.cpp

/*
 * ============================================================================
 *  Red-Black Tree — 完整 C++ 實作
 *  File: tree_red_black.cpp
 *
 *  Red-Black Tree 是一種自平衡 BST，透過「顏色規則」保證 h ≤ 2 log₂(N+1)。
 *  C++ STL 的 std::set / std::map 底層就是 Red-Black Tree。
 *
 *  五條規則:
 *    1. 每個節點是紅色或黑色
 *    2. Root 是黑色
 *    3. NIL (空節點) 是黑色
 *    4. 紅色節點的 children 都是黑色 (no red-red)
 *    5. 從任一節點到所有後代 NIL 路徑上的黑色節點數相同 (black-height)
 *
 *  涵蓋:
 *    1.  節點結構 (含顏色、parent 指標)
 *    2.  左旋 / 右旋
 *    3.  Insert + 插入修復 (3 cases)
 *    4.  Delete + 刪除修復 (4 cases)
 *    5.  Search / FindMin / FindMax
 *    6.  Inorder 遍歷
 *    7.  視覺化輸出 (含顏色標記)
 *    8.  驗證五條規則
 *
 *  Compile: g++ -std=c++11 -Wall -o tree_red_black tree_red_black.cpp
 * ============================================================================
 */

#include <iostream>
#include <string>
#include <queue>

using namespace std;

/* ============================================================================
 *  1. 節點結構
 *
 *  與 AVL 不同，RBT 用 parent 指標（方便向上回溯修復），
 *  且用一個 sentinel NIL 節點代替所有 nullptr（簡化邊界判斷）。
 * ============================================================================ */

enum Color { RED, BLACK };

struct RBNode {
    int data;
    Color color;
    RBNode* left;
    RBNode* right;
    RBNode* parent;

    RBNode(int val, Color c, RBNode* nil)
        : data(val), color(c), left(nil), right(nil), parent(nil) {}
};

class RedBlackTree {
private:
    RBNode* root;
    RBNode* NIL;  // sentinel 節點，所有 leaf 都指向它

    /* ========================================================================
     *  2. 左旋 / 右旋
     *
     *  旋轉是 RBT 修復的核心操作，和 AVL 一樣改變父子關係但保持 BST 性質。
     *  因為有 parent 指標，旋轉需要同時更新三組指標。
     * ======================================================================== */

    /*
     * 左旋 (Left Rotate) — 以 x 為軸
     *
     *     x                 y
     *    / \               / \
     *   a   y      →     x   c
     *      / \          / \
     *     b   c        a   b
     */
    void rotateLeft(RBNode* x) {
        RBNode* y = x->right;     // y 是 x 的右子

        // Step 1: y 的左子 b 變成 x 的右子
        x->right = y->left;
        if (y->left != NIL) {
            y->left->parent = x;
        }

        // Step 2: y 取代 x 的位置（更新 x 的 parent）
        y->parent = x->parent;
        if (x->parent == NIL) {
            root = y;              // x 是 root → y 成為新 root
        } else if (x == x->parent->left) {
            x->parent->left = y;   // x 是左子 → y 成為左子
        } else {
            x->parent->right = y;  // x 是右子 → y 成為右子
        }

        // Step 3: x 變成 y 的左子
        y->left = x;
        x->parent = y;
    }

    /*
     * 右旋 (Right Rotate) — 以 y 為軸（左旋的鏡像）
     *
     *       y              x
     *      / \            / \
     *     x   c    →     a   y
     *    / \                / \
     *   a   b              b   c
     */
    void rotateRight(RBNode* y) {
        RBNode* x = y->left;

        y->left = x->right;
        if (x->right != NIL) {
            x->right->parent = y;
        }

        x->parent = y->parent;
        if (y->parent == NIL) {
            root = x;
        } else if (y == y->parent->left) {
            y->parent->left = x;
        } else {
            y->parent->right = x;
        }

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

    /* ========================================================================
     *  3. 插入修復 (Insert Fixup)
     *
     *  新節點 z 塗紅色插入後，可能違反規則 4 (red-red)。
     *  修復分三種情況（父親是祖父的左子時；右子時為鏡像）：
     *
     *  Case 1: Uncle 是紅色 → 重新著色，z 上移到祖父
     *  Case 2: Uncle 是黑色，z 是內側 child → 旋轉成 Case 3
     *  Case 3: Uncle 是黑色，z 是外側 child → 旋轉+換色，完成
     * ======================================================================== */
    void insertFixup(RBNode* z) {
        // 當 z 的父親是紅色 → 違反規則 4 → 需要修復
        while (z->parent->color == RED) {
            if (z->parent == z->parent->parent->left) {
                // 父親是祖父的左子
                RBNode* uncle = z->parent->parent->right;

                if (uncle->color == RED) {
                    // Case 1: Uncle 是紅色
                    // → 父親和叔叔都變黑，祖父變紅，z 上移到祖父繼續檢查
                    z->parent->color = BLACK;
                    uncle->color = BLACK;
                    z->parent->parent->color = RED;
                    z = z->parent->parent;
                } else {
                    if (z == z->parent->right) {
                        // Case 2: Uncle 黑色，z 是右子（LR 形狀）
                        // → 對父親左旋，轉成 Case 3
                        z = z->parent;
                        rotateLeft(z);
                    }
                    // Case 3: Uncle 黑色，z 是左子（LL 形狀）
                    // → 父親變黑，祖父變紅，對祖父右旋
                    z->parent->color = BLACK;
                    z->parent->parent->color = RED;
                    rotateRight(z->parent->parent);
                }
            } else {
                // 鏡像：父親是祖父的右子
                RBNode* uncle = z->parent->parent->left;

                if (uncle->color == RED) {
                    // Case 1 鏡像
                    z->parent->color = BLACK;
                    uncle->color = BLACK;
                    z->parent->parent->color = RED;
                    z = z->parent->parent;
                } else {
                    if (z == z->parent->left) {
                        // Case 2 鏡像 (RL 形狀)
                        z = z->parent;
                        rotateRight(z);
                    }
                    // Case 3 鏡像 (RR 形狀)
                    z->parent->color = BLACK;
                    z->parent->parent->color = RED;
                    rotateLeft(z->parent->parent);
                }
            }
        }
        // 規則 2: root 永遠是黑色
        root->color = BLACK;
    }

    /* ========================================================================
     *  4. 刪除修復 (Delete Fixup)
     *
     *  當刪除一個黑色節點後，替代位置 x 可能「多一層黑」（double-black）。
     *  修復分四種情況（x 是父親的左子時；右子時為鏡像）：
     *
     *  Case 1: Sibling 是紅色 → 換色+旋轉 → 轉成 Case 2/3/4
     *  Case 2: Sibling 黑色，兩個 children 都黑 → Sibling 變紅，x 上移
     *  Case 3: Sibling 黑色，近側 child 紅、遠側黑 → 旋轉 → 轉成 Case 4
     *  Case 4: Sibling 黑色，遠側 child 紅 → 旋轉+換色 → 完成
     * ======================================================================== */
    void deleteFixup(RBNode* x) {
        while (x != root && x->color == BLACK) {
            if (x == x->parent->left) {
                RBNode* s = x->parent->right;  // sibling

                if (s->color == RED) {
                    // Case 1: Sibling 紅色
                    s->color = BLACK;
                    x->parent->color = RED;
                    rotateLeft(x->parent);
                    s = x->parent->right;
                }

                if (s->left->color == BLACK && s->right->color == BLACK) {
                    // Case 2: Sibling 黑色，兩個 children 都黑
                    s->color = RED;
                    x = x->parent;
                } else {
                    if (s->right->color == BLACK) {
                        // Case 3: 近側紅、遠側黑
                        s->left->color = BLACK;
                        s->color = RED;
                        rotateRight(s);
                        s = x->parent->right;
                    }
                    // Case 4: 遠側紅
                    s->color = x->parent->color;
                    x->parent->color = BLACK;
                    s->right->color = BLACK;
                    rotateLeft(x->parent);
                    x = root;  // 完成
                }
            } else {
                // 鏡像
                RBNode* s = x->parent->left;

                if (s->color == RED) {
                    s->color = BLACK;
                    x->parent->color = RED;
                    rotateRight(x->parent);
                    s = x->parent->left;
                }

                if (s->right->color == BLACK && s->left->color == BLACK) {
                    s->color = RED;
                    x = x->parent;
                } else {
                    if (s->left->color == BLACK) {
                        s->right->color = BLACK;
                        s->color = RED;
                        rotateLeft(s);
                        s = x->parent->left;
                    }
                    s->color = x->parent->color;
                    x->parent->color = BLACK;
                    s->left->color = BLACK;
                    rotateRight(x->parent);
                    x = root;
                }
            }
        }
        x->color = BLACK;
    }

    // 用 v 取代 u 在樹中的位置
    void transplant(RBNode* u, RBNode* v) {
        if (u->parent == NIL) {
            root = v;
        } else if (u == u->parent->left) {
            u->parent->left = v;
        } else {
            u->parent->right = v;
        }
        v->parent = u->parent;
    }

    RBNode* minimum(RBNode* node) {
        while (node->left != NIL) {
            node = node->left;
        }
        return node;
    }

    /* ========================================================================
     *  視覺化 & 驗證 (private helpers)
     * ======================================================================== */

    void printHelper(RBNode* node, const string& prefix, bool isLeft) {
        if (node == NIL) return;

        if (node->right != NIL) {
            printHelper(node->right, prefix + (isLeft ? "│   " : "    "), false);
        }

        cout << prefix;
        cout << (isLeft ? "└── " : "┌── ");
        cout << node->data << (node->color == RED ? "(R)" : "(B)") << endl;

        if (node->left != NIL) {
            printHelper(node->left, prefix + (isLeft ? "    " : "│   "), true);
        }
    }

    void inorderHelper(RBNode* node) {
        if (node == NIL) return;
        inorderHelper(node->left);
        cout << node->data << (node->color == RED ? "(R) " : "(B) ");
        inorderHelper(node->right);
    }

    // 驗證規則 5: 從 node 到所有 NIL 的 black-height 是否一致
    // 回傳 -1 表示不一致
    int verifyBlackHeight(RBNode* node) {
        if (node == NIL) return 1;

        int leftBH = verifyBlackHeight(node->left);
        int rightBH = verifyBlackHeight(node->right);

        if (leftBH == -1 || rightBH == -1 || leftBH != rightBH) return -1;

        return leftBH + (node->color == BLACK ? 1 : 0);
    }

    // 驗證規則 4: 無 red-red
    bool verifyNoRedRed(RBNode* node) {
        if (node == NIL) return true;
        if (node->color == RED) {
            if (node->left->color == RED || node->right->color == RED) {
                return false;
            }
        }
        return verifyNoRedRed(node->left) && verifyNoRedRed(node->right);
    }

    void destroyHelper(RBNode* node) {
        if (node == NIL) return;
        destroyHelper(node->left);
        destroyHelper(node->right);
        delete node;
    }

public:
    RedBlackTree() {
        NIL = new RBNode(0, BLACK, nullptr);
        NIL->left = NIL->right = NIL->parent = NIL;
        root = NIL;
    }

    ~RedBlackTree() {
        destroyHelper(root);
        delete NIL;
    }

    /* ========================================================================
     *  3. Insert（插入）
     *
     *  1. 像普通 BST 插入，新節點塗紅色
     *  2. 呼叫 insertFixup 修復可能的 red-red 違規
     * ======================================================================== */
    void insert(int key) {
        RBNode* z = new RBNode(key, RED, NIL);

        // 標準 BST 插入
        RBNode* y = NIL;
        RBNode* x = root;
        while (x != NIL) {
            y = x;
            if (z->data < x->data) {
                x = x->left;
            } else if (z->data > x->data) {
                x = x->right;
            } else {
                delete z;  // 不允許重複
                return;
            }
        }

        z->parent = y;
        if (y == NIL) {
            root = z;
        } else if (z->data < y->data) {
            y->left = z;
        } else {
            y->right = z;
        }

        // 修復 RBT 性質
        insertFixup(z);
    }

    /* ========================================================================
     *  4. Delete（刪除）
     *
     *  1. 找到要刪除的節點
     *  2. 像 BST 刪除（三種情況）
     *  3. 若刪除的是黑色 → deleteFixup
     * ======================================================================== */
    void deleteKey(int key) {
        RBNode* z = root;
        while (z != NIL) {
            if (key < z->data) z = z->left;
            else if (key > z->data) z = z->right;
            else break;
        }
        if (z == NIL) return;

        RBNode* y = z;
        Color yOriginalColor = y->color;
        RBNode* x;

        if (z->left == NIL) {
            // Case 1 & 2a: 沒有左子
            x = z->right;
            transplant(z, z->right);
        } else if (z->right == NIL) {
            // Case 2b: 沒有右子
            x = z->left;
            transplant(z, z->left);
        } else {
            // Case 3: 兩個 children → 找中序後繼
            y = minimum(z->right);
            yOriginalColor = y->color;
            x = y->right;

            if (y->parent == z) {
                x->parent = y;
            } else {
                transplant(y, y->right);
                y->right = z->right;
                y->right->parent = y;
            }

            transplant(z, y);
            y->left = z->left;
            y->left->parent = y;
            y->color = z->color;
        }

        delete z;

        // 只有當刪除的節點是黑色時才需要修復
        if (yOriginalColor == BLACK) {
            deleteFixup(x);
        }
    }

    /* ========================================================================
     *  5. Search / FindMin / FindMax
     * ======================================================================== */
    bool search(int key) {
        RBNode* node = root;
        while (node != NIL) {
            if (key == node->data) return true;
            if (key < node->data) node = node->left;
            else node = node->right;
        }
        return false;
    }

    int findMin() {
        RBNode* node = minimum(root);
        return node->data;
    }

    int findMax() {
        RBNode* node = root;
        while (node->right != NIL) node = node->right;
        return node->data;
    }

    /* ========================================================================
     *  6. Inorder 遍歷（排序輸出）
     * ======================================================================== */
    void inorder() {
        inorderHelper(root);
        cout << endl;
    }

    /* ========================================================================
     *  7. 視覺化輸出
     * ======================================================================== */
    void printTree() {
        if (root == NIL) {
            cout << "(empty tree)" << endl;
            return;
        }
        printHelper(root, "", true);
    }

    /* ========================================================================
     *  8. 驗證 RBT 性質
     * ======================================================================== */
    bool verify() {
        // 規則 2: root 是黑色
        if (root->color != BLACK) {
            cout << "VIOLATION: Root is not black!" << endl;
            return false;
        }
        // 規則 4: 無 red-red
        if (!verifyNoRedRed(root)) {
            cout << "VIOLATION: Red-red detected!" << endl;
            return false;
        }
        // 規則 5: black-height 一致
        if (verifyBlackHeight(root) == -1) {
            cout << "VIOLATION: Black-height inconsistent!" << endl;
            return false;
        }
        return true;
    }
};

/* ============================================================================
 *  主程式
 * ============================================================================ */
int main() {
    cout << "============================================" << endl;
    cout << "  Red-Black Tree Complete Demo" << endl;
    cout << "============================================\n" << endl;

    RedBlackTree rbt;

    // ── 逐步插入 ──
    cout << "--- Insert: 10, 20, 30, 15, 25, 5, 1 ---\n" << endl;
    int keys[] = {10, 20, 30, 15, 25, 5, 1};
    for (int k : keys) {
        cout << "Insert " << k << ":" << endl;
        rbt.insert(k);
        rbt.printTree();
        cout << "  Valid RBT: " << (rbt.verify() ? "YES" : "NO") << "\n" << endl;
    }

    // ── Inorder ──
    cout << "--- Inorder (sorted with colors) ---" << endl;
    rbt.inorder();
    cout << endl;

    // ── Search ──
    cout << "--- Search ---" << endl;
    cout << "search(15) = " << (rbt.search(15) ? "true" : "false") << endl;
    cout << "search(99) = " << (rbt.search(99) ? "true" : "false") << endl;
    cout << endl;

    // ── FindMin / FindMax ──
    cout << "--- FindMin / FindMax ---" << endl;
    cout << "Min = " << rbt.findMin() << endl;
    cout << "Max = " << rbt.findMax() << endl;
    cout << endl;

    // ── 更多插入 ──
    cout << "--- Insert more: 40, 50, 35, 28 ---\n" << endl;
    int more[] = {40, 50, 35, 28};
    for (int k : more) {
        rbt.insert(k);
    }
    rbt.printTree();
    cout << "  Valid RBT: " << (rbt.verify() ? "YES" : "NO") << "\n" << endl;

    // ── 刪除 ──
    cout << "--- Delete ---\n" << endl;

    cout << "Delete 1 (leaf):" << endl;
    rbt.deleteKey(1);
    rbt.printTree();
    cout << "  Valid RBT: " << (rbt.verify() ? "YES" : "NO") << "\n" << endl;

    cout << "Delete 20 (internal, two children):" << endl;
    rbt.deleteKey(20);
    rbt.printTree();
    cout << "  Valid RBT: " << (rbt.verify() ? "YES" : "NO") << "\n" << endl;

    cout << "Delete 30 (another internal):" << endl;
    rbt.deleteKey(30);
    rbt.printTree();
    cout << "  Valid RBT: " << (rbt.verify() ? "YES" : "NO") << "\n" << endl;

    cout << "--- Final Inorder ---" << endl;
    rbt.inorder();

    cout << "\n============================================" << endl;
    cout << "  Done." << endl;
    cout << "============================================" << endl;

    return 0;
}