# 【資工考研】DS: Binary Tree (5) Red-Black Tree + Splay Tree

## Red-Black Tree

我們[前面](https://hackmd.io/@RyoukiWei/binary_tree_4)討論到 AVL tree 作為一種平衡的二元搜尋樹，改善了二元搜尋樹的痛點
紅黑樹同 AVL tree ，也是一種平衡的二元搜尋樹，但 AVL tree 是透過時刻控制樹高來達到平衡，而紅黑樹則很特別，它是透過控制節點顏色來平衡的

紅黑樹遵守：

1. 其節點以顏色區分，不是紅色就是黑色
2. root 必定是黑色
3. Nil 必定是黑色
4. 任一 path 上不可出現連續的紅色節點
5. root 到不同 leaf 之 path 上皆有相同數目的黑色節點 (其平衡的意義所在)

    template <typename T>
    struct RBNode
    {
        T data;
        RBNode *left;
        RBNode *right;
        RBNode *parent;
        bool isRed;

        // All newly created nodes have a default color of red.
        RBNode(const T &val) : data(val), left(nullptr), right(nullptr), parent(nullptr), isRed(true) {}
    };

## Insert

我們先執行 BST 的插入方法，再對其做調整使之遵守 RB tree 的規則 (bottom up)
或著我們邊找插入位置邊調整 (top down)

想法基本上是：

1. 當發現某節點的兩子點為紅色時進行 color change (該節點變成紅色，兩子點變成黑色)，檢查此刻有沒有出現連續的紅色節點 (該節點與其 parent 皆紅)，若有則執行 rotation
2. 插入的新節點都先標成紅色 (可以發現我們 `RBNode` 的 constructor 是設定節點新建時顏色為紅色)
3. 如果有連續的紅色，則執行 rotation
4. root 顏色一律改成黑色

> [!Important]
> 其中第一步跟第三步可能這兩步都不會執行 rotation ，或著頂多其中一步會做一次 rotation
> 這是 RB tree 相較 AVL tree 的優勢所在，AVL tree 的 `erase` 可能會做 $O(\lg n)$ 次的 rotation ，但 RB tree 無論是 `insert` 還是 `erase` 都只會有 $O(1)$ 次 rotation

> [!Tip]
> RB tree 的 rotation 跟 AVL tree 的很像，基本上 AVL tree 那邊懂了，這邊也不成問題
> 只是 RB tree 是看顏色，AVL tree 看 balance factor
> RB tree 這邊的 LL, RR, LR, RL 判斷是自己跟父節點都紅色之下，從祖父節點看來

以下示範演算法課本提供的 bottom up 插入方法
下方是我們的調整方法：

我們要先判斷該節點的父節點 (`parent`) 是祖父的左子點還是右子點
因為 LL, RR, LR, RL 就是先看父節點位置再看該節點位置嘛
基本上 (LL, LR) 處理跟 (RR, RL) 的處理邏輯是一模一樣的，所以你會看到下面的 code 呈現上下雷同的感覺，我們就談 (LL, LR) 的處理：

case 1: 祖父的兩子點為紅色 (`parent` 跟 `uncle` 都是紅色)，因為 `parent` 本來就是要紅色才需要調整，所以其實就是看 `uncle` 是不是也紅色

case 2: 連續兩紅色節點的處理

        /**
         * @brief In order to fix Red-Black Tree properties after insertion.
         */
        void insertFixup(Node *node)
        {
            while (node != root && node->parent->isRed)
            {
                Node *parent = node->parent;
                Node *grandparent = parent->parent;

                if (parent == grandparent->left)
                {
                    Node *uncle = grandparent->right;
                    // case 1
                    if (uncle && uncle->isRed)
                    {
                        // color change
                        parent->isRed = false;
                        uncle->isRed = false;
                        grandparent->isRed = true;
                        node = grandparent;
                    }
                    // case 2
                    else
                    {
                        // LR -> LL
                        if (node == parent->right)
                        {
                            node = parent;
                            leftRotate(node);
                        }

                        // for LL
                        parent->isRed = false;
                        grandparent->isRed = true;
                        rightRotate(grandparent);
                    }
                }
                else
                {
                    Node *uncle = grandparent->left;
                    // case 3
                    if (uncle && uncle->isRed)
                    {
                        parent->isRed = false;
                        uncle->isRed = false;
                        grandparent->isRed = true;
                        node = grandparent;
                    }
                    // case 4
                    else
                    {
                        // RL -> RR
                        if (node == parent->left)
                        {
                            node = parent;
                            rightRotate(node);
                        }

                        // for RR
                        parent->isRed = false;
                        grandparent->isRed = true;
                        leftRotate(grandparent);
                    }
                }
            }

            root->isRed = false; // Ensure root is black.
        }

        void leftRotate(Node *x)
        {
            // y will become the new root of the subtree.
            Node *y = x->right;
            x->right = y->left;
            if (y->left != exNode)
                y->left->parent = x;
            y->parent = x->parent;

            if (!x->parent) // root does not have parent
                root = y;
            else if (x == x->parent->left)
                x->parent->left = y;
            else
                x->parent->right = y;

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

        void rightRotate(Node *y)
        {
            // x will become the new root of the subtree.
            Node *x = y->left;
            y->left = x->right;
            if (x->right != exNode)
                x->right->parent = y;
            x->parent = y->parent;

            if (!y->parent) // root does not have parent
                root = x;
            else if (y == y->parent->right)
                y->parent->right = x;
            else
                y->parent->left = x;

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

僅看插入的實現就相對簡單多了，難的都在 `insertFixup` ：

        /**
         * @brief Inserts a value into the Red-Black Tree.
         *
         * @param val The value to be inserted.
         * @return A pair where the first element is a pointer to the node containing the value,
         *         and the second element is a boolean indicating whether the insertion was successful.
         */
        std::pair<Node *, bool> insert(const T &val)
        {
            Node *curr = root;
            Node *parent = nullptr;

            // Just BST insert
            while (curr != exNode)
            {
                parent = curr;
                if (val == curr->data)
                    return {curr, false}; // already exist
                curr = val < curr->data ? curr->left : curr->right;
            }

            Node *node = new Node(val);
            node->left = node->right = exNode;
            node->parent = parent;

            if (!parent)
                root = node;
            else if (val < parent->data)
                parent->left = node;
            else
                parent->right = node;

            if (!node->parent)
            {
                node->isRed = false;
                return {node, true};
            }

            if (!node->parent->parent)
                return {node, true};

            insertFixup(node);
            return {node, true};
        }

### Erase

        /**
         * @brief Removes a value from the Red-Black Tree.
         *
         * @param val The value to be removed.
         * @return The number of nodes removed (0 if the value is not found, 1 otherwise).
         */
        size_t erase(const T &val)
        {
            Node *node = find(val);
            if (node == exNode)
                return 0; // Nothing found to be removed.

            Node *temp, *child;
            temp = (node->left == exNode || node->right == exNode)
                       ? node
                       : findSuccssor(node);

            child = temp->left != exNode ? temp->left : temp->right;
            child->parent = temp->parent;

            if (!temp->parent) // if removing root
                root = child;
            else if (temp = temp->parent->left)
                temp->parent->left = child;
            else
                temp->parent->right = child;

            if (temp != node) // copy the data if temp is a successor
                node->data = temp->data;

            if (!temp->isRed)
                delFixup(child);

            delete temp;
            return 1;
        }

        void delFixup(Node *node)
        {
            while (node != root && !node->isRed)
            {
                Node *parent = node->parent;
                if (node == parent->left)
                {
                    Node *sibling = parent->right;
                    if (sibling->isRed)
                    {
                        sibling->isRed = false;
                        parent->isRed = true;
                        leftRotate(parent);
                        sibling = parent->right;
                    }

                    if (!sibling->left->isRed && !sibling->right->isRed)
                    {
                        sibling->isRed = true;
                        node = node->parent;
                    }
                    else
                    {
                        if (!sibling->right->isRed)
                        {
                            sibling->left->isRed = false;
                            sibling->isRed = true;
                            rightRotate(sibling);
                            sibling = parent->right;
                        }

                        sibling->isRed = parent->isRed;
                        parent->isRed = false;
                        sibling->right->isRed = false;
                        leftRotate(parent);
                        node = root;
                    }
                }
                else
                {
                    Node *sibling = parent->left;
                    if (sibling->isRed)
                    {
                        sibling->isRed = false;
                        parent->isRed = true;
                        rightRotate(parent);
                        sibling = parent->left;
                    }

                    if (!sibling->left->isRed && !sibling->right->isRed)
                    {
                        sibling->isRed = true;
                        node = node->parent;
                    }
                    else
                    {
                        if (!sibling->left->isRed)
                        {
                            sibling->right->isRed = false;
                            sibling->isRed = true;
                            leftRotate(sibling);
                            sibling = parent->left;
                        }

                        sibling->isRed = parent->isRed;
                        parent->isRed = false;
                        sibling->left->isRed = false;
                        rightRotate(parent);
                        node = root;
                    }
                }
            }

            node->isRed = false;
        }

### 討論

> [!Important]
> 定義 black height $\mathrm{bh}(x) = x$ 到 leaf 之 path 上不含 $x$ 的黑色節點數目
> 則任意 $x$ 的子樹至少包含 $2^{\mathrm{bh}(x)} - 1$ 個 internal nodes

> [!Important]
> A RB tree with $n$ internal nodes has at most $\left\lceil 2\cdot \lg (n+1) \right\rceil$ tree height

根據 RB tree 的定義可知 $\mathrm{bh}(\mathrm{root}) \ge \frac{h}{2}$
$\Rightarrow n \ge 2^{\frac{h}{2}} - 1$
$\therefore h\le \left\lceil 2\cdot \lg (n+1) \right\rceil$

### 從 2-3-4 Tree 到 RB Tree

如果我們重新定義 RB tree 的顏色規則，其實 2-3-4 tree 是可以轉換成 RB tree 的：

1. link 的顏色非黑即紅
2. 若此 link 在原 2-3-4 tree 存在，標為黑色；反之，標為紅色
3. 任意 path 上不可出現連續的紅色 link
4. root 到不同 leaf 上的 path 上存在相同數目的黑色 link


<center>2-3-4 tree 轉換成 RB tree</center>

我們進一步探討：

在 2-3-4 tree 中我[們說過每個 external nodes 皆在同個 level ，這是其平衡的意義所在](https://hackmd.io/@RyoukiWei/binary_tree_4?stext=5828%3A52%3A0%3A1737530378%3A37Tg5H)，對應的其實就是 RB tree 中 root 到 leaf 的 path 上有相同的黑色節點數量這件事，當然，我們在這邊轉換 2-3-4 tree 成 RB tree 塗色的是 link ，但不影響我們意會到其中的奧妙

如果 2-3-4 tree 全都是 2-Node ，則轉換出來的 RB tree 高 $\lg (n+1)$
如果全是 4-Node ，則轉換出來的 RB tree 高 $2\lg (n+1)$

## Splay Tree

Splay tree 也是 BST，它 worst case 仍會達 $O(n)$ ，但它的 amortized cost 是 $O(\lg n)$ (均攤下， worst case 頂多 $O(\lg n)$)

AVL tree 跟 RB tree 都仰賴在節點上記錄一些訊息用以嚴格地保持樹平衡
而 splay tree 不需要冗餘的資料，我們只要每次操作都對 splay 起點執行 `splay` 就好
在平攤分析之下，splay tree 的時間複雜度亦與 AVL tree 和 RB tree 表現相當

每次的 `splay` 操作是其最重要的靈魂，它會將 splay 起點變成 root
畢竟我們是二元**搜尋**樹，對於查找頻率高的元素，讓它越靠近 root 不應該效率會更好嗎？

不過 splay tree 除了還是有機會變非常 skewed 外，還有一個大缺點：

即便我們的操作是 read-only ，例如 `find` ，splay tree 的樹結構仍會改變
這使得 splay tree 在 multi-thread 之類的環境會顯得相當複雜，不易維護
別說 multi-thread ，原本幫 BST 寫 iterator 就不容易了，要你幫 splay tree 寫 iterator 才是真的頭痛至極 (大概是不適合還設計 iterator 給它啦)

`splay` 操作基本上我們分只看兩點跟看三點兩大 cases

只看兩點的情況很簡單，把 splay 起點往上變 root 就好
看三點的話，就還要同時維持 BST 的大小關係，但一樣是把 splay 起點變 root ，相當樸實無華

當然，人家有定義這個 `splay` 分 `zig` 跟 `zag` 兩種 rotation 方式，就好像 AVL tree 他們有定義 left rotation 跟 right rotation
不過我想這邊我們不必細聊太多
我發現[中文 wiki](https://zh.wikipedia.org/zh-tw/%E4%BC%B8%E5%B1%95%E6%A0%91) 可以參考，真的有興趣可以去看

## 【資工考研】DS: Binary Tree 全系列

- [【資工考研】DS: Binary Tree (1)](https://hackmd.io/@RyoukiWei/binary_tree_1)
- [【資工考研】DS: Binary Tree (2)](https://hackmd.io/@RyoukiWei/binary_tree_2)
- [【資工考研】DS: Binary Tree (3)](https://hackmd.io/@RyoukiWei/binary_tree_3)
- [【資工考研】DS: Binary Tree (4)](https://hackmd.io/@RyoukiWei/binary_tree_4)
- [【資工考研】DS: Binary Tree (5)](https://hackmd.io/@RyoukiWei/binary_tree_5)