HackMD
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 函式
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 指標則指向接下來要插入的節點。
for (size_t i = 0; i < N; i++)
list_insert_before(&l, l.head, &items[i]);
接著 p 會找到目前 before 指向的節點, *p=item 讓 head 指標指向要插入的節點, item->next = before; ,則讓 item->next 指向原來的第一個節點。
list_insert_before 透過指標的指標 p ，找到目前 before 指向的節點,在此程式中,每次呼叫 list_insert_before before都會指向第一個節點，所以每次節點都會插入在鏈結串列的頭部。
延伸問題
W1Q2
這裡是基於二元搜尋樹管理空閒記憶體區塊，讓記憶體配置器能更有效率地搜尋到合適的區塊。
Free list 是使用鏈結串列管理記憶體區塊，搜尋合適區塊的時間複雜度為 O(N) ，若使用二元搜尋樹管理記憶體區塊，搜尋合適區塊的時間複雜度可為 O(logN)。
remove_free_tree 函式的功能是刪除二元搜尋樹中的某個節點，刪除節點的值就是配置那個大小的記憶體，然而刪除節點會有以下三種情況須討論。
Target沒有子節點
這時target指向 80 ，因為沒有子節點，直接刪除即可。
Target有一個子節點
這時target指向 40 ，我們要用45替代到現在40的位置
在這之前我一直以為 node_ptr 是指向 target 的指標，但看到最後更新的程式碼就一直覺得非常奇怪
/* 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 的註解
/* 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 的那個指標，這樣上面程式碼的更新就會顯得合理了。
Target有兩個子節點
這是最複雜的情形，二元搜尋樹有以下幾個規則需要遵守
- 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值
- 若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值
- 任意節點的左、右子樹也分別為二元搜尋樹
所以當要刪除的節點有兩個子節點時，必須找到該節點的 in-order predecessor 替代其原本的位置，才不會破壞二元搜尋樹的結構。
透過以下程式尋找 in-order predecessor
block_t **pred_ptr = &(*node_ptr)->l;
while (*pred_ptr)->r)
pred_ptr = &(*pred_ptr)->r;
這段程式碼會找到要刪除的節點的左子樹中，最下方且最右邊的節點，也就是 in-order predecessor。
刪除的節點有兩個子節點可分為下列兩種情況
- in-order predecessor 是要刪除節點的左子節點
這情況很簡單，只需要先把要刪除節點的右子樹先備份，將要刪除的節點替換成左子節點後，再將右子樹接回即可。
- in-order predecessor 在左子樹的更深層
這情況需要先將刪除節點的左子樹和右子樹以及 in-order predecessor 先備份，再將再將 in-order predecessor 從左子樹中刪除，再將 in-order predecessor 替代刪除的節點，並把左右子樹接回。
