# 2023q1 Homework4 (quiz4)
contributed by < `DokiDokiPB` >
> 巨集展開後的[程式碼 Github gist](https://gist.github.com/a1091150/b7040acd206d0188d7fbd439c05ad51c)
> 其中用於觀察紅黑樹行為的函式為 `good()`
> 並附上 `printTreeInorder()` 用於印出紅黑樹結構
- 透過以上 [USFCA 大學的 B tree 視覺化工具](https://www.cs.usfca.edu/~galles/visualization/BTree.html) 顯示 2-3 tree
- 使用 [線上工具 ysangkok.github.io](http://ysangkok.github.io/js-clrs-btree/btree.html) 繪製 B-tree 的 Graphviz code
## 測驗 1
撰寫這題時候發現自己缺少閱讀
- 從 GitHub 搜尋簡單的程式碼與介紹，初步了解最基本的紅黑樹與 B tree 介紹。
- [anandarao/Red-Black-Tree 實作](https://github.com/anandarao/Red-Black-Tree/blob/master/RBTree.cpp#L93)
- [資料結構與演算法：Red Black Tree 紅黑樹 part 1 by Joseph](https://josephjsf2.github.io/data/structure/and/algorithm/2020/04/28/red-black-tree-part-1.html)
- 閱讀教材的簡報 [Left-Leaning Red-Black Trees](https://hackmd.io/@sysprog/linux-rbtree)，照著簡報中了解 LLRBT 對應的 2-3 樹與 2-3-4 樹。
- [Nicholas Tsai B Tree Deletion](https://yu-shin.github.io/posts/fc4bcf8f/)
:::info
其中以下撰寫的內容的核心概念：
$\rightarrow$ 原本 2-3 樹或 2-3-4 樹對應多種紅黑樹，但是限制為左傾紅黑樹後，便成為一對一的關係，只對應一種紅黑樹。
因此在了解原理與程式碼運作上，可以先透過 2-3 樹行為去了解紅黑樹插入與移除行為。
:::
### 了解其原理
根據註釋，這裡使用的是 `C macro implementation of left-leaning 2-3 red-black trees.`
#### `tree_insert()` 函式
透過 [USFCA 大學的 B tree 視覺化工具](https://www.cs.usfca.edu/~galles/visualization/BTree.html) 加入節點，可以很好的了解依序輸入後獲得的 2-3 樹，就能對照 `tree_insert()` 函式行為。
將巨集 `x_attr void x_prefix##insert(x_rbt_type *rbtree, x_type *node)` 展開為 `static void tree_insert (tree_t *rbtree, node_t *node)`，並分成三段程式碼。這裡主要展示第二段與第三段
- 第一段程式碼：紅黑樹也是一種二元搜尋樹，紀錄走訪過的節點
- 第二段程式碼：透過修改顏色的方式，消去 4 樹成為 2 樹與 3 樹
- 第三段程式碼：將 4 樹分裂、將 2 樹右傾改為左傾
在以下圖例中，節點元素有 `*` 表示當前 `*cnode` 指向的節點
<!--
```c
// 第一段程式碼
tree_path_entry_t path[(sizeof(void *) << 4)];
tree_path_entry_t *pathp;
path->node = rbtree->root;
for (pathp = path; pathp->node; pathp++)
{
int cmp = pathp->cmp = node_cmp(node, pathp->node);
if (cmp < 0)
pathp[1].node = rbtn_left_get(node_t, link, pathp->node);
else
// pathp[1].node = ((node_t *)(((intptr_t)(pathp->node)->link.right_red) & ~3));
pathp[1].node = rbtn_right_get(node_t, link, pathp->node);
}
pathp->node = node;
```
第一段程式碼：
- `cmp` 標示節點的傾向
- `pathp` 紀錄走訪過的節點、`pathp[1].node` 為下一個走訪的節點
- 紅黑樹的顏色標示是放在 `link.right_red` 最低 1 個位元
- 0 表示黑色、 1 表示紅色
-->
##### 第二段程式碼
```c
for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) { \
x_type *cnode = pathp->node; \
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(node_t, link, leftleft); \
rbtn_rotate_right(x_type, x_field, cnode, tnode); \
cnode = tnode; \
} \
} else { \
/* ... */ \
} \
pathp->node = cnode; \
}
```
:::danger
使用 `clang-format` 對上述程式碼進行一致排版，確保以 4 個空白縮排。
:notes: jserv
:::
插入 1 元素之後，對應的示例圖
```graphviz
digraph BST {
graph [ratio=.44 ordering="out"];
node [style=filled, shape=circle, width=.6
fontname=Helvetica, fontweight=bold, fontcolor=black,
fontsize=36, fixedsize=true, fillcolor=white];
{rank = same; 2};
1, 2
[color=red];
3
[color=black, label="3*"];
n1, n2
[fontsize=0, fillcolor=white, color=transparent];
3 -> 2;
2 -> 1;
3 -> n1 [color="transparent"];
2 -> n2 [color="transparent"];
}
```
轉換成
```graphviz
digraph BST {
graph [ratio=.44 ordering="out"];
node [style=filled, color=red, shape=circle, width=.6
fontname=Helvetica, fontweight=bold, fontcolor=black,
fontsize=36, fixedsize=true, fillcolor=white];
{rank = same; 1;3};
3, 1
[color=black];
2
[label="2*"]
2 -> 1;
2 -> 3;
}
```
若 2 為根節點，則最終會被標注為黑色
##### 第三段程式碼
```c
for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) \
{ \
x_type *cnode = pathp->node;
if (pathp->cmp < 0) \
{
...
}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; \
}
}
pathp->node = cnode;
}
```
對應 `else case /* Lean left. */` 的程式碼，以示例圖表示其運作方式：
插入元素 7 之後，依據左傾的規定，必須左旋
```graphviz
digraph BST {
graph [ratio=.44 ordering="out"];
node [style=filled, color=red, shape=circle, width=.6
fontname=Helvetica, fontweight=bold, fontcolor=black,
fontsize=36, fixedsize=true];
4,5,7
[fillcolor=white];
4,5
[fillcolor=white, color="black"];
6
[fillcolor=white, color="black", label="6*"];
n1, n2
[fontsize=0, fillcolor=white, color=transparent];
5 -> 4;
5 -> 6;
6 -> n1 [color="transparent"];
6 -> 7;
}
```
轉換成
```graphviz
digraph BST {
graph [ratio=.44 ordering="out"];
node [style=filled, color=red, shape=circle, width=.6
fontname=Helvetica, fontweight=bold, fontcolor=black,
fontsize=36, fixedsize=true, fillcolor=white];
4, 5
[fillcolor=white, color="black"];
7
[fillcolor=white, color="black", label="7*"];
n1, n2
[fontsize=0, fillcolor=white, color=transparent];
5 -> 4;
5 -> 7;
7 -> 6;
7 -> n1 [color="transparent"];
}
```
這裡以再加入一個元素 8 作為範例，對應 `if case` 的程式碼，分裂 4 樹
```graphviz
digraph BST {
graph [ratio=.44 ordering="out"];
node [style=filled, color=red, shape=circle, width=.6
fontname=Helvetica, fontweight=bold, fontcolor=black,
fontsize=36, fixedsize=true, fillcolor=white];
4, 5
[fillcolor=white, color="black"];
7
[fillcolor=white, color="black", label="7*"];
8;
5 -> 4;
5 -> 7;
7 -> 6;
7 -> 8;
}
```
轉換成
```graphviz
digraph BST {
graph [ratio=.44 ordering="out"];
node [style=filled, color=red, shape=circle, width=.6
fontname=Helvetica, fontweight=bold, fontcolor=black,
fontsize=36, fixedsize=true, fillcolor=white];
4, 5,6 ,8
[fillcolor=white, color="black"];
7
[fillcolor=white, color="red", label="7*"];
8;
5 -> 4;
5 -> 7;
7 -> 6;
7 -> 8;
}
```
再因為 LLRB 規則， `5*` 要左旋，從
```graphviz
digraph BST {
graph [ratio=.44 ordering="out"];
node [style=filled, color=red, shape=circle, width=.6
fontname=Helvetica, fontweight=bold, fontcolor=black,
fontsize=36, fixedsize=true, fillcolor=white];
4, 5,6 ,8
[fillcolor=white, color="black"];
5
[fillcolor=white, color="black", label="5*"];
8, 7;
5 -> 4;
5 -> 7;
7 -> 6;
7 -> 8;
}
```
轉換成
```graphviz
digraph BST {
graph [ratio=.44 ordering="out"];
node [style=filled, color=red, shape=circle, width=.6
fontname=Helvetica, fontweight=bold, fontcolor=black,
fontsize=36, fixedsize=true, fillcolor=white];
4,6 ,8
[fillcolor=white, color="black"];
8, 7;
5;
7
[fillcolor=white, color="black", label="7*"];
7 -> 5;
7-> 8;
5 -> 6;
5 -> 4;
}
```
#### `tree_remove()` 函式
我決定直接跑一遍來看程式碼的作用。
在 ChatGPT 出來後，工程師寫程式碼的效率可以更高，其中<s>對於絕大多數的軟體工程師</s>，閱讀如紅黑樹移除節點的複雜程式碼，第一時間都無法知道或驗證程式碼作用。
:::warning
自己不懂的話，不要拉其他人下水。
:notes: jserv
:::
紅黑樹本身是 2-3 樹或 2-3-4 樹的變形，移除某個節點產生的平衡行為皆對應 2-3 tree 的操作。
##### 推敲其原理
巨集展開後的程式碼請參考 [`LLRBT_m.cpp`](https://gist.github.com/a1091150/b7040acd206d0188d7fbd439c05ad51c#file-llrbt_m-c-L1)，這裡使用測試資料來了解其中的運作模式。
依序輸入測試資料：`1, 2, 3, 4, 40, 41`，獲得
```graphviz
digraph g {
node [shape = record,height=.1];
node0[label = "<f0> |2|<f1> |4|<f2>"];
node1[label = "<f0> |1|<f1>"];
"node0":f0 -> "node1"
node2[label = "<f0> |3|<f1>"];
"node0":f1 -> "node2"
node3[label = "<f0> |40|<f1> |41|<f2>"];
"node0":f2 -> "node3"
}
```
對應 LLRBT
```graphviz
digraph 這圖片很難調整的二元樹的拉 {
graph [ratio=.44 ordering="out"];
node [style=filled, color=red, shape=circle, width=.6
fontname=Helvetica, fontweight=bold, fontcolor=black,
fontsize=36, fixedsize=true, fillcolor=white];
2, 40;
4, 3, 41, 1
[fillcolor=white, color="black"];
n1, n2, n3
[fontsize=0, fillcolor=white, color=transparent];
4 -> 2;
4 -> 41;
41 -> 40;
41 -> n1 [color="transparent"];
41 -> n2 [color="transparent"];
2 -> 1;
2 -> n3[color="transparent"];
2 -> 3;
}
```
###### 移除元素 2 的節點
依據步驟(這裡以「2」表示元素 2 的節點)：
- 程式碼找到 2 ，並紀錄沿途走過的路徑 `pathp`，紀錄到 2 的中序下一個的節點 3
- 2 與 3 對調，3 變為紅色，2 變為黑色並且被移除，並從 `pathp` 開始往上修正
```graphviz
digraph 這圖片很難調整的二元樹的拉 {
graph [ratio=.44 ordering="out"];
node [style=filled, color=red, shape=circle, width=.6
fontname=Helvetica, fontweight=bold, fontcolor=black,
fontsize=36, fixedsize=true, fillcolor=white];
40, 3;
4, 41, 1, 2
[fillcolor=white, color="black"];
n1, n2, n3
[fontsize=0, fillcolor=white, color=transparent];
4 -> 3;
4 -> 41;
41 -> 40;
41 -> n1 [color="transparent"];
41 -> n2 [color="transparent"];
3 -> 1;
3 -> n3[color="transparent"];
3 -> 2;
}
```
- 往上走訪過程對應到以下程式碼，`pathp->node` 為 3，此時修改程指定的顏色，3 修改為黑色，1 修改為紅色。樹平衡並離開函式。
```c
if (leftleft && rbtn_red_get(x_type, x_field, leftleft)) {
/* ... */
}else{
/* || */
/* pathp(r) */
/* / \\ */
/* (b) (b) */
/* / */
/* (b) */
rbtn_red_set(x_type, x_field, left);
rbtn_black_set(x_type, x_field, pathp->node);
return;
}
```
在使用 GDB 觀察程式碼運作後，會發現這些步驟可以對應 2-3 樹中的行為：
- 原本的 2-3 樹，替換並移除 2 後的圖例：
```graphviz
digraph g {
node [shape = record,height=.1];
node0[label = "<f0> |3|<f1> |4|<f2>"];
node1[label = "<f0> |1|<f1>"];
"node0":f0 -> "node1"
node2[label = "<f0> |X|<f1>"];
"node0":f1 -> "node2"
node3[label = "<f0> |40|<f1> |41|<f2>"];
"node0":f2 -> "node3"
}
```
- 該節點有 underflow，需要進行節點合併，這裡跟左邊節點合併
- 並且將 3 傳入至該合併的節點
```graphviz
digraph g {
node [shape = record,height=.1];
node0[label = "<f0> |4|<f1>"];
node1[label = "<f0> |1|<f1> |3|<f2>"];
"node0":f0 -> "node1"
node2[label = "<f0> |40|<f1> |41|<f2>"];
"node0":f1 -> "node2"
}
```
### 延伸問題開發出的效能評比程式，分析不同 rbtree 實作
xx
Sign in with Wallet
Connect another wallet