# 2025q1 Homework2 (quiz1+2)
contributed by < JUSTUSVMOS >
## Week 1 Quiz - Linked List
[Week1 Quiz](https://hackmd.io/@sysprog/linux2025-quiz1)
### Quiz 1 - Head Linked List `list_insert_before`
#### 解釋程式碼
**1. 線性尋找插入位置**
- 迴圈條件 `*p != before`：只要目前節點不是欲插入點，就把 p 移到下一個「指標的位址」──亦即 `p = &(*p)->next`。
- 若 before 為 NULL，迴圈會跑到最後一個節點的 next 欄位位址，使 p 最終指向「尾端指標」(即目前為 NULL 的那格)。
**2. 重寫指標，完成插入（兩步）**
- `*p = item;`
把原本指向 before 的指標改成指向新節點 item。
若 p 是 `&l->head`，這行相當於更新 head。
- `item->next = before`;
將新節點的 `next` 接回 `before`。
如果 `before == NULL`，就讓 item 成為新的尾節點 `(next == NULL)`。
**test_list() 共有三段情境**
1. 插入到 開頭 (before l.head)
```c
for (i = 0; i < N; i++)
list_insert_before(&l, l.head, &items[i]);
```
- 第一次 l.head == NULL ⇒ 行為相當於 push-front；插入後 head 指向 items[0].
- 第二次之後，before == l.head ⇒ 新節點不斷插到現行 head 前面，故串列最終逆序 (N-1 … 2 1 0).
2. 插入到 結尾 (before NULL)
```c
list_insert_before(&l, NULL, &items[i]);
```
把 before == NULL 解讀為「附加在尾端」。
由於每次都選擇尾端，最終串列保持順序 (0 1 2 … N-1).
3. 再次驗證尾端插入
與 2 相同，確保重複 reset → re-insert 仍正確、沒有記憶體殘留影響。
---
#### 在現有的程式碼基礎上，撰寫合併排序操作
```c
// 合併 a 與 b，回傳排序後的 head
static list_item_t* merge_two(list_item_t *a, list_item_t *b) {
list_item_t *head = NULL;
list_item_t **ptr = &head; // ptr 永遠指向「下一條要填入節點的那個指標」
while (a && b) {
if (a->value <= b->value) {
*ptr = a; // 接上 a
a = a->next; // a 前進
} else {
*ptr = b; // 接上 b
b = b->next; // b 前進
}
ptr = &((*ptr)->next); // ptr 跟著移動到剛接上節點的 next 欄位
}
// 其中一邊耗盡，直接把剩下的整串接上
*ptr = a ? a : b;
return head;
}
// 其餘遞迴拆半、排序邏輯不變
static list_item_t* merge_sort_rec(list_item_t *head) {
if (!head || !head->next)
return head;
list_item_t *slow = head, *fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
list_item_t *mid = slow->next;
slow->next = NULL;
return merge_two(merge_sort_rec(head),
merge_sort_rec(mid));
}
void list_merge_sort(list_t *l) {
l->head = merge_sort_rec(l->head);
}
```
---
### Week 1 Quiz 2 - Binary Search Tree
#### 解釋程式碼
在二元搜尋樹（Binary Search Tree，BST）中，某個節點 `x` 的 **predecessor**（前驅）指的是「在中序（左→根→右）遍歷中，緊接在 `x` 之前的那個節點」。換句話說，它是所有小於 `x->key` 節點中，鍵值最大的那一個。
---
**如何找前驅**
假設我們要找節點 `x` 的前驅，主要有兩種情況：
1. **左子樹非空**
* 前驅就是 `x` 左子樹中的最大節點。
* 作法：從 `x->left` 開始，一直往右走到不能再右→即為前驅。
2. **左子樹為空**
* 這時候前驅必定在 `x` 的祖先節點中。
* 作法：沿著父指標（或用遞迴／棧模擬）往上走，直到某個節點 `p` 滿足：
* 你剛從 `p->right` 走進 `p`（也就是 `x` 在 `p` 的右子樹裡）。
* 那麼 `p` 就是前驅。
* 若一路走到根都沒找到，代表 `x` 是整棵樹中最小的節點，沒有前驅。
---
**範例**
```
20
/ \
10 30
/ \ \
5 15 40
\
17
```
* **前驅(20)**
* 左子樹非空 → 在子樹 `10–15–17` 中找最大 → `17`
* **前驅(10)**
* 左子樹非空 → 在子樹 `5` 中最大 → `5`
* **前驅(5)**
* 左子樹空，向上看：5 是 10 的左子節點 → 繼續往上，到 20…都不是從右子樹來 → 無前驅
* **前驅(30)**
* 左子樹空，向上看：30 是 20 的右子 → 前驅就是 `20`
---
**remove\_free\_tree 的運作步驟**
1. **定位到要刪除的節點指標**
```c
block_t **node_ptr = find_free_tree(root, target);
```
`node_ptr` 指向「指向目標節點的那個指標」（pointer-to-pointer），方便後面直接改寫它。
2. **如果有兩個子節點**
* 必須找一個「替身」來頂替自己，常用中序前驅 (in-order predecessor)。
* 前驅定義：左子樹裡最大的那個 → 往左一次，再一路往右跑到底。
* 有了 `pred_ptr` 指向前驅節點的指標之後，分兩種情況：
1. **前驅就是左子節點**
```c
if (*pred_ptr == (*node_ptr)->l) {
block_t *old_right = (*node_ptr)->r;
*node_ptr = *pred_ptr; // 左子節點取代自己
(*node_ptr)->r = old_right; // 接回原本的右子樹
}
```
2. **前驅在更深處**
```c
else {
block_t *old_left = (*node_ptr)->l;
block_t *old_right = (*node_ptr)->r;
block_t *pred_node = *pred_ptr;
remove_free_tree(&old_left, *pred_ptr);
*node_ptr = pred_node; // 用前驅頂替自己
(*node_ptr)->l = old_left; // 接回拆掉的左子樹
(*node_ptr)->r = old_right; // 接回原本的右子樹
}
```
3. **只有一邊子節點或沒有子節點**
```c
else if ((*node_ptr)->l || (*node_ptr)->r) {
*node_ptr = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
} else {
*node_ptr = NULL;
}
```
－ 若只有一個子節點，就讓它直接頂上來；若都沒有，直接把指標設 `NULL`。
4. **清理原目標節點指標**
```c
target->l = target->r = NULL;
```
避免外面還留著懸空指標。
---
**為什麼要找左子樹最右邊**？
* 前驅要比 `target->size` 小（必在左子樹），又要是所有小於它之中「最大的」。
* 在 BST 上，左子樹的每個節點都小於根，而最右邊的那個正是最大值，所以往右跑到底就對了。
---
整段程式利用 **pointer-to-pointer** 技巧，將各種指標重連都改寫在 `*node_ptr` 或 `*pred_ptr` 上，免去處處判頭尾、記前驅父節點等繁瑣分支。
#### 嘗試補完程式碼，使其可獨立執行
`find_free_tree` 在二元搜尋樹中找到大於或等於 target 值的最小節點，並返回指向該節點的指標。
```c
block_t **find_free_tree(block_t **root, block_t *target)
{
if (!(*root))
return root;
if ((*root)->size >= target->size) {
block_t **left = find_free_tree(&(*root)->l, target);
return (*left) ? left : root;
}
return find_free_tree(&(*root)->r, target);
}
```
`print_tree`採用 中序遍歷 (in-order traversal) 來印出整棵二元搜尋樹（BST），順序為：
先走左子樹 -> 印出當前節點 -> 再走右子樹
```c
void print_tree(block_t *root) {
if (!root)
return;
print_tree(root->l);
printf("%zu ", root->size);
print_tree(root->r);
}
```
測試主程式 `main` ：建樹、刪除並列印每次結果
```c
int main() {
block_t *root = NULL;
// 插入順序：產生值為 (i * 3) % 10 的節點，確保亂中有序且不重複
for (int i = 0; i < 10; i++) {
insert_tree(&root, (i * 3) % 10);
}
print_tree(root);
puts(""); // 印出初始樹狀結構
// 刪除順序：依序以 (i * 4) % 10 模擬實際記憶體釋放情境
block_t dummy;
for (int i = 0; i < 10; i++) {
dummy.size = (i * 4) % 10;
remove_free_tree(&root, &dummy);
print_tree(root);
puts(""); // 每次刪除後印出目前 BST 結構
}
return 0;
}
```
Sign in with Wallet
Connect another wallet