# 紅黑樹移除節點時的問題與討論
[2022q1 第 18 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz18)
[rbtree-minimal](https://gist.github.com/jserv/3e87c957b577dc46c91d51f94159666c)
* `node->__rb_parent_color` 紀錄 node 的 parent 及 node 的 color
* 程式碼註解中小寫為 red node 大寫為 black node 帶有括號則兩種都有可能 e.g n N (n)
* 以 kernel-scheduler Figure 3.3: data structure: red-black tree 的圖來看

1. 假如 `__rb_erase` 的 node 是 2 的話會進到 case1 , 移除掉的節點是紅色 , 所以 rebalance 會是 NULL 不會進行 `__rb_erase_color` ; 反之 `__rb_erase` 移除的 node 是 31 的話 , 因為移除的 node 是黑色的 , 所以 rebalance 會是 node 34 , `__rb_erase_color` 會進到 if 的 case 4 並 break 出來
- [ ] `__rb_erase`

if (!tmp) {
        /* Case 1: node to erase has no more than 1 child (easy!)
         *
         * Note that if there is one child it must be red due to 5)
         * and node must be black due to 4). We adjust colors locally
         * so as to bypass __rb_erase_color() later on.
         */
        pc = node->__rb_parent_color;
        parent = __rb_parent(pc);
        __rb_change_child(node, child, parent, root);
        if (child) {
            child->__rb_parent_color = pc;
            rebalance = NULL;
        } else // pc 裡紀錄的是 node 的顏色
            rebalance = __rb_is_black(pc) ? parent : NULL;
        tmp = parent;
    }

2. 假如 `__rb_erase` 的 node 是 7 的話會進到 else if 的 case1 , 會將 7 移除並將 2 變為 19 的 leftchild 且顏色改變為 7 的顏色 , rebalance 一樣是 NULL 所以也不會進行 `__rb_erase_color`
- [ ] `__rb_erase`

else if (!child) {
    /* Still case 1, but this time the child is node->rb_left */
    // 將 2 顏色改變為 7 的顏色
    tmp->__rb_parent_color = pc = node->__rb_parent_color;
    parent = __rb_parent(pc);
    // 將從 19 移出的 7 變成 2
    __rb_change_child(node, tmp, parent, root);
    rebalance = NULL;
    tmp = parent;
}

3. 假如 `__rb_erase` 的 node 是 19 的話會進到 Case 2 , rebalance 會是 node 25 , `__rb_erase_color` 會進到 `else` 的 case4 並 break 出去
4. 假如 `__rb_erase` 的 node 是 34 的話會進到 Case 3 , successor 為 49 且不是黑色所以 rebalance 為 NULL
5. `__rb_erase`
* case1 : erase node 最多只有一個 child , 若只有一個 child 就不用 rebalance , 若沒有 child 則看 erase node 是否為黑色來決定要不要 rebalance , rebalance node 為 erase node 的 parent
* case2 : erase node 有兩個 child 且 rightchild->left == NULL , erase node 會被 right child 取代 , 看 successor->right 是否存在或 successor 是否為黑色來決定要不要 rebalance , rebalance node 為 sucessor (即替換掉 erase node 的 node)
* case3 : erase node 有兩個 child 且 rightchild->left != NULL , erase node 會被 right child 的 leftmost under node 取代 , 看 successor->right 是否存在或 successor 是否為黑色來決定要不要 rebalance , rebalance node 為 sucessor (即替換掉 erase node 的 node) 的 parent
6. `__rb_erase_color`
* 會進到 if 的情況：
* 迴圈第一次 parent->rb_right != null
* 經過 Case 2 後且需要在 rebalance , node 為 node 的 parent 的 leftchild
* 此時 sibling 為 parent->rightchild
* case1: sibling 為紅色
* case2: sibling 為黑色，並且 sibling 兩個child 皆為黑色
* case3: sibling 為黑色，並且 sibling rightchild 為黑色，leftchild 為紅色
* case4: sibling 為黑色，並且 sibling rightchild 為紅色
* 會進到 else 的情況：
* 迴圈第一次 parent->rb_right == null , 也就是 rebalance node 沒有 rightchild 的情況 (e.g 上面舉例的 19)
* 經過 Case 2 後且需要在 rebalance , node 為 node 的 parent 的 rightchild
* 此時 sibling 為 parent->leftchild
* case1: sibling 為紅色
* case2: sibling 為黑色，並且 sibling 兩個 child 皆為黑色
* case3: sibling 為黑色，並且 sibling leftchild 為黑色，rightchild 為紅色
* case4: sibling 為黑色，並且 sibling leftchild 為紅色

7. 假如 `__rb_erase` 的 node 是 27 , 因為兩個 child 都有且 rightchild->left != NULL , 所以進到 Case 3 , successor 為 rightchild 的 leftmost under node(31) 並取代 erase node(27), 因 successor->right 不存在且 successor 為黑色要進行 rebalance , rebalance node 為 successor 的 parent(34) , 並傳入 `__rb_erase_color` , 因 rightchild 存在會進入 if statement , sibling 為黑色 65 又 sibling 的兩個 child 皆為紅色所以只會進到 case4 , 並完成修正

參考資料:
https://codertw.com/%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80/743044/
http://alrightchiu.github.io/SecondRound/red-black-tree-deleteshan-chu-zi-liao-yu-fixupxiu-zheng.html