# Linux 核心專題: 紅黑樹實作
> 執行人: marsh-fish
> [專題解說錄影](https://www.youtube.com/watch?v=bqqZxfqZa9U)
>
## 任務簡介
延伸 [2023 年專題](https://hackmd.io/@sysprog/rJbMiW3S3)，探究 Linux 核心的紅黑樹設計和實作。可重用原本的素材，但要重現所有實驗並改進程式碼。
### Reviewed by `ChenFuhuangKye `
[commit 3498397](https://github.com/marsh-fish/lab0-c/commit/3498397c3ab1a33ae9633ac6989b1343f7754e63) 增進英文表達，程式原本的出錯問題是?
> 這個 commit 是我拿來測試用的，請無視 commit 內容
### 介紹紅黑樹
#### 簡述紅黑樹
紅黑樹是 2-3-4 樹的變形，1978 年 Leonidas J. Guibas 和 Robert Sedgewick 發明最初的紅黑樹。2008 年 Sedgewick 做了改進，並將此命名為 LLRBT (Left-leaning red–black tree，即 左傾紅黑樹)，後者相比 1978 年的紅黑樹要簡單，程式碼量更精簡，可參見 [Left-leaning Red-Black Trees](https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf)。
底下為一個符合規則的紅黑樹
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
2,19,34,49,98[fillcolor=red]
A,B,C,D,E,F,G,H,I,J,K[label="null",fontsize=15,color=transparent]
27 -> {19 34}
19 -> {7 25}
7 -> {2 A}
25 -> {B C}
2 -> {D E}
34 -> {31 65}
31 -> {F G}
65 -> {49 98}
49 -> {H I}
98 -> {J K}
}
```
在研究 [rbtree.c](https://elixir.bootlin.com/linux/v6.9.6/source/lib/rbtree.c) 的程式碼時，發現了例子錯誤，下圖中的 Sr 應為小寫 S 加上小寫 r，組成 sr，但如果 N 節點與 sl 節點都有子節點的話，此紅黑樹也會成立，所以也可能是作者省略，不過我認為例子應該保持其簡單易懂，更改成 sr 會好一點。
[Fix the example typo patch](https://lore.kernel.org/all/20240628142229.69419-1-zxcvb600870024@gmail.com/T/#u)
```c
/*
* Case 3 - right rotate at sibling
* (p could be either color here)
*
* (p) (p)
* / \ / \
* N S --> N sl
* / \ \
* sl Sr S
* \
* Sr
...
```
:::danger
文字訊息「不要」用圖片展現！
:::
## TODO: 重做紅黑樹相關測驗題
> 均有設計和實作考量、完整的效能分析
### TODO: 對第 3 週測驗 [treesort.c](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401) 程式碼的理解
> 將 [treesort.c](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401) 整合到 lab0-c ，探討 tree sort 的效率
[commit 8fccccf](https://github.com/marsh-fish/lab0-c/commit/8fccccfe4f03ac1bff81cc0d4b7d94ec424510c5)
#### header
參考 [LiChiiiii](https://github.com/LiChiiiii/lab0-c) 的定義及程式
將`list_head`套用至 treesort.c 的結構裡並將 `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 ;
```
同時 `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;
}
```
`cmap_internal` 改成與結構相符
```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 *);
};
```
將上述定義結構與宣告函式之程式寫入 `treesort.h`
#### treesort.c
建立 `treesort.c` 以使用 `treesort.h` 定義的函式，這部份的僅列出想探討的部份
#### list_make_node
為了符合定義的結構將 `list_make_node` 的參數改寫成使用 `list_head` 類別，並用 `cmap_create_node` 來初始化 `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;
}
node_t *cmap_create_node(node_t *node)
{
/* Setup the pointers */
node->RBnode.left = node->RBnode.right = NULL;
rb_set_parent(&(node->RBnode), NULL);
/* Set the color to black by default */
rb_set_red(&(node->RBnode));
return node;
}
```
#### tree_free
功能相當於原本的 `list_free` 目的為釋放使用到的空間，以 DFS (Depth-First-Search) 的方式走訪每個節點
```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));
}
```
其餘的修改主要是將 `node_t` 的結構體改成 `treesort.h` 定義的 `rb_node` 結構體
#### qtest.c
新增 `treesort` 命令以方便使用 treesot, `do_treesort` 程式碼取至 `do_sort` 但不使用 `set_noallocate_mode` 因為在建立紅黑樹的時候會使用到 `malloc`
```c
bool do_treesort(int argc, char *argv[])
{
...
if (current && exception_setup(true))
tree_sort(current->q);
exception_cancel();
...
}
```
```c
ADD_COMMAND(treesort,
"Sort queue in ascending/descening order with tree sort", "");
```
執行看看
數字排序
```shell
cmd> show
Current queue ID: 0
l = [9 8 2 6 5 1]
cmd> treesort
l = [1 2 5 6 8 9]
```
字母排序
```shell
cmd> it RAND 5
l = [bkyeaezwp bcfykyts bgtjza juxuhi yiqyjg]
cmd> treesort
l = [bcfykyts bgtjza bkyeaezwp juxuhi yiqyjg]
```
可以成功進行排序，但在釋放記憶體的時候會出現錯誤訊息
```shell
cmd> free
l = NULL
ERROR: There is no queue, but 3 blocks are still allocated
```
:::danger
注意用語：
* allocate 是「配置」，而非「分配」，避免無法與 dispatch 區隔
:::
這是因為 `it_end`, `it_most`, `it_least` 有配置記憶體給他們，但配置給他們的空間並沒有被釋放，檢查程式碼發現，這三個變數並沒有被使用到，因此將 `cmap_calibrate` 註解，在 `cmap_new` 的宣告刪除
[commit 5eef13f](https://github.com/marsh-fish/lab0-c/commit/5eef13f5cbe1ab08d9a127eb7e48ba5282d485e2)
:::danger
改進你的漢語表達。
:::
能夠成功釋放記憶體且不會有錯誤訊息
```shell
cmd> free
l = NULL
cmd>
Freeing queue
```
```shell
cmd> it RAND 10000
l = [kjtpn jqlxp bcncdx ynssgd uyrsotju sshlouzmp dcuvaz galom srixx hpcahtfx hyforrqm lyzljfqfr qvjqoywf yldjn zxulxcuq wvfjxc ehbqhuij nahsaohsu pwvfnejob nggduem edylzuv ronfoidm lwugslt ombuq rrhunjmpf geclgcyu froeu yelpid kbiqqow onuhluaec ... ]
cmd> time treesort
l = [aabvut aacfzseue aacoyzxgd aadvsk aafwpycv aahhvdk aapnvp aarlnjcrp aawfoah aaxarpvjq aaxpitqo aazernv aazqzm abarifdmu abbdkfow abcvxl abeit abgvyo abjcb abjwafsad abroltd abveev abvhbfybp abvkcwnrh abvqrovzg abyhpgj acbhxmk acbxd accjnadap acdpvqe ... ]
Delta time = 0.125
```
`treesort` 平均五次下來為 `0.126.2` s
> 參考 [LiChiiiii](https://hackmd.io/ga0IoIC0ReCjpozPjtwY-Q?view#%E5%AF%A6%E9%9A%9B%E5%9F%B7%E8%A1%8C%E6%B8%AC%E8%A9%A6) 的作法
### TODO: 對第 4 週測驗 [LLRBT](https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf) 程式碼的理解
在 [2023 年第 4 週測驗一](https://hackmd.io/@sysprog/linux2023-quiz4#%E6%B8%AC%E9%A9%97-1)提供的程式碼中定義
```c
#define rb_node(x_type)
struct{
x_type *left, *right_red;
}
```
:::danger
使用精準的描述。
:::
可以看出與紅黑樹不同，不需要 parent 的指標，因此在程式碼的實作上也會有許多不同之處，下面是 [LLRBT](https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf) 中的旋轉和顏色翻轉，可以看出即使沒有親代節點的指標也能夠達成，不過需要提前知道下一步動作，因此在實作上才會透過 search path 來紀錄路線
:::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
:::
```c
Node rotateLeft(Node h)
{
x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;
h.color = RED;
return x;
}
Node rotateRight(Node h)
{
x = h.left;
h.left= x.right;
x.right= h;
x.color = h.color;
h.color = RED;
return x;
}
void flipColors(Node h)
{
h.color = !h.color;
h.left.color = !h.left.color;
h.right.color = !h.right.color;
}
```
而與一般紅黑樹的操作中，最大的差異是若出現下圖左邊的情況，需執行左旋以符合左傾條件
```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]
}
```
### 兩種紅黑樹實作方式比較
| 特徵 | Tree Sort | LLRBT |
| -------------- | -------------------------------------------------- | -------------------------------------------------- |
| 節點結構 | 包含==左子節點、右子節點和親代節點==的指標 | 包含==左子節點和右子節==點的指標，無親代節點直接紀錄 |
| 節點操作方式 | 通過節點的親代指標==直接獲取和操作==親代節點 | 使用==額外的路徑陣列==追蹤操作路徑並對紅黑樹進行平衡 |
| 空間佔用 | 需要額外的指標記錄親代節點，**佔用更多的內存空間** | 不需要額外的指標記錄親代節點，節省內存空間 |
| 平衡操作複雜度 | 平衡操作相對較簡單，直接==通過指標修改==節點的親代關係 | 平衡操作較複雜，需要使用==陣列記錄路徑==並進行調整 |
| 適用場景 |操作和追蹤節點的親代關係較為頻繁的場景 | 節點操作和平衡操作頻率較低的場景 |
## TODO: 紅黑樹實作的效能評比
利用 [rb-bench](https://github.com/jserv/rb-bench)，分析不同紅黑樹實作手法的差異，應當考慮更大的資料範圍
> 對照 [rbtree_bench](https://github.com/ypaskell/rbtree_bench)
### 執行 rb-bench
fork [rb-bench](https://github.com/jserv/rb-bench) 並執行以下命令
```shell
make all
./rb-bench > reports/test-linux-emag.xml
make images
```
:::danger
注意用語：
* command 是「命令」，而非「指令」(instruction)
:::
我有修改原本的 `make images` 命令使其相當於執行 `./plot.py reports/test-linux-emag.xml reports/test-linux-emag.png` 才能夠成功執行 python 並將圖片生成於 reports 目錄下，便可得到以下這張圖，其中
> Linear: 插入的節點為遞增的數值。
RandomOps: 若要插入的隨機數已在樹中就將其移除，反之進行插入。
下圖為`small_set_size = 128`時的結果
會發現再左側的 X 軸和底部的 Y 軸以及上方的標題都出現了重疊的數值，猜測是 python 語法因為版本不同而產生的錯誤顯示，仔細看可以看出上方重疊一個 X ，對照 python 檔便可得知 `plt.title('x')` 是產生此重疊的原因將該行刪除，再輸出一次
[commit 8fb9889](https://github.com/marsh-fish/rb-bench/commit/8fb988935916a4df24df5bb0adaa7978b6089da5)
Linear: Eternally Confuzzled > LLRB > bheap > jemalloc > Linux > FreeBSD
RandomOps: LLRB > Eternally Confuzzled > jemalloc > FreeBSD > Linux > bheap
下圖為`small_set_size = 256`時的結果
Linear: Eternally Confuzzled > LLRB > bheap > jemalloc > Linux > FreeBSD
RandomOps: LLRB > Eternally Confuzzled > jemalloc > FreeBSD > Linux > bheap
下圖為`small_set_size = 512`時的結果
Linear: Eternally Confuzzled > LLRB > bheap > jemalloc > Linux > FreeBSD
RandomOps: LLRB > Eternally Confuzzled > jemalloc > FreeBSD > Linux > bheap
下圖為`small_set_size = 1024`時的結果
Linear: LLRB > Eternally Confuzzled > bheap > jemalloc > Linux > FreeBSD
RandomOps: LLRB > Eternally Confuzzled > jemalloc > FreeBSD > Linux > bheap
當 `small_set_size` 大於 512 的時候，在 Linear 的部份 LLRB 的時間已經大於 Eternally Confuzzled 所需要的時間，猜測在 `small_set_size = 2048` 時其差距會更大
下圖為`small_set_size = 2048`時的結果
Linear: LLRB > Eternally Confuzzled > bheap > jemalloc > Linux > FreeBSD
RandomOps: LLRB > Eternally Confuzzled > jemalloc > FreeBSD > Linux > bheap
根據 `small_set_size = 2048` 的結果得知先前 LLRB > Eternally Confuzzled 的假設是正確的，其他線圖的斜率也沒發生重大的變化，若所有方法都是線性增長的，可以推知資料再增大也不會有變化
:::danger
思考現有的 rb-bench 是否足以代表真實世界的場景？
:::
## TODO: 分析不同紅黑樹實作手法的差異
> 應予以解讀並說明應用場景。
Linear 相當於僅有插入節點沒有刪除節點操作，而 RandomOps 若遇到以出現過的節點的情況會將已存在的節點刪除，所以 Linear 和 RandomOps 的差異可以想成是有刪除操作與否。所以在應用場景上，例如前面做的 `treesort.c` ，在 `treesort.c` 中，紅黑樹的操作只有使用到插入節點的功能，所以使用 FreeBSD 便會達到最好的效果，在會使用到刪除的場景上，如 timer ，則使用 bheap 會達到最好的效果。
:::danger
用 Linux 核心在內的開放原始碼專案，探討其紅黑樹設計的考量和效能表現。
jemalloc 使用特化的 LLRBT
:::
## TODO: 探討 Linux 核心 augmented rbtree 實作手法
> Linux 核心的 [augmented rbtree](https://www.kernel.org/doc/Documentation/rbtree.txt) 在設計上與經典的紅黑樹不同，探究其 [rbtree_augmented.h](https://github.com/torvalds/linux/blob/master/include/linux/rbtree_augmented.h) 的設計。
> 以下規則參照 [rbtree.c](https://elixir.bootlin.com/linux/v6.9.6/source/lib/rbtree.c) 的程式碼
#### 插入節點
當插入的節點之親代節點為紅色時會有三個不同的情況會需要判斷，以下是三種不同的操作
Case 1 - 親代的平輩節點為紅色 (祖代節點 (grandparent) 與其子節點顏色翻轉)：
#### 例子
插入 40，遇到 Case 1
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
2,19,34,40,49,98[fillcolor=red]
A,B,C,D,E,F,G,H,I,J,K,L[label="null",fontsize=15,color=transparent]
27 -> {19 34}
19 -> {7 25}
7 -> {2 A}
25 -> {B C}
2 -> {D E}
34 -> {31 65}
31 -> {F G}
65 -> {49 98}
49 -> {40 H}
98 -> {I J}
40 -> {K L}
}
```
65 節點與其子節點顏色翻轉並移到65
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
2,19,34,40,65[fillcolor=red]
A,B,C,D,E,F,G,H,I,J,K,L[label="null",fontsize=15,color=transparent]
27 -> {19 34}
19 -> {7 25}
7 -> {2 A}
25 -> {B C}
2 -> {D E}
34 -> {31}
34 -> {65}
31 -> {F G}
65 -> {49 98}
49 -> {40 H}
98 -> {I J}
40 -> {K L}
}
```
27 節點與其子節點顏色翻轉並移到27
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
2,27,40,65[fillcolor=red]
A,B,C,D,E,F,G,H,I,J,K,L[label="null",fontsize=15,color=transparent]
27 -> {19 34}
19 -> {7 25}
7 -> {2 A}
25 -> {B C}
2 -> {D E}
34 -> {31}
34 -> {65}
31 -> {F G}
65 -> {49 98}
49 -> {40 H}
98 -> {I J}
40 -> {K L}
}
```
27 顏色翻轉結束迴圈操作
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
2,40,65[fillcolor=red]
A,B,C,D,E,F,G,H,I,J,K,L[label="null",fontsize=15,color=transparent]
27 -> {19 34}
19 -> {7 25}
7 -> {2 A}
25 -> {B C}
2 -> {D E}
34 -> {31}
34 -> {65}
31 -> {F G}
65 -> {49 98}
49 -> {40 H}
98 -> {I J}
40 -> {K L}
}
```
這裡先示範插入節點的親代節點為黑色時會如何
插入 100，由於 100 的親代節點為黑色因此可以直接插入
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
2,40,65,100[fillcolor=red]
A,B,C,D,E,F,G,H,I,J,K,L,M[label="null",fontsize=15,color=transparent]
27 -> {19 34}
19 -> {7 25}
7 -> {2 A}
25 -> {B C}
2 -> {D E}
34 -> {31}
34 -> {65}
31 -> {F G}
65 -> {49 98}
49 -> {40 J}
98 -> {I}
98 -> {100}
40 -> {K L}
100 -> {H M}
}
```
Case 3 - 親代的平輩節點為黑色且為其親代節點的左(右)子點 (對其祖代節點做右(左)旋)：
#### 例子
插入 105，遇到 Case 3
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
2,40,65,100,105[fillcolor=red]
A,B,C,D,E,F,G,H,I,J,K,L,M,N[label="null",fontsize=15,color=transparent]
27 -> {19 34}
19 -> {7 25}
7 -> {2 A}
25 -> {B C}
2 -> {D E}
34 -> {31}
34 -> {65}
31 -> {F G}
65 -> {49 98}
49 -> {40 J}
98 -> {I}
98 -> {100}
40 -> {K L}
100 -> {H}
100 -> {105}
105 -> {N M}
}
```
對 98 做左旋
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
2,40,65,100,105[fillcolor=red]
A,B,C,D,E,F,G,H,I,J,K,L,M,N[label="null",fontsize=15,color=transparent]
27 -> {19 34}
19 -> {7 25}
7 -> {2 A}
25 -> {B C}
2 -> {D E}
34 -> {31}
34 -> {65}
31 -> {F G}
65 -> {49}
65 -> {100}
49 -> {40 J}
40 -> {K L}
100 -> {98}
100 -> {105}
98 -> {H I}
105 -> {N M}
}
```
98 100 顏色對調
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
2,40,65,98,105[fillcolor=red]
A,B,C,D,E,F,G,H,I,J,K,L,M,N[label="null",fontsize=15,color=transparent]
27 -> {19 34}
19 -> {7 25}
7 -> {2 A}
25 -> {B C}
2 -> {D E}
34 -> {31}
34 -> {65}
31 -> {F G}
65 -> {49}
65 -> {100}
49 -> {40 J}
40 -> {K L}
100 -> {98}
100 -> {105}
98 -> {H I}
105 -> {N M}
}
```
Case 2 - 親代的平輩節點為黑色且插入的節點為親代節點的右(左)子點 (對插入的節點之親代節點做左(右)旋)：
#### 例子
插入 46，遇到 Case 2
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
2,40,46,65,98,105[fillcolor=red]
A,B,C,D,E,F,G,H,I,J,K,L,M,N,O[label="null",fontsize=15,color=transparent]
27 -> {19 34}
19 -> {7 25}
7 -> {2 A}
25 -> {B C}
2 -> {D E}
34 -> {31}
34 -> {65}
31 -> {F G}
65 -> {49 100}
49 -> {40 J}
100 -> {98}
100 -> {105}
98 -> {H I}
105 -> {O M}
40 -> {K}
40 -> {46}
46 -> {N L}
}
```
對 40 做左旋
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
2,40,46,65,98,105[fillcolor=red]
A,B,C,D,E,F,G,H,I,J,K,L,M,N,O[label="null",fontsize=15,color=transparent]
27 -> {19 34}
19 -> {7 25}
7 -> {2 A}
25 -> {B C}
2 -> {D E}
34 -> {31}
34 -> {65}
31 -> {F G}
65 -> {49}
65 -> {100}
49 -> {46 J}
100 -> {98}
100 -> {105}
98 -> {H I}
105 -> {N M}
40 -> {K O}
46 -> {40 L}
}
```
在linux版本的紅黑數中，做完 Case 2 後會直接執行 Case 3 的操作，因此對 49 做右旋
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
2,40,46,65,98,105[fillcolor=red]
A,B,C,D,E,F,G,H,I,J,K,L,M,N,O[label="null",fontsize=15,color=transparent]
27 -> {19 34}
19 -> {7 25}
7 -> {2 A}
25 -> {B C}
2 -> {D E}
34 -> {31}
34 -> {65}
31 -> {F G}
65 -> {46}
65 -> {100}
49 -> {L J}
100 -> {98}
100 -> {105}
98 -> {H I}
105 -> {N M}
40 -> {K O}
46 -> {40 49}
}
```
46 49 顏色對調
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
2,40,49,65,98,105[fillcolor=red]
A,B,C,D,E,F,G,H,I,J,K,L,M,N,O[label="null",fontsize=15,color=transparent]
27 -> {19 34}
19 -> {7 25}
7 -> {2 A}
25 -> {B C}
2 -> {D E}
34 -> {31}
34 -> {65}
31 -> {F G}
65 -> {46}
65 -> {100}
49 -> {L J}
100 -> {98}
100 -> {105}
98 -> {H I}
105 -> {N M}
40 -> {K O}
46 -> {40 49}
}
```
#### 刪除節點
當我們刪除節點的時候會先判斷是否需要執行再平衡(rebalance)，因為當我們刪除節點後可能不會影響到樹的平衡，此時便無需再平衡。
根據以下幾種情況判斷是否需要執行再平衡
Case 1 - 當刪除的節點沒有超過 1 個子節點：
若刪除的節點沒有子節點且該節點為紅色，可以直接刪除不會影響平衡，例如底下圖式的 2, 40, 49, 98, 105；若刪除的節點只有一個子節點，根據紅黑樹的規則只會有一種情況，該節點為黑色，其子節點為紅色，如 7, 2 ，此時也可以直接刪除並將子節點補上並變色
#### 例子
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
2,40,49,65,98,105[fillcolor=red]
A,B,C,D,E,F,G,H,I,J,K,L,M,N,O[label="null",fontsize=15,color=transparent]
27 -> {19 34}
19 -> {7 25}
7 -> {2 A}
25 -> {B C}
2 -> {D E}
34 -> {31}
34 -> {65}
31 -> {F G}
65 -> {46}
65 -> {100}
49 -> {L J}
100 -> {98}
100 -> {105}
98 -> {H I}
105 -> {N M}
40 -> {K O}
46 -> {40 49}
}
```
刪除 7
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
40,49,65,98,105[fillcolor=red]
B,C,D,E,F,G,H,I,J,K,L,M,N,O[label="null",fontsize=15,color=transparent]
27 -> {19 34}
19 -> {2 25}
25 -> {B C}
2 -> {D E}
34 -> {31}
34 -> {65}
31 -> {F G}
65 -> {46}
65 -> {100}
49 -> {L J}
100 -> {98}
100 -> {105}
98 -> {H I}
105 -> {N M}
40 -> {K O}
46 -> {40 49}
}
```
也就是說若刪除的節點沒有子節點且該節點為黑色，就需要執行再平衡
例如現在這個圖的 2, 25, 31
Case 2 - 當刪除的節點的後繼節點(successor)是該節點右子節點：
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.7]
null[fontsize=0,color=transparent]
n -> {x s}
s -> null[color=transparent]
s -> c
}
```
刪除後變成
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.7]
s -> {x c}
}
```
以我們的例子來說的話， 19, 46, 100 節點便是 Case 2
其中，後繼節點的子節點不一定存在，若後繼節點的子節點存在則無須再平衡；若後繼節點的子節點不存在，根據後繼節點的顏色來決定是否再平衡。
Case 3 - 當刪除的節點的後繼節點 (successor) 是該節點右子節點的最左子節點：
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.7]
null, null1, null2[fontsize=0,color=transparent]
n -> {x y}
y -> p
y -> null[color=transparent]
p -> s
p -> null1[color=transparent]
s -> null2[color=transparent]
s -> c
}
```
刪除後變成
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.7]
null, null1[fontsize=0,color=transparent]
s -> {x y}
y -> p
y -> null[color=transparent]
p -> c
p -> null1[color=transparent]
}
```
以我們的例子來說的話， 27, 34, 65 節點便是 Case 3
Case 2, Case 3 是否需要再平衡的判斷是一樣的，主要的差異為程式的實作。
#### 再平衡
接著再做再平衡的時候也會有四種情況需要考慮，但此時四種情況是會依序判斷並執行
Case 1 - 刪除節點為親代節點的左(右)子節點，平輩節點為紅色，對親代節點左(右)旋，並保持與旋轉前相當的顏色
Case 2 - 刪除節點為親代節點的左(右)子節點，平輩節點的左(右)子節點為黑色，平輩節點顏色翻轉，若不是從 Case 1 進入到 Case 2 則遞迴向上
Case 3 - 刪除節點為親代節點的左(右)子節點，平輩節點的右(左)子節點為黑色，對平輩節點右(左)旋
Case 4 - 刪除節點為親代節點的左(右)子節點，對親代節點左(右)旋 + 顏色翻轉
其中 Case 4 的旋轉會依照以下規則進行：
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.7]
p,sl[fillcolor=white]
p -> {n s}
s -> {sl sr}
}
```
左旋後
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.7]
s,sl[fillcolor=white]
s -> {p sr}
p -> {n}
p -> {sl}
}
```
s 節點的顏色會等同旋轉前 p 節點的顏色
sl 節點的顏色則會保持不便
旋轉後的 p, sr 節點顏色會是黑色
#### 例子
刪除 31
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
40,49,65,98,105[fillcolor=red]
B,C,D,E,G,I,J,H,K,L,M,N,O[label="null",fontsize=15,color=transparent]
27 -> {19 34}
19 -> {2 25}
25 -> {B C}
2 -> {D E}
34 -> {G}
34 -> {65}
65 -> {46}
65 -> {100}
49 -> {L J}
100 -> {98}
100 -> {105}
98 -> {H I}
105 -> {N M}
40 -> {K O}
46 -> {40 49}
}
```
遇到 Case 1，對 34 左旋
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
40,49,65,98,105[fillcolor=red]
B,C,D,E,G,I,J,H,K,L,M,N,O[label="null",fontsize=15,color=transparent]
27 -> {19}
27 -> {65}
19 -> {2 25}
25 -> {B C}
2 -> {D E}
34 -> {G}
34 -> {46}
65 -> {34}
65 -> {100}
49 -> {L J}
100 -> {98}
100 -> {105}
98 -> {H I}
105 -> {N M}
40 -> {K O}
46 -> {40 49}
}
```
34 65 顏色對調
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
40,49,34,98,105[fillcolor=red]
B,C,D,E,G,I,J,H,K,L,M,N,O[label="null",fontsize=15,color=transparent]
27 -> {19}
27 -> {65}
19 -> {2 25}
25 -> {B C}
2 -> {D E}
34 -> {G}
34 -> {46}
65 -> {34}
65 -> {100}
49 -> {L J}
100 -> {98}
100 -> {105}
98 -> {H I}
105 -> {N M}
40 -> {K O}
46 -> {40 49}
}
```
遇到 Case 4，對 34 左旋
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
40,49,34,98,105[fillcolor=red]
B,C,D,E,G,I,J,H,K,L,M,N,O[label="null",fontsize=15,color=transparent]
27 -> {19}
27 -> {65}
19 -> {2 25}
25 -> {B C}
2 -> {D E}
34 -> {G}
34 -> {40}
65 -> {46}
65 -> {100}
49 -> {L J}
100 -> {98}
100 -> {105}
98 -> {H I}
105 -> {N M}
40 -> {K O}
46 -> {34}
46 -> {49}
}
```
顏色翻轉
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
40,46,98,105[fillcolor=red]
B,C,D,E,G,I,J,H,K,L,M,N,O[label="null",fontsize=15,color=transparent]
27 -> {19}
27 -> {65}
19 -> {2 25}
25 -> {B C}
2 -> {D E}
34 -> {G}
34 -> {40}
65 -> {46}
65 -> {100}
49 -> {L J}
100 -> {98}
100 -> {105}
98 -> {H I}
105 -> {N M}
40 -> {K O}
46 -> {34}
46 -> {49}
}
```
刪除 49
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
40,46,98,105[fillcolor=red]
B,C,D,E,G,I,J,H,K,M,N,O[label="null",fontsize=15,color=transparent]
27 -> {19}
27 -> {65}
19 -> {2 25}
25 -> {B C}
2 -> {D E}
34 -> {G}
34 -> {40}
65 -> {46}
65 -> {100}
100 -> {98}
100 -> {105}
98 -> {H I}
105 -> {N M}
40 -> {K O}
46 -> {34}
46 -> {J}
}
```
34 左子節點為黑色，Case 3，對 34 左旋
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
40,46,98,105[fillcolor=red]
B,C,D,E,G,I,J,H,K,M,N,O[label="null",fontsize=15,color=transparent]
27 -> {19}
27 -> {65}
19 -> {2 25}
25 -> {B C}
2 -> {D E}
34 -> {G K}
65 -> {46}
65 -> {100}
100 -> {98}
100 -> {105}
98 -> {H I}
105 -> {N M}
40 -> {34}
40 -> {O}
46 -> {40}
46 -> {J}
}
```
接續執行 Case 4，右旋
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
40,46,98,105[fillcolor=red]
B,C,D,E,G,I,J,H,K,M,N,O[label="null",fontsize=15,color=transparent]
27 -> {19}
27 -> {65}
19 -> {2 25}
25 -> {B C}
2 -> {D E}
34 -> {G K}
65 -> {40}
65 -> {100}
100 -> {98}
100 -> {105}
98 -> {H I}
105 -> {N M}
40 -> {34}
40 -> {46}
46 -> {J O}
}
```
顏色翻轉
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
40,98,105[fillcolor=red]
B,C,D,E,G,I,J,H,K,M,N,O[label="null",fontsize=15,color=transparent]
27 -> {19}
27 -> {65}
19 -> {2 25}
25 -> {B C}
2 -> {D E}
34 -> {G K}
65 -> {40}
65 -> {100}
100 -> {98}
100 -> {105}
98 -> {H I}
105 -> {N M}
40 -> {34}
40 -> {46}
46 -> {J O}
}
```
刪除 2
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
40,98,105[fillcolor=red]
A,B,C,D,E,F,G,H,I,J,K[label="null",fontsize=15,color=transparent]
27 -> {19}
27 -> {65}
19 -> {K 25}
25 -> {A B}
34 -> {C D}
65 -> {40}
65 -> {100}
100 -> {98}
100 -> {105}
98 -> {E F}
105 -> {G H}
40 -> {34}
40 -> {46}
46 -> {I J}
}
```
遇到 Case 2，將 25 顏色翻轉，並遞迴至 19 節點
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
25,40,98,105[fillcolor=red]
A,B,C,D,E,F,G,H,I,J,K[label="null",fontsize=15,color=transparent]
27 -> {19}
27 -> {65}
19 -> {K}
19 -> {25}
25 -> {A B}
34 -> {C D}
65 -> {40}
65 -> {100}
100 -> {98}
100 -> {105}
98 -> {E F}
105 -> {G H}
40 -> {34}
40 -> {46}
46 -> {I J}
}
```
遇到 Case 3，對 65 右旋
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
25,40,98,105[fillcolor=red]
A,B,C,D,E,F,G,H,I,J,K[label="null",fontsize=15,color=transparent]
27 -> {19}
27 -> {40}
19 -> {K}
19 -> {25}
25 -> {A B}
34 -> {C D}
65 -> {46}
65 -> {100}
100 -> {98}
100 -> {105}
98 -> {E F}
105 -> {G H}
40 -> {34}
40 -> {65}
46 -> {I J}
}
```
接續執行 Case 4，對 27 左旋
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
25,40,98,105[fillcolor=red]
A,B,C,D,E,F,G,H,I,J,K[label="null",fontsize=15,color=transparent]
40 -> {27 65}
27 -> {19 34}
19 -> {K}
19 -> {25}
25 -> {A B}
34 -> {C D}
65 -> {46}
65 -> {100}
100 -> {98}
100 -> {105}
98 -> {E F}
105 -> {G H}
46 -> {I J}
}
```
顏色翻轉
```graphviz
digraph BST {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
25,98,105[fillcolor=red]
A,B,C,D,E,F,G,H,I,J,K[label="null",fontsize=15,color=transparent]
40 -> {27 65}
27 -> {19 34}
19 -> {K}
19 -> {25}
25 -> {A B}
34 -> {C D}
65 -> {46}
65 -> {100}
100 -> {98}
100 -> {105}
98 -> {E F}
105 -> {G H}
46 -> {I J}
}
```
## 針對其他學員 (含授課教師和社會人士) 在開發紀錄頁面提出的問題或建議
[Linux 核心專題: 重作第 3, 4, 7 週測驗題](https://hackmd.io/bKJ36r1lSciU3YrBRUTWcQ#Reviewed-by-marsh-fish)
[Linux 核心專題: 紅黑樹實作改進](https://hackmd.io/8EXDGddgQ9SMTF1yjrQJ0w#Reviewed-by-marsh-fish)
[Linux 核心專題: 浮點數運算案例探討](https://hackmd.io/xTkhMdn1Sp-Mnvt5a7_-Ww#Reviewed-by-marsh-fish)
[Linux 核心專題: 高性能網頁伺服器](https://hackmd.io/mQptX1mMR6Gg--CGTdCssA#Reviewed-by-marsh-fish)
[Linux 核心專題: 虛擬無線網路裝置驅動程式](https://hackmd.io/@sysprog/rJ-LF4nNC#Reviewed-by-marsh-fish)
Sign in with Wallet
Connect another wallet