2023q1 Homework4 (quiz4)

contributed by < koty6069 >

2023q1 第 4 週測驗題

測驗 1

與 quiz3 的紅黑樹做比較

理解 Left-leaning Red-Black Trees

原先將 2-3-4 樹轉為紅黑樹時，會將 3-node 轉為一紅邊一黑邊的左右子樹，因為紅邊可以在左或右，會導致轉換後的紅黑樹有多種情況，使得實作時程式碼會變得非常複雜，因此提出左傾紅黑樹，將 3-node 固定轉換成左子樹為紅邊的情況，這樣可以把轉換後的紅黑樹限制為一種，2-3-4 樹和紅黑樹之間的關係變為 1-1 對應。

在插入新節點的部分可明顯看出左傾紅黑樹的優勢，只要在搜尋要插入的位置時檢查路徑上遇到的情況並進行以下幾種操作，即可確保整棵樹仍會遵守紅黑樹的規則：

1. 若遇到 4-node （也就是左右子樹皆為紅色），就將顏色翻轉。
2. 遇到右子樹為紅就將其旋轉為左傾。
3. 遇到連續兩個紅邊，執行右旋轉，將其平衡為 4-node。

只要在原始二元搜尋樹的插入操作加入以上幾項檢查即可完成紅黑樹的插入操作，相較於一般的紅黑樹需考慮更多種情況，程式碼顯得更加簡潔。

解析程式碼 (Incomplete rb.h)

/* Node structure */
#define rb_node(x_type)           \
    struct {                      \
        x_type *left, *right_red; \
    }

使用巨集定義紅黑樹的節點，與第三次作業不同處在於只紀錄左右子節點，並無紀錄親代節點的位址，也因此利用對齊的技巧將顏色儲存在右子樹 （right_red） 的最低位元。

/* Right accessors */
#define rbtn_right_get(x_type, x_field, x_node) \
    ((x_type *) (((intptr_t) (x_node)->x_field.right_red) & ~3))
#define rbtn_right_set(x_type, x_field, x_node, x_right)                  \
    do {                                                                  \
        (x_node)->x_field.right_red =                                     \
            (x_type *) (((uintptr_t) x_right) |                           \
                        (((uintptr_t) (x_node)->x_field.right_red) & 1)); \
    } while (0)

取得和設定右節點時和 quiz3 相同，取出時將用不到的最低三位元清空，設定時將傳入的 x_right 與存有原本顏色的最低位元做 or，用以將原本節點的顏色保留下來。

/* Node initializer */
#define rbt_node_new(x_type, x_field, x_rbt, x_node)          \
    do {                                                      \
        /* Bookkeeping bit cannot be used by node pointer. */ \
        assert(((uintptr_t) (x_node) & (0x1)) == 0);          \
        rbtn_left_set(x_type, x_field, (x_node), NULL);       \
        rbtn_right_set(x_type, x_field, (x_node), NULL);      \
        rbtn_red_set(x_type, x_field, (x_node));              \
    } while (0)

初始化一個新的紅黑樹節點，按照規則會將此節點設為紅色。

/* Internal utility macros */
#define rbtn_rotate_left(x_type, x_field, x_node, r_node)         \
    do {                                                          \
        (r_node) = rbtn_right_get(x_type, x_field, (x_node));     \
        rbtn_right_set(x_type, x_field, (x_node),                 \
                       rbtn_left_get(x_type, x_field, (r_node))); \
        rbtn_left_set(x_type, x_field, (r_node), (x_node));       \
    } while (0)

#define rbtn_rotate_right(x_type, x_field, x_node, r_node)        \
    do {                                                          \
        (r_node) = rbtn_left_get(x_type, x_field, (x_node));      \
        rbtn_left_set(x_type, x_field, (x_node),                  \
                      rbtn_right_get(x_type, x_field, (r_node))); \
        rbtn_right_set(x_type, x_field, (r_node), (x_node));      \
    } while (0)

執行一次左旋轉或右旋轉的巨集，

rb_gen

#define rb_gen(x_attr, x_prefix, x_rbt_type, x_type, x_field, x_cmp)

rb_gen 使用你所不知道的 C 語言：前置處理器應用篇提到的連結技巧，會根據傳入的參數去展開巨集，產生一系列對應的程式碼。

rb_gen(static, tree_, tree_t, node_t, link, node_cmp);

在測驗題中將以上參數傳入 rb_gen，根據 rb_proto 會產生包含 tree_new、tree_insert 等在內的函式，tree_t 為記錄紅黑樹的結構，node_t 則為紅黑樹節點， link 為節點之間的連結，node_cmp 為比較節點大小值的函式，根據註解要求，若值較小需傳回 -1，相等傳回 0，較大傳回 1。

    typedef struct {                                                           \
        x_type *node;                                                          \
        int cmp;                                                               \
    } x_prefix##path_entry_t;  

因為本實作中每個節點只有記錄自己的左右子樹，並沒有記錄親代節點，因此另外定義一個 tree_path_entry_t 的結構體，用來在走訪紅黑樹時存放走過的路徑，node 就是存放走過的節點內容， cmp 則用來記錄比較的結果，可以得知要往右或往左走訪。

tree_search

作用為在紅黑樹中找到 key 值的位置。

        int cmp;                                                               \
        x_type *ret = rbtree->root;                                            \
        while (ret && (cmp = (x_cmp) (key, ret)) != 0) {                       \
            if (cmp < 0) {                                                     \
                ret = rbtn_left_get(x_type, x_field, ret);                     \
            } else {                                                           \
                ret = rbtn_right_get(x_type, x_field, ret);                    \
            }                                                                  \
        }                                                                      \
        return ret;  

使用到比較函式 node_cmp ，若比較結果 cmp 為 -1 就往左走，cmp 為 1 就向右走，cmp 為 0 代表找到該值，因此就脫離迴圈並回傳。

tree_insert

x_attr void x_prefix##insert(x_rbt_type *rbtree, x_type *node)

作用為將節點插入紅黑樹中適當的位置。

        x_prefix##path_entry_t path[RB_MAX_DEPTH];                             \
        x_prefix##path_entry_t *pathp;                                         \
        rbt_node_new(x_type, x_field, rbtree, node);                           \
        /* Wind. */                                                            \
        path->node = rbtree->root;                                             \
        for (pathp = path; pathp->node; pathp++) {                             \
            int cmp = pathp->cmp = x_cmp(node, pathp->node);                   \
            assert(cmp != 0);                                                  \
            if (cmp < 0) {                                                     \
                pathp[1].node = rbtn_left_get(x_type, x_field, pathp->node);   \
            } else {                                                           \
                pathp[1].node = rbtn_right_get(x_type, x_field, pathp->node);  \
            }                                                                  \
        }                                                                      \
        pathp->node = node;  

首先建立一個長度為 RB_MAX_DEPTH 的 tree_path_entry_t 陣列，用來記錄過的路徑，其中RB_MAX_DEPTH 就是給予紅黑樹的高度限制，在走訪時可以確定不會超過紅黑樹的高度，*pathp 則是在 for 迴圈時迭代整個陣列所使用。

在進入迴圈前會將 root 放入 path 的第一個位置，進入迴圈後，第 7 行會在每次迭代時將比較的結果存進當前陣列位置的 cmp，在 9~13 行會依據比較的結果，將左或右子節點放入陣列的下一個位置 pathp[1] 接著 pathp 會指向下一個位置，當目前的指到的陣列位置 pathp->node 為空時，就會離開迴圈，此時指到的陣列位置就是此次路徑的最後一個節點，因此 15 行將預備要插入的節點 node 放入。

        for (pathp--; (uintptr_t) pathp >= (uintptr_t) path; pathp--) {        \
            x_type *cnode = pathp->node;  

正式進行插入的動作，會從前述路徑 path 的倒數第二的節點開始，不斷沿著記錄的路徑向前，在此過程中依序檢查各節點間的關係是否符合紅黑樹的規則，若違反就進行調整，直到達到路徑的起始點 (uintptr_t) pathp >= (uintptr_t) path，這樣就能確保整個紅黑樹都符合規則，cnode 為當前位置的節點。

            if (pathp->cmp < 0) {                                              \
                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;                                             \
                    AAAA(x_type, x_field, leftleft);                           \
                    rbtn_rotate_right(x_type, x_field, cnode, tnode);          \
                    cnode = tnode;                                             \
                }    

每次迴圈會以當前指到的節點為主，去檢查 cmp 是 1 或 -1，以得知走訪路徑中下個節點位於左或右子樹，假如 cmp < 0 代表需要取得左子節點，因為在紅黑樹中只需要旋轉紅邊，因此當第 4 行發現到下個節點並非紅色時，就不需再繼續檢查，直接 return，結束插入的程序。

第 7 行的 if 條件式在檢測連續兩個紅邊的情形，也就是最前述提到的第 3 種情況，這時要將其修正為 4-node，於是直行右旋轉將 left 調整至目前節點的位置，AAAA 為 rbtn_black_set。

3. 遇到連續兩個紅邊，執行右旋轉，將其平衡為 4-node。

            } 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, BBBB);              \
                    CCCC(x_type, x_field, cnode);                              \
                    cnode = tnode;                                             \
                }                                                              \
            }                                                                  \
            pathp->node = cnode;

進入 else 則是下一節點為右子樹的情形，第 7 行為最前述的第 1 種情形，要將 4-node 分割，因此進行顏色翻轉，將左右子節點設為黑色，當前節點設為紅色。

1. 若遇到 4-node （也就是左右子樹皆為紅色），就將顏色翻轉。

第 12 行的 else 代表只有右節點為紅色，就是第 2 種情形，要將右子樹的紅邊旋轉去左邊，執行左旋轉後將原本的右節點 tnode 轉至 cnode 的位置，再將其設為原本 cnode 的顏色， BBBB 為 tred，此時 cnode 在原本 left 的位置，我們的目的是將紅邊調整至左邊，因此最後要將 cnode 設為紅色，CCCC 為 rbtn_red_set。

2. 遇到右子樹為紅就將其旋轉為左傾。

        /* Set root, and make it black. */                                     \
        rbtree->root = path->node;                                             \
        rbtn_black_set(x_type, x_field, rbtree->root);

最後重新記錄 root 的位置，並將其設為黑色以保持規則的正確性。

tree_remove

用來將節點刪除並對紅黑樹做對應的調整。

        x_prefix##path_entry_t path[RB_MAX_DEPTH];                             \
        x_prefix##path_entry_t *pathp;                                         \
        x_prefix##path_entry_t *nodep;                                         \
        /* This is just to silence a compiler warning. */                      \
        nodep = NULL;

刪除時一樣使用紀錄路徑的技巧。

                if (cmp == 0) {                                                \
                    /* Find node's successor, in preparation for swap. */      \
                    pathp->cmp = DDDD;                                         \
                    nodep = pathp;                                             \
                    for (pathp++; pathp->node; pathp++) {                      \
                        pathp->cmp = -1;                                       \
                        pathp[1].node =                                        \
                            rbtn_left_get(x_type, x_field, pathp->node);       \
                    }                                                          \
                    break;                                                     \
                }