# 2025q1 Homework2 (quiz1+2)
contributed by <`h0w726`>
## W1Q1
### 解釋程式碼運作原理
一開始先定義 `my_assert` 函式，若 `test` 為 `false` ，則印出 `message` ，用來判斷 list 初始的大小是否為0，分配完的 list 大小為 N ，以及 list 是否正確為遞增或遞減。
在 `test_list` 中，先呼叫 `list_reset` 初始化 i 個節點以及 head 指標。
`list_insert_before` 函式
```c
static inline void list_insert_before(list_t *l,
list_item_t *before,
list_item_t *item)
{
list_item_t **p;
for (p = &l->head; *p != before; p = &(*p)->next)
;
*p = item;
item->next = before;
}
```
這裡演示插入開頭的位置的步驟,首先指標的指標 `p` 會指向 `head` 指標， `item` 指標則指向接下來要插入的節點。
```c
for (size_t i = 0; i < N; i++)
list_insert_before(&l, l.head, &items[i]);
```
```graphviz
digraph linkedlist{
rankdir=LR
p[shape=none,label=p]
head[shape=none,label=head]
null[shape=none,label=NULL];
null1[shape=none,label=NULL];
before[shape=none,label=before];
i[shape=none,label=item];
a [shape=record,label="{ <data> 4 | <ref> }"];
b [shape=record,label="{ <data> 3 | <ref> }"];
c [shape=record,label="{ <data> 2 | <ref> }"];
d [shape=record,label="{ <data> 1 | <ref> }"];
e [shape=record,label="{ <data> 5 | <ref> }"]
{ rank = same; p -> head[arrowhead=vee, arrowtail=dot, dir=both,minlen=3] }
head -> a
e:ref:c->null1[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
i->e
before->a
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
接著 `p` 會找到目前 `before` 指向的節點, `*p=item` 讓 `head` 指標指向要插入的節點, `item->next = before;` ,則讓 `item->next` 指向原來的第一個節點。
```graphviz
digraph linkedlist{
rankdir=LR
p[shape=none,label=p]
head[shape=none,label=head]
null[shape=none,label=NULL];
null1[shape=none,label=NULL];
before[shape=none,label=before];
i[shape=none,label=item];
a [shape=record,label="{ <data> 4 | <ref> }"];
b [shape=record,label="{ <data> 3 | <ref> }"];
c [shape=record,label="{ <data> 2 | <ref> }"];
d [shape=record,label="{ <data> 1 | <ref> }"];
e [shape=record,label="{ <data> 5 | <ref> }"]
f [shape=record,label="{ <data> 6 | <ref> }"]
{ rank = same; p -> head[arrowhead=vee, arrowtail=dot, dir=both,minlen=3] }
head -> e
i->f
f:ref:c->null1[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
before->e
e:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
`list_insert_before` 透過指標的指標 `p` ，找到目前 `before` 指向的節點,在此程式中,每次呼叫 `list_insert_before` `before`都會指向第一個節點，所以每次節點都會插入在鏈結串列的頭部。
### 延伸問題
## W1Q2
這裡是基於二元搜尋樹管理空閒記憶體區塊，讓記憶體配置器能更有效率地搜尋到合適的區塊。
Free list 是使用鏈結串列管理記憶體區塊，搜尋合適區塊的時間複雜度為 O(N) ，若使用二元搜尋樹管理記憶體區塊，搜尋合適區塊的時間複雜度可為 O(logN)。
`remove_free_tree` 函式的功能是刪除二元搜尋樹中的某個節點，刪除節點的值就是配置那個大小的記憶體，然而刪除節點會有以下三種情況須討論。
1. `Target` 沒有子節點
這時 `target` 指向 80 ，因為沒有子節點，直接刪除即可。
```graphviz
digraph 1{
node [fontname="Arial"];
50 -> 30;
50 -> 70;
70 -> 80;
t[shape=none,label=target];
t -> 30
null0 [shape=point];
70 -> null0
}
n[shape=none,label=node_ptr];
n -> t
```
2. `Target` 有一個子節點
這時 `target` 指向 40 ，我們要用45替代到現在40的位置
```graphviz
digraph 2{
node [fontname="Arial"];
50 -> 30;
30 -> 20;
30 -> 40;
t[shape=none,label=target];
t -> 40;
50 -> 70;
70 -> 80;
null [shape=point];
70 -> null;
null0 [shape=point];
40 -> 45;
40 -> null0
}
```
在這之前我一直以為 `node_ptr` 是指向 `target` 的指標，但看到最後更新的程式碼就一直覺得非常奇怪
```c
/* If the target node has one child (or none), simply splice it out. */
else if ((*node_ptr)->l || (*node_ptr)->r) {
block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
*node_ptr = child;
} else {
/* No children: remove the node. */
*node_ptr = NULL;
}
```
如果 `node_ptr` 指向 `target` 的話，`*node_ptr = NULL` 也只是讓 `target` 指向 `NULL` 而已，根本沒有刪除到節點，後來發現 `find_free_tree` 的註解
```c
/* Locate the pointer to the target node in the tree. */
block_t **node_ptr = find_free_tree(root, target);
```
只有說到找到指向 target node 的指標，並沒有說一定就是指向 `target` 這個指標,所以 `node_ptr` 是指向 target node 的
父節點中指向 target node 的那個指標，這樣上面程式碼的更新就會顯得合理了。
3. `Target` 有兩個子節點
這是最複雜的情形，二元搜尋樹有以下幾個[規則](https://zh.wikipedia.org/zh-tw/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9)需要遵守
* 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值
* 若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值
* 任意節點的左、右子樹也分別為二元搜尋樹
所以當要刪除的節點有兩個子節點時，必須找到該節點的 in-order predecessor 替代其原本的位置，才不會破壞二元搜尋樹的結構。
透過以下程式尋找 in-order predecessor
```c
block_t **pred_ptr = &(*node_ptr)->l;
while (*pred_ptr)->r)
pred_ptr = &(*pred_ptr)->r;
```
這段程式碼會找到要刪除的節點的左子樹中，最下方且最右邊的節點，也就是 in-order predecessor。
刪除的節點有兩個子節點可分為下列兩種情況
* in-order predecessor 是要刪除節點的左子節點
```graphviz
digraph 3{
node [fontname="Arial"];
50 -> 30;
50 -> 70;
}
```
這情況很簡單，只需要先把要刪除節點的右子樹先備份，將要刪除的節點替換成左子節點後，再將右子樹接回即可。
* in-order predecessor 在左子樹的更深層
```graphviz
digraph 4{
node [fontname="Arial"];
50 -> 30;
50 -> 70;
30 -> 20;
30 -> 40;
t[shape=none,label=target];
t -> 50
}
```
這情況需要先將刪除節點的左子樹和右子樹以及 in-order predecessor 先備份，再將再將 in-order predecessor 從左子樹中刪除，再將 in-order predecessor 替代刪除的節點，並把左右子樹接回。
```graphviz
digraph 5{
node [fontname="Arial"];
40 -> 30;
40 -> 70;
30 -> 20;
}
```
### 延伸問題
Sign in with Wallet
Connect another wallet