2023q1 Homework4 (quiz4)

contributed by < Korin777 >

測驗題目

測驗三

RB_LOG2_MAX_NODES

node_t 的大小為 sizeof(void*) * 4 所以 node 最多有

$$\frac{1<<(sizeof(void\ast )<<3)}{(sizeof(void\ast )\ast 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 變為黑色讓路徑上的黑色節點數相同

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

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

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 會多出許多走訪的過程