HackMD
2023q1 Homework4 (quiz4)
contributed by < LiChiiiii >
測驗題目：quiz4
測驗一
在測驗一提供的程式碼中定義
typedef rb_tree(node_t) tree_t;
rb_gen(static, tree_, tree_t, node_t, link, node_cmp);
對照 rb.h 之巨集的使用，展開 rb_gen(static, ex_, ex_t, ex_node_t, ex_link, ex_cmp) 巨集可以得到插入、刪除等功能之函式。
推敲其設計思維
tree_insert()
將巨集 x_attr void x_prefix##insert(x_rbt_type *rbtree, x_type *node) 展開為 static void tree_insert (tree_t *rbtree, node_t *node) ，此函式將新節點插入紅黑樹中，主要有三個步驟：
- 根據節點的比較結果遞迴查找插入位置
- 依次從下往上檢查是否需要旋轉
- 將根節點設為黑色。
舉個例子來說，現在有一個紅黑樹。
我們想插入新的節點 3，會先用 BST 的概念尋找插入的位置。
3與7比較，紀錄 cmp = -1 ，並往左進行下一層尋找。3與2比較，紀錄 cmp = 1 ，並往右進行下一層尋找。3與5比較，紀錄 cmp = -1 ，並往左進行下一層尋找，得到 NULL 跳出迴圈，把插入位置指向此節點，也就是pathp->node = node。
由於在尋找插入的位置的過程中，有依序紀錄經過每個節點及其 cmp 至名為 path 的陣列，因此當找到插入位置的同時，也得到了以下陣列 path 。
接下來將 pathp 反向回去，判斷每個 pathp 的 cmp 值來檢查是否需要旋轉。
如果 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;
rbtn_black_set(x_type, x_field, leftleft);
rbtn_rotate_right(x_type, x_field, cnode, tnode);
cnode = tnode;
}
如果 cmp >= 0 ，
- 出現左邊狀況則進行顏色轉換設定成右邊的樣子。
- 出現左邊狀況則進行旋轉成右邊的樣子。這邊是為了滿足 LLRBT 的左傾條件。
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);
rbtn_red_set(x_type, x_field, cnode);
cnode = tnode;
}
最後將根節點設為黑色。
tree_remove()
將巨集 x_attr void x_prefix##remove(x_rbt_type *rbtree, x_type *node) 展開為 static void tree_remove(tree_t *rbtree, node_t *node) ，此函式用於刪除紅黑樹中的節點，跟 tree_insert() 一樣的方式去尋找要刪除的節點，只是額外加上 if(cmp==0) ，若條件式成立，則表示找到要刪除的節點，接著就是找出節點的 successor ，來為交換做準備。
舉個例子來說，現在有一個紅黑樹，我想刪除節點 2。
可以得到這個 path 陣列。
在 cmp == 0 時，代表找到想刪除的節點，也就是找到節點 2，會設定 pathp->cmp = 1 ，並尋找此節點的 successor 。
if (cmp == 0) {
/* Find node's successor, in preparation for swap. */
pathp->cmp = 1;
nodep = pathp;
for (pathp++; pathp->node; pathp++) {
pathp->cmp = -1;
pathp[1].node = rbtn_left_get(x_type, x_field, pathp->node);
}
break;
}
因此 path 陣列會變成
