owned this note
owned this note
Published
Linked with GitHub
# 2023q1 Homework4 (quiz4)
contributed by < `LiChiiiii` >
>測驗題目：[quiz4](https://hackmd.io/@sysprog/linux2023-quiz4)
## 測驗一
在測驗一提供的程式碼中定義
```c
typedef rb_tree(node_t) tree_t;
rb_gen(static, tree_, tree_t, node_t, link, node_cmp);
```
對照 [rb.h](https://gist.github.com/jserv/6610eb56bf2486979c8bf6ee8061f71c) 之巨集的使用，展開 `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)` ，此函式將新節點插入紅黑樹中，主要有三個步驟：
1. 根據節點的比較結果遞迴查找插入位置
2. 依次從下往上檢查是否需要旋轉
3. 將根節點設為黑色。
舉個例子來說，現在有一個紅黑樹。
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
2[fillcolor=red]
A,B,C,D,E,F[fontsize=0,color=transparent]
7 -> {2 11}
2 -> {1 5}
1 -> {A B}
5 -> {C D}
11 -> {E F}
}
```
我們想插入新的節點 `3`，會先用 BST 的概念尋找插入的位置。
1. `3` 與 `7` 比較，紀錄 cmp = -1 ，並往左進行下一層尋找。
2. `3` 與 `2` 比較，紀錄 cmp = 1 ，並往右進行下一層尋找。
3. `3` 與 `5` 比較，紀錄 cmp = -1 ，並往左進行下一層尋找，得到 NULL 跳出迴圈，把插入位置指向此節點，也就是 `pathp->node = node` 。
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
2,3[fillcolor=red]
A,B,C,D,E,F[fontsize=0,color=transparent]
7 -> {2 11}
2 -> {1 5}
1 -> {A B}
5 -> {3 D}
11 -> {E F}
}
```
由於在尋找插入的位置的過程中，有依序紀錄經過每個節點及其 cmp 至名為 path 的陣列，因此當找到插入位置的同時，也得到了以下陣列 path 。
```graphviz
digraph path{
// node [shape=plaintext, fontcolor=black, fontsize=18];
// "Pointers:" -> "Values:" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
pointers [label="<f0> | <f1> | <f2>pathp |<f3> pathp[1]", color=white];
values [label="<f0> 7, -1 | <f1> 2, 1 | <f2> 5, -1 | <f3> 3", fillcolor=pink, style=filled];
// { rank=same; "Pointers:"; pointers }
// { rank=same; "Values:"; values }
edge [color=black];
pointers:f2 -> values:f2;
pointers:f3 -> values:f3;
}
```
接下來將 pathp 反向回去，判斷每個 pathp 的 cmp 值來檢查是否需要旋轉。
如果 cmp < 0 ，且出現左邊狀況則進行旋轉成右邊的樣子。
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.7]
left, leftleft [fillcolor=red]
A,B[fontsize=0,color=transparent]
cnode -> left
cnode -> A [color=transparent]
left -> leftleft
// left -> B [color=transparent]
left_[fillcolor=red]
A,B[fontsize=0,color=transparent]
left_ -> leftleft_
left_ -> cnode_
}
```
```c
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 ，
1. 出現左邊狀況則進行顏色轉換設定成右邊的樣子。
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.7]
left, right [fillcolor=red]
cnode -> left
cnode -> right
cnode_[fillcolor=red]
cnode_ -> left_
cnode_ -> right_
}
```
2. 出現左邊狀況則進行旋轉成右邊的樣子。這邊是為了滿足 LLRBT 的左傾條件。
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.7]
tnode [fillcolor=red]
null, null1[fontsize=0,color=transparent]
cnode -> null[color=transparent]
cnode -> tnode
cnode_[fillcolor=red]
tnode_ -> cnode_
tnode_ -> null1[color=transparent]
}
```
```c
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`。
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
2[fillcolor=red]
A,B,C,D,E,F[fontsize=0,color=transparent]
7 -> {2 11}
2 -> {1 5}
1 -> {A B}
5 -> {C D}
11 -> {E F}
}
```
可以得到這個 path 陣列。
```graphviz
digraph path{
// node [shape=plaintext, fontcolor=black, fontsize=18];
// "Pointers:" -> "Values:" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
pointers [label="<f0> | <f1>pathp ", color=white];
values [label="<f0> 7, -1 | <f1> 2, -1 ", fillcolor=pink, style=filled];
// { rank=same; "Pointers:"; pointers }
// { rank=same; "Values:"; values }
edge [color=black];
pointers:f1 -> values:f1;
}
```
在 `cmp == 0` 時，代表找到想刪除的節點，也就是找到節點 `2`，會設定 pathp->cmp = 1 ，並尋找此節點的 successor 。
```c
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 陣列會變成
```graphviz
digraph path{
// node [shape=plaintext, fontcolor=black, fontsize=18];
// "Pointers:" -> "Values:" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
pointers [label="<f0>pathp[-1] | <f1>pathp | <f2>pathp[1] ", color=white];
values [label="<f0> 7, -1 | <f1> 2, 1 | <f2> 1, -1", fillcolor=pink, style=filled];
// { rank=same; "Pointers:"; pointers }
// { rank=same; "Values:"; values }
edge [color=black];
pointers:f0 -> values:f0;
pointers:f1 -> values:f1;
pointers:f2 -> values:f2;
}
```
## 測驗二
## 測驗三
Google Drive
Gist
Clipboard
Sign in with Wallet
