# Linux 核心專題: 紅黑樹實作研究
> 執行人: LiChiiiii
> [GitHub](https://github.com/LiChiiiii/lab0-c)
> [專題解說錄影](https://youtu.be/QUbCfCwSl3I)
:::success
:question: 提問清單
* 是否可以 `lab0-c` 原本的 list-sort 對後續整合的 tree-sort 進行效能比較，並針對結果分析?
* 紅黑樹實作的效能評比部分僅列出實驗數據，並沒有針對圖表進行分析
:::
## 任務描述
重做[第 3 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz3) 的測驗一及[第 4 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz4)的測驗一，深入理解紅黑樹的實作考量。
## TODO: 重做紅黑樹相關測驗題
重做[第 3 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz3) 的測驗一及[第 4 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz4)的測驗一，彙整其他學員的成果，連同延伸問題，比照〈[Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree)〉的風格進行報告。
### 對第 3 週測驗 [treesort.c](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401) 程式碼的理解
定義一個結構 `node_t` ，其中 `color` 代表節點顏色， `left` 和 `right` 分別代表紅黑樹的左子節點和右子節點，`next` 代表在原始陣列中下一個節點， `value` 代表節點的值。
```c
typedef struct __node {
uintptr_t color;
struct __node *left, *right;
struct __node *next;
long value;
} node_t __attribute__((aligned(sizeof(long))));
```
定義一個結構 `cmap_internal` 記錄整個 `map` 的資訊，有 `key`, `element`, `map` 的 size, 也記錄了 `end`, `most`, `least` 和比較的函式 `comparator`。
```c
struct cmap_internal {
node_t *head;
/* Properties */
size_t key_size, element_size, size;
cmap_iter_t it_end, it_most, it_least;
int (*comparator)(void *, void *);
};
```
為了節省記憶體空間，這裡把親代節點的位址存在 `uintptr_t color` 的最高位中。在 64 位元的系統中，考慮到 alignment，記憶體以 8 bytes 為一個單位進行管理，也就是說 `node_t` 的位址的最後 3 個 bits 一定為 0 ，因此只要對給定的引數 `(r)` 清除後面 3 個 bits 就可以得到親代節點的位址，並且在引數 `(r)` 最後一個 bit 存放顏色信息， `(r)->color & 1` 取出最後一個 bit 。
```c
#define rb_parent(r) ((node_t *) ((r)->color & ~7))
#define rb_color(r) ((color_t) (r)->color & 1)
```
而在設定顏色時，以 bitwise 操作，若節點是紅色則設定最後一個bit 為 0 ，反之。
```c
#define rb_set_red(r) do { (r)->color &= ~1; } while (0)
#define rb_set_black(r) do { (r)->color |= 1; } while (0)
```
程式碼內的 `cmap_l_l`, `cmap_l_r`, `cmap_r_r`, `cmap_r_l` 代表在平衡紅黑樹時會處理的四種情況，並會在 `cmap_fix_colors` 裡呼叫。
`cmap_insert()` 是在紅黑樹中插入節點的功能，若比較結果 `res` 小於零代表往左邊走，否則往右邊走，直到走訪到的節點為 NULL，或迴圈結束，即插入節點。
`tree_sort()` 會建立一個 map 配置 key 和 element 足夠的空間，接著在 while 迴圈將 list 中的每個節點一個一個插入 map 中。定義 `*node` 為 map 中擁有最小值的節點，透過 for 迴圈，從最左子開始在紅黑樹找到下一個節點（`cmap_next(node)` ），由小到大放入 list 中，完成 sort 功能。
```c
void tree_sort(node_t **list)
{
node_t **record = list;
cmap_t map = cmap_new(sizeof(long), sizeof(NULL), cmap_cmp_int);
while (*list) {
cmap_insert(map, *list, NULL);
list = &(*list) -> next ;
}
node_t *node = cmap_first(map), *first = node;
for (; node; node = cmap_next(node)) {
*list = node;
list = &(*list) -> next ;
}
*list = NULL;
*record = first;
free(map);
}
```
### 將 [treesort.c](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401) 整合到 lab0-c ，探討 tree sort 的效率
> [commit f9b2abb](https://github.com/LiChiiiii/lab0-c/commit/f9b2abb207b6f3145ab6241de80396ce7fc6a662)
#### 定義結構體
改寫 [treesort.c](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401) ，利用 lab0-c 定義的 `list_head` ，串接每一個 node。
`value` 的型態從原本的改成 `long` 改成 `char*` ，讓排序不限於數字。
```c
struct rb_node {
uintptr_t color;
struct rb_node *left, *right;
char *value;
}__attribute__((aligned(sizeof(long))));
```
```c
typedef struct __node {
struct rb_node RBnode;
struct list_head *list;
} node_t ;
```
```graphviz
digraph structs {
rankdir = LR;
node [shape=record, style=bold];
subgraph cluster_1{
node [shape=record];
node_1[label="<f1>list"];
subgraph cluster_A {
rbnode_1 [label="<f0> color|<f1> left|<f2> right|<f3> value", width=2.0];
style = "dashed, bold";
label = "RBnode";
color = red;
};
label = "node_t";
};
subgraph cluster_2{
node [shape=record];
node_2[label="<f1>list"];
subgraph cluster_B {
rbnode_2 [label="<f0> color|<f1> left|<f2> right|<f3> value", width=2.0];
style = "dashed, bold";
label = "RBnode";
color = red;
};
label = "node_t";
};
node_1:list:label -> node_2:list:label
node_2:list:label -> node_1:list:label
}
```
因此改寫 `cmap_cmp_int` 程式碼，變成 `cmap_cmp_str` 用以比較字串大小。
```c
static inline int cmap_cmp_str(void *arg0, void *arg1)
{
char *a = (char *) arg0, *b = (char *) arg1;
int result = strcmp(a, b);
return result < 0 ? _CMP_LESS : result > 0 ? _CMP_GREATER : _CMP_EQUAL;
}
```
可以使用 `struct *rb_node` 作為走訪節點的通用迭代器。
改寫 `cmap_internal` 程式碼，用以表示整個 `map` 的資訊。
```c
struct cmap_internal {
struct rb_node *head;
/* Properties */
size_t key_size, element_size, size;
struct rb_node it_end, it_most, it_least;
int (*comparator)(void *, void *);
};
```
#### 建立節點
傳入的參數為定義的結構體 `node_t` 裡的 `list_head` 結構，並透過 `cmap_create_node()` 來初始化 `node_t` 內的 `rb_node`。
```c
node_t *list_make_node(struct list_head *list) {
node_t *node = malloc(sizeof(node_t));
node->list = list;
node->RBnode.value = ((element_t *)list_entry(list, element_t, list))->value;
cmap_create_node(node);
return node;
}
```
```c
node_t *cmap_create_node(node_t *node){
node->RBnode.left = node->RBnode.right = NULL;
rb_set_parent(&(node->RBnode), NULL);
rb_set_red(&(node->RBnode));
return node;
}
```
#### 釋放 tree 所用到的空間
利用 DFS 方法走所有節點並釋放記憶體。
```c
void tree_free(struct rb_node *node){
if (!node)
return;
tree_free(node->left);
tree_free(node->right);
free(container_of(node, node_t, RBnode));
}
```
#### 節點旋轉及顏色變換的操作
更改 [treesort.c](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401) 內所有操作紅黑樹節點旋轉及顏色變換之函式的結構體，將 `node_t` 改成 `rb_node`。
#### 尋找最小節點
先檢查紅黑樹的根節點 `obj->head` 是否存在，如果根節點存在，則進入迴圈。迴圈的目的是往左子樹移動，一直到達最左端的節點。返回最左端節點的地址，因為紅黑樹中的節點是通過 `struct rb_node` 結構嵌入到 `node_t` 結構中的，所以需要使用 `container_of` 宏來找到 `node_t` 結構的起始地址。
```c
node_t *cmap_first(cmap_t obj) {
struct rb_node *n = obj->head;
if (!n)
return NULL;
while (n->left)
n = n->left;
return (node_t *)container_of(n, node_t, RBnode);
}
```
#### 尋找下一個節點
在紅黑樹中找到給定節點的下一個節點，並以 `node_t` 結構的指標形式返回。它通過判斷節點的右子節點和父節點的關係來確定下一個節點的位置，並使用 `container_of` 宏計算出相應的 `node_t` 結構的指標。
```c
node_t *cmap_next(node_t *node) {
if (!node)
return NULL;
if (node->RBnode.right) {
node = (node_t *)container_of(node->RBnode.right, node_t, RBnode);
while (node->RBnode.left)
node = (node_t *)container_of(node->RBnode.left, node_t, RBnode);
return node;
}
struct rb_node *parent;
while ((parent = rb_parent(&(node->RBnode))) && &(node->RBnode) == parent->right)
node = (node_t *)container_of(parent, node_t, RBnode);
return parent ? (node_t *)container_of(parent, node_t, RBnode) : NULL;
}
```
#### 插入節點
功能及做法相同，根據新定義的結構體，更改 [treesort.c](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401) 內`cmap_insert()` 使用到函式之參數的結構體。
#### tree sort
此函式利用紅黑樹將原始鏈表中的元素進行排序，然後重新連結這些元素，使它們按照排序順序形成一個新的鏈表，最後釋放相關的記憶體。
Tree sort 主要分成兩個部分，分別是建立紅黑樹並在走訪樹來將佇列排序。
1. 建立紅黑樹，利用 list.h 裡的 `list_for_each` 迴圈遍歷傳入指向佇列的 `head` 指標，將每個節點轉換為 `node_t` 結構，並插入到 `map` 紅黑樹中。
```c
void tree_sort(struct list_head *head) {
cmap_t map = cmap_new(sizeof(long), sizeof(NULL), cmap_cmp_str);
struct list_head *list;
list_for_each(list, head) {
node_t *node = list_make_node(list);
cmap_insert(map, node, NULL);
}
...
}
```
2. 從 `map` 紅黑樹中取出第一個節點作為起始節點 `node` ，使用 `cmap_next` 函式獲取下一個節點 `next`，並進行以下迴圈遍歷操作：
* 從原始佇列中移除節點 `next->list`。
* 將節點 `next->list` 插入到 `node->list` 之前，即將節點按照排序順序插入到佇列中。
* 更新 `node` 為 `next`，以便進行下一輪迴圈。
```c
node_t *node = cmap_first(map);
if (!node) {
free(map);
return;
}
for (node_t *next = cmap_next(node); next; next = cmap_next(next)) {
list_del(next->list);
list_add(next->list, node->list);
node = next;
}
```
最後釋放記憶體
```c
tree_free(map->head);
free(map);
```
#### 修改 `qtest.c`
引入 option，讓 `qtest` 得以在執行時期切換不同的排序實作，有助於後續分析。
新增條件式 `if (is_enable_tree_sort) ` ，當輸入命令 `option tree_sort 1`，即可使用 `tree_sort` 進行排序
```c
bool do_sort(int argc, char *argv[])
{
...
if (current && exception_setup(true))
{
if (is_enable_tree_sort) {
tree_sort(current->q);
} else {
q_sort(current->q);
}
}
...
}
```
並在 `console_init` 函式中加入對應的 option 的參數
```c
add_param("tree_sort",
&is_enable_tree_sort, "Enable red black tree sort", NULL);
```
#### 實際執行測試
對數字做排序
```shell
cmd> show
Current queue ID: 0
l = [8 7 1 9 4 6 5 3 2]
cmd> option tree_sort 1
cmd> sort
l = [1 2 3 4 5 6 7 8 9]
```
對字母做排序
```shell
cmd> it RAND 5
l = [cajcwse umryjwxb puhyhrinu ziompt kmzif]
cmd> option tree_sort 1
cmd> sort
l = [cajcwse kmzif puhyhrinu umryjwxb ziompt]
```
隨機產生 10000 筆資料計算 tree sort 排序時間
```shell
cmd> it RAND 10000
l = [cytzpsri hmcbl nxrdcxzb wnhiudpi yrmalec bahpslek lnytyc gjuzkk uptwhevm yvcwllv fwxznfpy inhmgmvg gqiwobwgc hykmtpi cdmnkg ujrhylszl kvvojtzb sdcht wzhhm tlrjj qcsidq jhapssga dpejiu gxnvg gsztahcbw twoyuzmpz ikiomm fstavbq rybee txnffxew ... ]
cmd> option tree_sort 1
cmd> time sort
l = [aaekaamj aaery aahlqgqnd aaidup aajsmj aalswiy aaptsp aapzpdfb aavixwyig aaxvzp aaykobgl abdtywi abetyf abgrvq abijuxdii abipvffyr abjlsfaj abjxcgc abkahhy abkaimkpk ablomtzf abohmr abopusld abpnniib abrow abseaup abssul abuco abvnvss abxxl ... ]
Delta time = 0.119
```
`tree_sort` 平均五次下來為 `0.134` s
> 參考 [willwillhi1](https://hackmd.io/@willwillhi/treesort#tree_sort) 的作法
### 對第 4 週測驗 [LLRBT](https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf) 程式碼的理解
在測驗一提供的程式碼中定義
```c
#define rb_node(x_type)
struct{
x_type *left, *right_red;
}
```
這裡的 `rb_node` 定義了紅黑樹中的節點結構，其中 `x_type` 是節點的數據類型。該結構包含了 `left` 和 `right_red` 兩個成員指標。
`left` 指向節點的左子節點，而 `right_red` 指向節點的右子節點，同時它的最低有效位（Least Significant Bit）儲存節點的顏色信息（紅色或黑色），以此原理精簡紅黑樹節點佔用的空間。
```c
typedef rb_tree(node_t) tree_t;
rb_gen(static, tree_, tree_t, node_t, link, node_cmp);
```
對照 [rb.h](https://gist.github.com/jserv/6610eb56bf2486979c8bf6ee8061f71c) 之巨集的使用，展開 `rb_gen(static, ex_, ex_t, ex_node_t, ex_link, ex_cmp)` 巨集可以得到插入、刪除等功能之函式。
#### 新增節點操作 `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)` ，此函式將新節點插入紅黑樹中，主要有三個步驟：
1. 根據節點的比較結果遞迴查找插入位置
2. 依次從下往上檢查是否需要旋轉
3. 將根節點設為黑色。
舉個例子來說，現在有一個紅黑樹。
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
2[fillcolor=red]
A,B,C,D,E,F[fontsize=0,color=transparent]
7 -> {2 11}
2 -> {1 5}
1 -> {A B}
5 -> {C D}
11 -> {E F}
}
```
我們想插入新的節點 `3`，會先用 BST 的概念尋找插入的位置。
1. `3` 與 `7` 比較，紀錄 cmp = -1 ，並往左進行下一層尋找。
2. `3` 與 `2` 比較，紀錄 cmp = 1 ，並往右進行下一層尋找。
3. `3` 與 `5` 比較，紀錄 cmp = -1 ，並往左進行下一層尋找，得到 NULL 跳出迴圈，把插入位置指向此節點，也就是 `pathp->node = node` 。
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
2,3[fillcolor=red]
A,B,C,D,E,F[fontsize=0,color=transparent]
7 -> {2 11}
2 -> {1 5}
1 -> {A B}
5 -> {3 D}
11 -> {E F}
}
```
由於在尋找插入的位置的過程中，有依序紀錄經過每個節點及其 cmp 至名為 path 的陣列，因此當找到插入位置的同時，也得到了以下陣列 path 。
```graphviz
digraph path{
// node [shape=plaintext, fontcolor=black, fontsize=18];
// "Pointers:" -> "Values:" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
pointers [label="<f0> | <f1> | <f2>pathp |<f3> pathp[1]", color=white];
values [label="<f0> 7, -1 | <f1> 2, 1 | <f2> 5, -1 | <f3> 3", fillcolor=pink, style=filled];
// { rank=same; "Pointers:"; pointers }
// { rank=same; "Values:"; values }
edge [color=black];
pointers:f2 -> values:f2;
pointers:f3 -> values:f3;
}
```
接下來將 pathp 反向回去，判斷每個 pathp 的 cmp 值來檢查是否需要旋轉。
如果 cmp < 0 ，且出現左邊狀況則進行旋轉成下圖右側。
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.7]
left, leftleft [fillcolor=red]
A,B[fontsize=0,color=transparent]
cnode -> left
cnode -> A [color=transparent]
left -> leftleft
// left -> B [color=transparent]
left_[fillcolor=red]
A,B[fontsize=0,color=transparent]
left_ -> leftleft_
left_ -> cnode_
}
```
```c
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(x_type, x_field, leftleft);
rbtn_rotate_right(x_type, x_field, cnode, tnode);
cnode = tnode;
}
```
如果 cmp >= 0 ，
1. 出現左邊狀況則進行顏色轉換設定成下圖右側。
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.7]
left, right [fillcolor=red]
cnode -> left
cnode -> right
cnode_[fillcolor=red]
cnode_ -> left_
cnode_ -> right_
}
```
2. 出現左邊狀況則進行旋轉成下圖右側。這邊是為了滿足 LLRBT 的左傾條件。
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.7]
tnode [fillcolor=red]
null, null1[fontsize=0,color=transparent]
cnode -> null[color=transparent]
cnode -> tnode
cnode_[fillcolor=red]
tnode_ -> cnode_
tnode_ -> null1[color=transparent]
}
```
```c
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, BBBB);
rbtn_red_set(x_type, x_field, cnode);
cnode = tnode;
}
```
最後將根節點設為黑色。
#### 刪除節點操作 `tree_remove()`
將巨集 `x_attr void x_prefix##remove(x_rbt_type *rbtree, x_type *node)` 展開為 `static void tree_remove(tree_t *rbtree, node_t *node)` ，此函式用於刪除紅黑樹中的節點，跟 `tree_insert()` 一樣的方式去尋找要刪除的節點，只是額外加上 `if(cmp==0)` ，若條件式成立，則表示找到要刪除的節點，接著就是找出節點的 successor ，來為交換做準備。
舉個例子來說，現在有一個紅黑樹，我想刪除節點 `2`。
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
2[fillcolor=red]
A,B,C,D,E,F[fontsize=0,color=transparent]
7 -> {2 11}
2 -> {1 5}
1 -> {A B}
5 -> {C D}
11 -> {E F}
}
```
可以得到這個 path 陣列。
```graphviz
digraph path{
// node [shape=plaintext, fontcolor=black, fontsize=18];
// "Pointers:" -> "Values:" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
pointers [label="<f0> | <f1>pathp ", color=white];
values [label="<f0> 7, -1 | <f1> 2, -1 ", fillcolor=pink, style=filled];
// { rank=same; "Pointers:"; pointers }
// { rank=same; "Values:"; values }
edge [color=black];
pointers:f1 -> values:f1;
}
```
在 `cmp == 0` 時，代表找到想刪除的節點，也就是找到節點 `2`，會設定 pathp->cmp = 1 ，並尋找此節點的 successor 。
```c
if (cmp == 0) {
/* Find node's successor, in preparation for swap. */
pathp->cmp = 1;
nodep = pathp;
for (pathp++; pathp->node; pathp++) {
pathp->cmp = -1;
pathp[1].node = rbtn_left_get(x_type, x_field, pathp->node);
}
break;
}
```
因此 path 陣列會變成
```graphviz
digraph path{
// node [shape=plaintext, fontcolor=black, fontsize=18];
// "Pointers:" -> "Values:" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
pointers [label="<f0>pathp[-1] | <f1>pathp | <f2>pathp[1] ", color=white];
values [label="<f0> 7, -1 | <f1> 2, 1 | <f2> 1, -1", fillcolor=pink, style=filled];
// { rank=same; "Pointers:"; pointers }
// { rank=same; "Values:"; values }
edge [color=black];
pointers:f0 -> values:f0;
pointers:f1 -> values:f1;
pointers:f2 -> values:f2;
}
```
接著確定要拿來替代的節點 `pathp->node` 不是欲刪除的節點後，將兩者的顏色和左右子樹及在 path 陣列中的位置交換。
此時紅黑樹會變成
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
1[fillcolor=red]
A,B,C,D,E,F[fontsize=0,color=transparent]
7 -> {1 11}
1 -> {2 5}
2 -> {A B}
5 -> {C D}
11 -> {E F}
}
```
`nodep` 的 `node` 指向後繼者節點（successor node），`pathp` 的 `node` 指向要刪除的節點，path 陣列會變成
```graphviz
digraph path{
// node [shape=plaintext, fontcolor=black, fontsize=18];
// "Pointers:" -> "Values:" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
pointers [label="<f0>| <f1>nodep | <f2>pathp ", color=white];
values [label="<f0> 7, -1 | <f1> 1, -1 | <f2> 2, 1", fillcolor=pink, style=filled];
// { rank=same; "Pointers:"; pointers }
// { rank=same; "Values:"; values }
edge [color=black];
pointers:f1 -> values:f1;
pointers:f2 -> values:f2;
}
```
最後移除 `pathp->node`，移除掉欲刪除的節點。
若欲刪除節點是紅色，則可以直接移除，不影響樹的平衡（如上述範例）；若欲刪除節點是黑色，則沿著 path 陣列反向走訪經過的節點，並根據狀態作出平衡。
### 兩種紅黑樹實作方式比較
| 特徵 | Tree Sort | LLRBT |
| -------------- | -------------------------------------------------- | -------------------------------------------------- |
| 節點結構 | 包含==左子節點、右子節點和親代節點==的指標 | 包含==左子節點和右子節==點的指標，無親代節點直接紀錄 |
| 節點操作方式 | 通過節點的親代指標==直接獲取和操作==親代節點 | 使用==額外的路徑陣列==追蹤操作路徑並對紅黑樹進行平衡 |
| 空間佔用 | 需要額外的指標記錄親代節點，**佔用更多的內存空間** | 不需要額外的指標記錄親代節點，節省內存空間 |
| 平衡操作複雜度 | 平衡操作相對較簡單，直接==通過指標修改==節點的親代關係 | 平衡操作較複雜，需要使用==陣列記錄路徑==並進行調整 |
| 適用場景 |操作和追蹤節點的親代關係較為頻繁的場景 | 節點操作和平衡操作頻率較低的場景 |
:::warning
上述程式碼已整合進 [rv32emu](https://github.com/sysprog21/rv32emu):
* [map.h](https://github.com/sysprog21/rv32emu/blob/master/src/map.h)
* [map.c](https://github.com/sysprog21/rv32emu/blob/master/src/map.c)
* [test-map.c](https://github.com/sysprog21/rv32emu/blob/master/tests/map/test-map.c)
撰寫測試/效能評比程式碼時，可對照運用。
:notes: jserv
:::
## TODO: 紅黑樹實作的效能評比
利用 [rb-bench](https://github.com/jserv/rb-bench)，分析不同紅黑樹實作手法的差異，應當考慮更大的資料範圍
> 對照 [rbtree_bench](https://github.com/ypaskell/rbtree_bench)
### 使用 [rb-bench](https://github.com/jserv/rb-bench)
依序執行
```shell
make all
./rb-bench > reports/test-linux-emag.xml
./plot.py reports/test-linux-emag.xml reports/test-linux-emag.png
```
得到以下這張圖
在 `test.h` 宣告一變數 `small_set_size`，代表測試中的小型數據集大小，預設 `small_set_size = 128` （上圖），接著我們更改數據集大小觀察圖表。
當`small_set_size = 256` 時得到下圖
當`small_set_size = 512` 時得到下圖
### 分析不同紅黑樹實作手法的差異
在 SmallSetLinear 情況下，發現 FreeBSD 的效能最好
:::warning
應予以解讀並說明應用場景。
:notes: jserv
:::
<!-- > **TODO**
> 思考：linux 核心的 RB tree 會有更好的 cache locality 嗎？
> 將 `RBnode` 嵌入到要使用的結構之中，用 `container_of` 存取資料，不是在 `RBnode` 宣告終端資料指標。
> 討論：每個節點佔用空間 -->
Sign in with Wallet
Connect another wallet