owned this note
owned this note
Published
Linked with GitHub
# 2023q1 Homework4 (quiz4)
###### tags: `linux2023`
contributed by < `Paintako` >
## 測驗 `1`
```c
typedef struct { \
x_type *node; \
int cmp; \
} x_prefix##path_entry_t;
```
閱讀前置處理器篇, 得知 `x_prefix##` 是透過 `cpp` 來展開產生程式碼的, 註釋也有提示 :
```c
* x_prefix:
* Prefix for generated functions (e.g., ex_).
```
故產生出來的程式碼會像是 `x_prefix##path_entry_t -> ex_path_entry_t
`
### rb_gen macro
#### insert
這段程式是 `left-leaning 2-3 red-black trees` 的實作
參考 [LLRB](https://sedgewick.io/wp-content/uploads/2022/03/2008-09LLRB.pdf)
插入時, 先找到插入位置, 再從從樹葉一路往上到 root 調整
因為是左傾樹, 所以如果遇到插入時, 所以插入時遇到只有右子時需要往左調整
如果遇到連續兩個紅點 (or link), 則需要做 balance
而遇到 4 樹的情況, 需要做分裂
:::warning
4 樹: node with 3 keys and 4 children
3、4 樹 in RB trees:
* 用 **紅邊** 表示 3、4 樹的邊
* 3樹: 
* 4樹: 
:::
```c
x_prefix##path_entry_t path[RB_MAX_DEPTH]; \
x_prefix##path_entry_t *pathp; \
rbt_node_new(x_type, x_field, rbtree, node); \
/* Wind. */ \
path->node = rbtree->root;
```
一開始不曉得為何 `path` 明明就是宣告成 array 的形式, 但卻可以直接賦值, 但後來想到, path 雖然是一個 array, 但 array 等同於指向 array[0] 的指針, 所以當我們使用 path->node 時, 相當於 path[0].node, 這樣的寫法可以省去紀錄 i, 並且只通過操作指標的方式取得 array 中的成員.
```c
pathp[1].node = rbtn_left_get(x_type, x_field, pathp->node);
```
而這裡為何是 `pathp[1]`? 因為我們只是操作 pointer, 而 pointer 的下一個成員即是樹中的下一個節點.
這邊插入一個新節點時, 從 root 開始比較, 並且把比較的結果 ( cmp ) 以及比較的節點紀錄在 `path` 中
找到要插入的位置後, 看 `path` 中前一個點 (父點) 的資訊, 前一個點中有 `cmp` , 可以得知插入點是屬於左子 ( cmp < 0 ), 或者右子 (cmp > 0)
給定一節點 x, 考慮以下情形:
1. rbtn_rotate_left
2. rbtn_rotate_right
第一種 rotate_left
* 旋轉前:
* 
* 旋轉後:
第二種 rotate_right
* 旋轉前:
* 
* 旋轉後:
```c
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); // AAAA \
rbtn_rotate_right(x_type, x_field, cnode, tnode); \
cnode = tnode; \
}
```
此段程式碼是檢查出現連續兩紅點的情形, 如果連續出現兩個紅點, 則旋轉調整, 而調整完後是 4 樹, 所以這邊先對 `leftleft` 調整成黑點, 則在調整完後, 就已經是 4 樹分裂的情形.
```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); // BBBB \
rbtn_red_set(x_type, x_field, cnode); // CCCC \
cnode = tnode; \
} \
} \
pathp->node = cnode; \
}
```
上面的是考慮 `插入的點 > 比較節點` 的情形, 如圖示
這種情況下, 比較節點有兩種情形:
1. 沒有左子, 或者左子不是紅的 :
這種情況, 會先紀錄 cnode 的顏色, 並且左旋轉, 旋轉上來的 tnode 設為 cnode 的顏色, 並且因為旋轉後的 cnode 改成紅色, 並且往上繼續檢查
2. 有左子, 並且左子是紅的, 也就是 4 樹, 如下圖:
這種情形只需調整顏色即可
:::danger
Todo:
圖表改成 `Graphviz` & `TreeComparison`
:::
#### remove
```c=
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; // DDDD \
nodep = pathp; \
for (pathp++; pathp->node; pathp++) { \
pathp->cmp = -1; \
pathp[1].node = \
rbtn_left_get(x_type, x_field, pathp->node); \
} \
break; \
} \
}
```
要刪除某個節點時, 一樣先從 root 一路往下尋找要刪除的點, 這邊我們假設已經找到要刪除的點, 用一個指針 `nodep` 記錄刪除地址, 再來往右子樹開始找, 找到 `右子樹中最小的點`, 作為替代點, 這也就是為何 `pathp->cmp` (第5行) 要設為 1 的原因.
接著, 判斷刪除點是否有 successor, 有的話把此點拉上來替代
這個點有三種情況:
* case1: 是 right-least (右子樹中最小的)
* case2: 沒有右子但有左子
* case3: 這個樹只有刪除點一點
首先是第一種情況: 後繼者在右子樹當中
```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)); \
rbtn_left_set(x_type, x_field, pathp->node, \
rbtn_left_get(x_type, x_field, node)); \
/* If node's successor is its right child, the following code */ \
/* will do the wrong thing for the right child pointer. */ \
/* However, it doesn't matter, because the pointer will be */ \
/* properly set when the successor is pruned. */ \
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); \
/* The pruned leaf node's child pointers are never accessed */ \
/* again, so don't bother setting them to nil. */ \
nodep->node = pathp->node; \
pathp->node = node; \
if (nodep == path) { \
rbtree->root = nodep->node; \
} else { \
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); \
} \
}
```
1. 先找到後繼者的位置 `pathp`, 並把連結顏色 assign 給後繼者
2. 再來把要刪除節點 node 的左右子點 assign 給後繼者, 就可以把 node 給移除了
3. 移除後, 判斷後繼者的位置, 如果他是 root, 代表此點沒有雙親, 反之, 找出他的父母並 assign 給此點
再來考慮第二種情況, 也就是沒有右子, 但是有左子的情況, 有左子同樣判斷以下條件:
1. 如果找到後繼者的位址 == pathp, 也就是找到的位置位於樹根, 那麼將 root 的位址改成刪除點的左子
2. 不是以上情況, 只要把左子拉到刪除的位置並且 assign 他的左右父點即可
最後是第三種情況, 刪除點的位置位於 root, 這時只需要判斷 `nodep == path` 即可確定是不是刪除點 = root
Google Drive
Gist
Clipboard
Sign in with Wallet
