# 2023q1 Homework4 (quiz4)
contributed by < `terry23304` >
## 測驗 1
把顏色資訊儲存在右子的最低位元中，最低位元為 1 則為紅， 0 為黑
```c
#define rb_node(x_type) \
struct { \
x_type *left, *right_red; \
}
```
### insert
從 root 開始走訪，直到插入點並記錄走訪過的節點
```c
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` 為左子，因為左傾樹，點為左子時不會有平輩節點，不須考慮自己與平輩節點皆為紅的狀況
```c
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; \
rbtn_black_set(x_type, x_field, leftleft); \
rbtn_rotate_right(x_type, x_field, cnode, tnode); \
cnode = tnode; \
} \
}
```
若 `pathp->node` 為右子，要檢查平輩節點是否皆為紅點與有沒有符合左傾樹與有沒有相鄰的紅點
```c
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; \
} \
}
```
### remove
從樹根開始找到要刪除的節點，並往左尋訪找到 successor 並用 `pathp` 紀錄
```c
path->node = rbtree->root; \
for (pathp = path; pathp->node; pathp++) { \
int cmp = pathp->cmp = x_cmp(node, pathp->node); \
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); \
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; \
} \
} \
}
```
若 successor 不等於 `node` 則代表 successor 在 `node` 的子樹中
```c
if (pathp->node != node) { \
/* Swap node with its successor. */ \
bool tred = rbtn_red_get(x_type, x_field, pathp->node); \
rbtn_color_set(x_type, x_field, pathp->node, \
rbtn_red_get(x_type, x_field, node)); \
// 交換 node 與 successor
rbtn_left_set(x_type, x_field, pathp->node, \
rbtn_left_get(x_type, x_field, node)); \
rbtn_right_set(x_type, x_field, pathp->node, \
rbtn_right_get(x_type, x_field, node)); \
rbtn_color_set(x_type, x_field, node, tred); \
nodep->node = pathp->node; \
pathp->node = node; \
// 若已是 root 則設成 root
if (nodep == path) { \
rbtree->root = nodep->node; \
} else { \
// 看目前在 parent node 的左子還是右子樹，並把 Link 接上
if (nodep[-1].cmp < 0) { \
rbtn_left_set(x_type, x_field, nodep[-1].node, \
nodep->node); \
} else { \
rbtn_right_set(x_type, x_field, nodep[-1].node, \
nodep->node); \
} \
} \
}
```
若要刪除的節點 successor 不在 `node` 的右子樹中
```c
else { \
x_type *left = rbtn_left_get(x_type, x_field, node); \
if (left) { \
/* node has no successor, but it has a left child. */ \
/* Splice node out, without losing the left child. */ \
assert(!rbtn_red_get(x_type, x_field, node)); \
assert(rbtn_red_get(x_type, x_field, left)); \
rbtn_black_set(x_type, x_field, left); \
if (pathp == path) { \
rbtree->root = left; \
/* Nothing to summarize -- the subtree rooted at the */ \
/* node's left child hasn't changed, and it's now the */ \
/* root. */ \
} else { \
if (pathp[-1].cmp < 0) { \
rbtn_left_set(x_type, x_field, pathp[-1].node, left); \
} else { \
rbtn_right_set(x_type, x_field, pathp[-1].node, left); \
} \
} \
return; \
} else if (path == pathp) { \
/* The tree only contained one node. */ \
rbtree->root = NULL; \
return; \
} \
}
```
## 測驗 2
`Timsort`: 採用了 insersion sort 與 merge sort
先分成小區塊，再用 Insertion Sort 對每個區塊做排序，再把這些區塊合併起來
### inplace merge
合併兩個 run [1, 2, 5, 7] 、 [3, 4, 6, 8]
找到 run 1 中小於 `cur_2` 的區域 (1, 2)，用 `cur_1` 紀錄
```c
while (cur_1 < last_2 && !cmp(cur_2, cur_1))
cur_1 += size;
```
找到 run 2 中小於 `cur_1` 的區域 (3, 4)，用 `cur_2` 紀錄
```c
while (cur_2 < last_2 && cmp(cur_2, cur_1))
cur_2 += size;
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=black, fontsize=16];
"Pointers:" -> "Values:" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
pointers [label="<f0> first_1 | <f7> cur_1 | <f2> last_1 | <f1> first_2 |<f10> cur_2 | <f3> last_2", color=white];
values [label="<f0> 1 | <f1> 2 | <f2> 5 | <f3> 7 | <f4> 3 | <f5> 4 | <f6> 6 | <f7> 8"];
{ rank=same; "Pointers:"; pointers }
{ rank=same; "Values:"; values }
edge [];
pointers:f0 -> values:f0;
pointers:f1 -> values:f4;
pointers:f2 -> values:f3;
pointers:f3 -> values:f7;
pointers:f7 -> values:f2;
pointers:f10 -> values:f6;
}
```
先反轉 `cur_1` 到 `first_2 -= size`
```c
__reverse(cur_1, first_2, size);
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=black, fontsize=16];
"Pointers:" -> "Values:" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
pointers [label="<f0> first_1 | <f7> cur_1 | <f2> last_1 | <f1> first_2 |<f10> cur_2 | <f3> last_2", color=white];
values [label="<f0> 1 | <f1> 2 | <f2> 7 | <f3> 5 | <f4> 3 | <f5> 4 | <f6> 6 | <f7> 8"];
{ rank=same; "Pointers:"; pointers }
{ rank=same; "Values:"; values }
edge [];
pointers:f0 -> values:f0;
pointers:f1 -> values:f4;
pointers:f2 -> values:f3;
pointers:f3 -> values:f7;
pointers:f7 -> values:f2;
pointers:f10 -> values:f6;
}
```
再翻轉 `first_2` 到 `cur_2 -= size`
```c
__reverse(first_2, cur_2, size);
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=black, fontsize=16];
"Pointers:" -> "Values:" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
pointers [label="<f0> first_1 | <f7> cur_1 | <f2> last_1 | <f1> first_2 |<f10> cur_2 | <f3> last_2", color=white];
values [label="<f0> 1 | <f1> 2 | <f2> 7 | <f3> 5 | <f4> 4 | <f5> 3 | <f6> 6 | <f7> 8"];
{ rank=same; "Pointers:"; pointers }
{ rank=same; "Values:"; values }
edge [];
pointers:f0 -> values:f0;
pointers:f1 -> values:f4;
pointers:f2 -> values:f3;
pointers:f3 -> values:f7;
pointers:f7 -> values:f2;
pointers:f10 -> values:f6;
}
```
最後翻轉 `cur_1` 到 `cur_2` ，完成 `first_1` 到 `cur_2`
```c
__reverse(cur_1, cur_2, size);
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=black, fontsize=16];
"Pointers:" -> "Values:" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
pointers [label="<f0> first_1 | <f7> cur_1 | <f2> last_1 | <f1> first_2 |<f10> cur_2 | <f3> last_2", color=white];
values [label="<f0> 1 | <f1> 2 | <f2> 3 | <f3> 4 | <f4> 5 | <f5> 7 | <f6> 6 | <f7> 8"];
{ rank=same; "Pointers:"; pointers }
{ rank=same; "Values:"; values }
edge [];
pointers:f0 -> values:f0;
pointers:f1 -> values:f4;
pointers:f2 -> values:f3;
pointers:f3 -> values:f7;
pointers:f7 -> values:f2;
pointers:f10 -> values:f6;
}
```
更新 `first_1` 、 `first_2` 指到尚未排序的區域
```c
first_1 = cur_1 + (cur_2 - first_2);
first_2 = cur_2;
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=black, fontsize=16];
"Pointers:" -> "Values:" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
pointers [label="<f0> first_1 | <f1> first_2", color=white];
values [label="<f0> 1 | <f1> 2 | <f2> 3 | <f3> 4 | <f4> 5 | <f5> 7 | <f6> 6 | <f7> 8"];
{ rank=same; "Pointers:"; pointers }
{ rank=same; "Values:"; values }
edge [];
pointers:f0 -> values:f4;
pointers:f1 -> values:f7;
}
```
再用同樣的方式繼續合併直到完成
### merge rule
若 run 的大小差不多合併的效率更好，所以在下層長度比上層大時才合併
```c
return run_length(stack[top]) > run_length(stack[top - 1]) ||
run_length(stack[top]) + run_length(stack[top - 1]) >
run_length(stack[top - 2]);
```
### next partition
切出各個 run 並用 insertion sort 排序
計算有多少數已是升冪或降冪排序好的，若為降冪則做反轉，並計算該 run 的長度
```c
if (cmp(cur, next)) {
while (next < last && cmp(cur, next)) {
++run_len;
cur += size;
next += size;
}
} else {
while (next < last && !cmp(cur, next)) {
++run_len;
cur += size;
next += size;
}
__reverse(first, next, size);
}
```
若長度還小於 `MIN_RUN` 且總長比 `MIN_RUN` 大則加大該 run 的長度，並用 insertion sort 排序。
```c
if (next < last && run_len < MIN_RUN) {
last = first + MIN_RUN * size < last ? first + MIN_RUN * size : last;
__insertion_sort(first, last, size, cmp);
return (last - first) / size;
}
return run_len;
}
```
### timsort
把數列切成好幾個 run 放進 stack 中，若符合規則每次取兩個合併
```c
while (cur < last) {
size_t len = next_partition(cur, last, size, cmp);
stack[top].first = cur;
stack[top].last = stack[top].first + len * size;
cur = stack[top].last;
while (merge_rule(stack, top)) {
if (buf)
__merge(stack[top - 1].first, stack[top - 1].last,
stack[top].first, stack[top].last, buf, size, cmp);
else
__inplace_merge(stack[top - 1].first, stack[top - 1].last,
stack[top].first, stack[top].last, size, cmp);
stack[top - 1].last = stack[top].last;
top --;
}
top++;
}
```
最後把剩餘的 run 合併起來
```c
while (top > 1) {
--top;
if (buf)
__merge(stack[top - 1].first, stack[top - 1].last, stack[top].first,
stack[top].last, buf, size, cmp);
else
__inplace_merge(stack[top - 1].first, stack[top - 1].last,
stack[top].first, stack[top].last, size, cmp);
// 合併 top 跟 top - 1 所以要更新 top - 1 的 last
stack[top - 1].last = stack[top].last;
}
```
## 測驗 3
```c
#define RB_LOG2_MAX_NODES \
(RB_LOG2_MAX_MEM_BYTES - \
(sizeof(void *) >= 8 ? 4 \
: sizeof(void *) >= 4 ? 3 \
: 2) - 1)
```
### sum subtree
```c
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)) {
// 把右子設成 Node
rbtn_right_get(node_t, link, pre) = node;
node = rbtn_left_get(node_t, link, node);
} else {
rbtn_right_get(node_t, link, pre) = NULL;
do_print:
result += node->value;
printf("value: %d\n", node->value);
node = rbtn_right_get(node_t, link, node);
}
}
```
Sign in with Wallet
Connect another wallet