# 2023q1 Homework4 (quiz4)
contributed by < `Korin777` >

> [測驗題目](https://hackmd.io/@sysprog/linux2023-quiz4)

## 測驗三
### `RB_LOG2_MAX_NODES`
`node_t` 的大小為 `sizeof(void*) * 4` 所以 node 最多有 $$\frac{1 << (sizeof(void *) << 3)} {(sizeof(void*) * 4)}$$ 取 `log2` 可以得到 `RB_LOG2_MAX_MEM_BYTES - log2(sizeof(void*)*2) - 1`，若 `sizeof(void*) == 8` 就會是 `RB_LOG2_MAX_MEM_BYTES - 4 - 1`
### `tree_insert`
這裡透過 `path` 來記錄插入節點的所有祖先節點，所以節點不須記錄自己的親代節點也能在插入後向上修復紅黑數，遇到黑色節點就可以停下，因為只有紅色節點可能會違反規則

if (pathp->less) {                                                \
    x_type *left = pathp[1].node;                                 \
    rbtn_left_set(x_type, x_field, cnode, left);                  \
    if (!rbtn_red_get(x_type, x_field, left)) /* 黑節點 */                  \
        return;                                                   \
    x_type *leftleft = rbtn_left_get(x_type, x_field, left);      \
    if (leftleft && rbtn_red_get(x_type, x_field, leftleft)) { /* 紅色相鄰 */   \
        /* Fix up 4-node. */                                      \
        x_type *tnode;                                            \
        rbtn_black_set(x_type, x_field, leftleft);                \
        rbtn_rotate_right(x_type, x_field, cnode, tnode);         \
        cnode = tnode;                                            \
    }                                                             \
} else {                                                          \
    x_type *right = pathp[1].node;                                \
    rbtn_right_set(x_type, x_field, cnode, right);                \
    if (!rbtn_red_get(x_type, x_field, right))                    \
        return;                                                   \
    x_type *left = rbtn_left_get(x_type, x_field, cnode);         \
    if (left && rbtn_red_get(x_type, x_field, left)) {            \
        /* Split 4-node. */                                       \
        rbtn_black_set(x_type, x_field, left);                    \
        rbtn_black_set(x_type, x_field, right);                   \
        rbtn_red_set(x_type, x_field, cnode);                     \
    } else {                                                      \
        /* Lean left. */                                          \
        x_type *tnode;                                            \
        bool tred = rbtn_red_get(x_type, x_field, cnode);         \
        rbtn_rotate_left(x_type, x_field, cnode, tnode);          \
        rbtn_color_set(x_type, x_field, tnode, tred);             \
        rbtn_red_set(x_type, x_field, cnode);                     \
        cnode = tnode;                                            \
    }                                                             \
} 

第 7 行修復紅色相鄰的情況，將 `cnode` 左旋並將 `leftleft` 變為黑色讓路徑上的黑色節點數相同

digraph BST {
    graph[ordering="out"]
    node [shape=circle, fixedsize=true, style=filled,width=.8]
    
    left,leftleft[fillcolor=red]
    
    null,null1[fontsize=0,color=transparent] 
    cnode -> left
    cnode -> null[color=transparent]
    left -> leftleft
    left -> null1[color=transparent]
    
    fix_left[fillcolor=red]
    
    fix_left -> fix_leftleft
    fix_left -> fix_cnode
    
}

第 15 行讓紅黑數是左傾的，將 `cnode` 右旋並將 `cnode` 設為紅色 `right` 的顏色則要跟 `cnode` 一樣確保路徑上的黑色節點數相同
這裡做完可能會有紅色相鄰的情況，會在下一步透過上面或下面的方法修復

digraph BST {
    graph[ordering="out"]
    node [shape=circle, fixedsize=true, style=filled,width=.8]
    
    right[fillcolor=red]
    cnode[fillcolor=white]
    null,null1[fontsize=0,color=transparent] 
    cnode -> null[color=transparent]
    cnode -> right

    
    fix_cnode[fillcolor=red]
    fix_right[fillcolor=white]
    fix_right -> fix_cnode
    fix_right -> null1[color=transparent]
    
}

第 20 行將顏色翻轉，這個操作既不會改變路徑上黑色節點的數量又可以修復紅色相鄰的情況

digraph BST {
    graph[ordering="out"]
    node [shape=circle, fixedsize=true, style=filled,width=.8]
    
    left,right[fillcolor=red]
    
    cnode -> left
    cnode -> right

    
    fix_cnode[fillcolor=red]
    
    fix_cnode -> fix_left
    fix_cnode -> fix_right
    
}

### `sum_subtree`

static int sum_subtree(node_t *node)
{
    int result = 0;
    while (node) {
        node_t *pre;
        if (!rbtn_left_get(node_t, link, node))
            goto do_print;
        for (pre = rbtn_left_get(node_t, link, node);
             rbtn_right_get(node_t, link, pre) &&
             rbtn_right_get(node_t, link, pre) != node;
             pre = rbtn_right_get(node_t, link, pre)) {
        }
        if (!rbtn_right_get(node_t, link, pre)) {
            rbtn_right_get(node_t, link, pre) = node;
            node = rbtn_left_get(node_t, link, node); // JJJJ
        } else {
            rbtn_right_get(node_t, link, pre) = NULL; // KKKK

        do_print:
            result += node->value;
            printf("value: %d\n", node->value);
            node = rbtn_right_get(node_t, link, node); // LLLL 
        }
    }
    return result;
}
/*    5   15行     5     輸出 1         5  輸出 5            5
 *   /     =>     /       =>          /   =>               /
 *  1            1    22行回到5      1     10行發現回到5    1
 *                \                   \   將1的rightmost node 設回 null
 *                 5                   5  輸出 5
 * / 

可以發現沒有用到額外的空間卻能將值由小到大取出，8 ~ 12 行利用了 left node 的 right most child 空間紀錄前一個較大的 node ， 之後輸出這個較大 node 的值後再把它改回 NULL ， 所以 22 行 `rbtn_right_get` 可以回到前一個較大的 node ， 第 10 行就是判斷是否回到這個較大的 node
相較於用額外空間來記錄較大的 node ， 為了找出 right most child 會多出許多走訪的過程