# Linux 核心專題: 紅黑樹實作研究及改進
> 執行人: Wufangni
> [專題解說影片](https://youtu.be/qI-6X9I6q0Q)
### Reviewed by `ChenFuhuangKye`
建議不要使用圖片說明，可以試著使用 graphviz 。
> 謝謝提醒，已更正。
### Reviewed by `SuNsHiNe-75`
提到 Augmented Red-Black Tree 會將樹的額外資訊「藏」在節點中，其具體手法為何？
這些資訊的保留是否會影響到此資料結構的空間複雜度？
>Augmented Red-Black Tree 可以對節點附加額外資訊，並採用各種維護操作去更新增強過後的節點內容，其原理為在原本定義節點的資料結構中新增要附加的額外內容，下面以子樹數目做為附加資訊的例子:
``` c
struct my_node {
int key;
struct rb_node rb;
int size; // subtree size
};
```
>且 Augmented Red-Black Tree 在空間複雜度造成的影響主要取決於要附加的內容，以上面例子來說若在每個節點都新增一個整數空間 `size`，則最後所增加的空間為 $O(n)$ ，雖然增加了附加資訊但整體的空間複雜度仍為 $O(n)$ 。
### Reviewed by `lintin528`
請問在 `最大節點數達到 1000 時，分別對插入搜尋刪除三種操作時長的紀錄` 中，在 `Node Count` 為 `150-250` 的範圍內時，為何會出現浮動，這是隨機事件還是在每次的統計中都會發生呢？
>產生浮動的原因可能在於每次操作的細微差異造成不穩定的曲線狀態，可從不同迭代次數的實驗中(在 TODO: 設計實驗 中提及)看出，若增加每次紀錄的操作次數再取平均可得到較為平穩的分佈曲線。
### Reviewed by `fennecJ`
針對 linux kernel 中紅黑樹的相關函式 API 進行廣泛的探討，閱讀文章過程中我學到了許多，也複習了不熟悉的紅黑樹操作流程。
#### 問題
* 問題一
「紅黑樹在重新平衡的標準下容忍度相較高，減少需重新平衡的時間成本。」可否進一步說明，或透過分析其演算法呈現為何其容忍度較高。
>紅黑樹遵守五大原則(在 TODO: 研究 Linux 核心的紅黑樹 中提及)，因此做插入或刪除操作時只會因為黑色節點數量不一致或顏色規則而需重新平衡，而 AVL Tree 在平衡結構方面規劃的較為嚴謹，若左右子樹差超過 1 時就須重新平衡，因此整體所需的重平衡成本相較高於紅黑樹。
* 問題二
針對運用場景的歸納，為何 AVL tree 相較 rb tree 更適合用於搜尋較多的場合
>因上述回答說明，AVL Tree 在平衡方面有較嚴謹的規範，因此整體平衡性會高於紅黑樹，因此在搜尋操作下相較於紅黑樹能更有效率的找出目標節點。
* 問題三
rb_augmented_tree 中使用了 propagate function 進行資料的維護，該 function 的時間複雜度為何？是否會影響到原本 insert/del 的時間複雜度。
>根據紅黑樹性質其樹高最多被限制在 $O(\log{n})$，而 `propagate` 用於向上更新節點附加資訊(從更新節點位置到至多根節點位置)，因此時間複雜度為 $O(\log{n})$，且由於額外維護操作與樹高成正比，因此在插入及刪除操作下時間複雜度仍為 $O(\log{n})$。
## 任務簡介
研究 Linux 核心紅黑樹的實作手法，並予以量化分析。
## TODO: 研究 Linux 核心的紅黑樹
> 將 rbtree 自 Linux 核心原始程式碼搬到使用者空間，並與第四周測驗 `3` 提到的 XTree (注意: 這名稱沒有特別意義，更沒有論文發表，純粹是給學員練習改寫的程式碼) 比較，探討其設計考量。
> 可對照 [Linux 核心專題: 紅黑樹實作](https://hackmd.io/@sysprog/HkZcqus8R)的成果，善用 rb-bench 程式來量化程式表現。
> :warning: 圖例應以 Graphviz 或其他向量繪圖描述語言來處理
### 閱讀課程教材 [Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree) 了解紅黑樹的基本定義及優勢
紅黑樹 (red-black tree，在 Linux 核心簡稱 rbtree) 做為一種自我平衡樹在新增、刪除或搜尋等操作下時間複雜度均為 $O(\log{n})$，特別的地方在於樹高採用 black height (不含自身節點到樹葉節點的總黑色節點數量)，相較於 AVL Tree 嚴格要求每個節點左右子樹高度差不超過 1，紅黑樹在重新平衡的標準下容忍度相較高，減少需重新平衡的時間成本。
因此以不同角度對 AVL Tree 與紅黑樹做觀察和比較，前者雖然整體結構較平衡，但需要比多的平衡時間，而在搜尋資料方面 AVL Tree 因較好的平衡規範表現優於紅黑樹，所需空間方面紅黑樹只需 1 個位元的變數來區分紅色或黑色資訊，因此可將兩種資料結構的運用場景歸納如下:
- 插入或移除較多的情況: 使用紅黑樹結構
- 以搜尋為主的場景: 使用 AVL Tree 結構
:::danger
列出各式的屬性，特別是數學證明
:::
**紅黑樹樹高證明**
假設 rbtree 有 $n$ 個節點，且樹高用 $h$、每一條路徑(從根結點至樹葉節點)的黑色節點數量用 $bh$ 表示:
根據紅黑樹原則之一「不能出現連續紅色節點」，因此每一條路徑(從根結點至樹葉節點)的紅色節點必不會多於黑色節點，紅黑樹高度 $h$ 至少有一半以上為黑色節點，可推論出: $h \le 2bh$ 。
且 $bh$ 必小於或等於 $h$ 數目，因此可合併成: $bh \le h \le 2bh$ 。
根據完整二元樹公式若樹高為 $h$ 則節點數為 $2^h-1$ ，因此最小黑節點樹高為 $bh \le log_2(n+1)$ 。
由於 $h \le 2bh$ ，因此將上述式子整理成: $h \le 2log_2(n+1)$ 。
可推論出紅黑樹樹高 $h$ 為: $O(\log{n})$ 。
### 從 Linux 核心提供的紅黑樹相關程式碼逐一理解紅黑樹基本操作
原始程式碼：
* [include/linux/rbtree.h](https://elixir.bootlin.com/linux/v5.10/source/include/linux/rbtree.h)
* [include/linux/rbtree_augmented.h](https://elixir.bootlin.com/linux/v5.10/source/include/linux/rbtree_augmented.h)
* [include/lib/rbtree.c](https://elixir.bootlin.com/linux/v5.10/source/lib/rbtree.c)
:::danger
專題要求學員要在 Linux v6.8+ 的環境驗證，因此探討的原始程式碼也該升級到 Linux v6.8
:::
紅黑樹從 2-3-4 樹變化而來，因此可以自由地在兩結構之間做變換，主要遵守五大原則:
1. 紅黑樹內所有節點不是紅色就是黑色
2. 樹根 (root) 必為黑色節點
3. 紅色節點的子節點皆為黑色節點
4. 所有樹葉節點 (null) 皆為黑色
5. 從根節點到每個樹葉節點的路徑內黑色節點數量必一致
#### 節點定義
:::danger
免父權主義的遺毒，本文將 parent node 翻譯為「親代節點」，而非「父節點」或「母節點」，不僅更中性，也符合英文原意。若寫作「父」，則隱含「母」的存在，但以二元樹來說，沒有這樣成對關連性。若用「上代」會造成更多的混淆，在漢語中，「上一代」沒有明確的血緣關係 (例如「[炎黃子孫](https://dict.revised.moe.edu.tw/dictView.jsp?ID=155219)」與其說是血緣關係，不如說是傾向文化認同)，但「[親](https://dict.concised.moe.edu.tw/dictView.jsp?ID=25345)」的本意就是指名血緣和姻親關係。
延伸閱讀: [「新中國」和「中華民族」—— 梁啟超悔之莫及的發明](https://www.thenewslens.com/article/122516)
:::
`rb_node` 結構體存放三種資訊，`*rb_left`, `*rb_right` 分別指向左右子節點位址，`__rb_parent_color` 存放了親代節點位址，且由於 `__attribute__((aligned(sizeof(long)))` 會讓編譯器對 `sizeof(long)` 做對齊，因此最低兩位元不會被使用到 (永遠都是零)，可用來儲存該節點顏色資訊，而 `rb_root` 用來儲存根節點的位址資訊。
:::danger
注意書寫規範：
* 程式碼註解不該出現中文，總是用美式英語書寫
> 好的，已更正
> 不要急著回應，後面還有一堆要改。
> :warning: 依據 lab0 規範的程式碼風格，縮排是 4 個空白字元，本處列出的程式碼也該跟著變更。
> 注意細節！
:::
``` c
struct rb_node {
unsigned long __rb_parent_color; #Including the address of the parent node and color, with the color stored in the last two bits
struct rb_node *rb_right;
struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
struct rb_root {
struct rb_node *rb_node;
};
```
:::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
:::
較常使用的 `rb_parent` 過濾掉 `__rb_parent_color` 最低兩位元資訊，用於獲取親代節點的位址。
``` c
#define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
```
`rb_link_node` 透過指定 `__rb_parent_color` 到 `*parent` 的方式將 `*node` 的親代節點位址指定到 `*parent`。
``` c
static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
struct rb_node **rb_link)
{
node->__rb_parent_color = (unsigned long)parent;
node->rb_left = node->rb_right = NULL;
*rb_link = node;
}
```
:::danger
探討以下 cache 生效和更新的條件。
:::
`rb_root_cached` 除了儲存根節點位址外也存了最左節點(樹的最小節點)資訊，因此使用 `#define rb_first_cached(root) (root)->rb_leftmost` 可直接存取cache儲存的最左節點，搜尋結果的時間複雜度只需 $O(1)$。
:::danger
注意書寫規範：
* 無論標題和內文中，漢字和英語字元之間要有空白字元 (對排版和文字搜尋有利)
* 程式碼註解不該出現中文，總是用美式英語書寫
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
:::
``` c
struct rb_root_cached {
struct rb_root rb_root; //The root node of the red-black tree
struct rb_node *rb_leftmost; //The leftmost node of the red-black tree
};
```
對 `rb_root_cached` 做插入、刪除、替換節點的操作時需要一同更新 cache 內最左節點的資訊。
``` c
static inline void rb_insert_color_cached(struct rb_node *node,
struct rb_root_cached *root,
bool leftmost){
if (leftmost)
root->rb_leftmost = node; //If the inserted node is the leftmost node, then update the cache.
rb_insert_color(node, &root->rb_root);
}
static inline void rb_erase_cached(struct rb_node *node,
struct rb_root_cached *root){
if (root->rb_leftmost == node)
root->rb_leftmost = rb_next(node); //If the inserted node is the rightmost node, then update the cache.cache
rb_erase(node, &root->rb_root);
}
static inline void rb_replace_node_cached(struct rb_node *victim,
struct rb_node *new,
struct rb_root_cached *root){
if (root->rb_leftmost == victim) //If the replaced node is the leftmost node.
root->rb_leftmost = new; //Update the cache to the new node.
rb_replace_node(victim, new, &root->rb_root);
}
```
:::danger
區分「函數」和「函式」，務必詳閱 https://hackmd.io/@sysprog/it-vocabulary
:::
#### Augmented Red-Black Tree
Augmented Red-Black Tree 可在一般傳統紅黑樹上附加額外的資訊及維護功能，將額外資訊藏在節點中 (比如子樹的最大值、最小值...等)，且由於它帶有除了節點自身的額外附加資訊，因此應用在很多重要的場合當中，以下是對它應用場景的舉例:
:::danger
注意用語：
* file 是「檔案」，而非「文件」
下方的案例，你真的閱讀相關的原始程式碼並進行判斷嗎？抑或，仍停留在人云亦云的階段？
務必使用本課程教材規範的用語。
$\to$ [Linux 核心設計: 檔案系統概念及實作手法](https://hackmd.io/@sysprog/linux-file-system)
:::
- <s>文件系統</s>
需要快速搜尋、插入或刪除資料的一種資料系統，Augmented Red-Black Tree 結構可利用節點儲存目錄的<s>文件</s> 數量(子節點總數)、文件大小(節點的 size )等相關附加資訊。
- 記憶體管理
利用 Augmented Red-Black Tree 結構儲存記憶體區間大小、使用情況等資訊，加速記憶體存取效能。
- 資料庫索引
索引結構需要高效率的搜尋和修改(插入、刪除)等操作，利用 Augmented Red-Black Tree 特性可在節點中額外儲存最大值、最小值...等附加資訊，大程度提升範圍搜尋的效率。
:::danger
用對應的原始程式碼來說明 augmented red-black tree 的應用場景。
:::
Linux 核心開發者提出此機制的原因在於 Augmented Red-Black Tree 可添加多樣的額外訊息在節點當中，且具有靈活的回調機制使用者可根據自身要求去對附加資訊定義和修改，在不顯著影響時間複雜度的情況下利用少量操作去維護輔助資訊，使其操作可保持在紅黑樹基本操作下的時間成本 $O(\log{n})$ ，同時可有效提升上述提及的不同場合下的使用效能。
:::danger
探討 Augmented Red-Black Tree 的使用場合。
為何 Linux 核心開發者提出此機制？
:::
從 `rbtree_augmented.h` 可看到對於 Augmented Red-Black Tree 的相關定義與實作方式，使用 `rb_augment_callbacks` 做各種維護操作，主要結構如下:
``` c
struct rb_augment_callbacks {
void (*propagate)(struct rb_node *node, struct rb_node *stop);
void (*copy)(struct rb_node *old, struct rb_node *new);
void (*rotate)(struct rb_node *old, struct rb_node *new);
};
```
- `*propagate` 代表在插入、刪除節點和調整顏色時用來向上更新子樹的附加資訊
- `*copy` 代表節點被替換時複製附加資訊
- `*rotate` 代表在旋轉時更新附加資訊
`rbtree_augmented.h` 內的常用定義:
``` c
#define RB_RED 0 //Red node is represented by the value 0.
#define RB_BLACK 1 //Black node is represented by the value 1.
#define __rb_parent(pc) ((struct rb_node *)(pc & ~3)) //To obtain the address of the parent node.
#define __rb_color(pc) ((pc) & 1)
#define __rb_is_black(pc) __rb_color(pc)
#define __rb_is_red(pc) (!__rb_color(pc))
#define rb_color(rb) __rb_color((rb)->__rb_parent_color) //To obtain the color of the node.
#define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color) //To determine if it is red.
#define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color) //To determine if it is black.
```
`rb_set_parent` 將 `*rb` 節點的顏色與 `*p` 的位址合起來指定給 `rb->__rb_parent_color`，等同於設定 `*p` 作為 `*rb` 的親代節點。
``` c
static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p){
rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
}
```
`__rb_change_child` 為替換節點操作，如果親代節點存在則判斷要被替換的節點是否為左子節點，一致就將左子節點位址指定到新節點，否則指定右子節點位址到新節點，若親代節點不存在代表此被替代節點為根節點，則指定根節點為址到新節點。
``` c
static inline void
__rb_change_child(struct rb_node *old, struct rb_node *new,
struct rb_node *parent, struct rb_root *root){
if (parent) {
if (parent->rb_left == old)
WRITE_ONCE(parent->rb_left, new);
else
WRITE_ONCE(parent->rb_right, new);
} else
WRITE_ONCE(root->rb_node, new);
}
```
`__rb_erase_augmented` 刪除節點情況:
1. **Case1 如果刪除節點沒有子節點或只有一個子節點:**
- 將刪除節點以子節點作替代
- 若只有右(左)子節點則將pc(刪除節點的親代節點位址及刪除節點的顏色)給替代的節點
- 若皆無子節點則判斷刪除節點是否為黑色，若刪除黑色節點則需重新平衡紅黑樹(保持第五點原則)
:::danger
以 Graphviz 或其他向量繪圖描述方式重新製圖。
注意用語！
:::
2. **Case2 如果刪除節點有兩個子節點，且刪除節點的右子節點就是後繼節點:**
``` c
if (child2) {
rb_set_parent_color(child2, parent, RB_BLACK);
rebalance = NULL;
}
```
若 child2 為紅色，後繼節點必為黑色，則刪除節點有兩種情況(圖中白色節點代表可為黑也可為紅):
- 刪除節點為黑色時，因紅黑樹原則第五點每條路徑黑色節點數必須一致，child2 必須轉為黑色節點確保數量正確。
```graphviz
digraph rbTree {
label="刪除 node 節點前的紅黑樹";
labelloc="t";
fontsize=15;
node [shape=circle, style=filled, fontcolor=white];
A [label="", fillcolor=white, fontcolor=black];
B [label="", fillcolor=black];
D [label="", fillcolor=white];
E [label="", fillcolor=black];
G [label="", fillcolor=red, style=dashed];
F [label="", fillcolor=red];
C [label="", fillcolor=black, style=dashed];
A -> C;
A -> B;
B -> D;
B -> E;
E -> F;
E -> G;
{
rank="same";
tmp[label="tmp", shape=plaintext, fontcolor=black, fillcolor=white]
tmp -> A[color=red]
}
{
rank="same";
war[label="黑色節點數減一", shape=plaintext, fontcolor=black, fillcolor=white]
war -> B[color=red, style=dashed]
}
{
rank="same";
nod[label="node", shape=plaintext, fontcolor=black, fillcolor=white]
nod -> B[color=red]
}
{
rank="same";
succesor[label="succesor", shape=plaintext, fontcolor=black, fillcolor=white]
succesor -> E[color=red]
}
}
```
```graphviz
digraph rbTree {
label="刪除 node 節點後的紅黑樹";
labelloc="t";
fontsize=15;
node [shape=circle, style=filled, fontcolor=white];
A [label="", fillcolor=white, fontcolor=black];
B [label="", fillcolor=black];
D [label="", fillcolor=white];
E [label="", fillcolor=black];
C [label="", fillcolor=black, style=dashed];
A -> C;
A -> B;
B -> D;
B -> E;
{
rank="same";
tmp[label="tmp", shape=plaintext, fontcolor=black, fillcolor=white]
tmp -> A[color=red]
}
{
rank="same";
succesor[label="succesor", shape=plaintext, fontcolor=black, fillcolor=white]
succesor -> B[color=red]
}
{
rank="same";
war[label="轉為黑節點", shape=plaintext, fontcolor=black, fillcolor=white]
war -> E[color=red, style=dashed]
}
{
rank="same";
child2[label="child2", shape=plaintext, fontcolor=black, fillcolor=white]
child2 -> E[color=red]
}
}
```
- 刪除節點為紅色時，原在刪除節點的左子節點必為黑色，跑到後繼節點下則黑色節點數目需加一，child2 需轉為黑色確保後面的路徑黑色節點數一致。
```graphviz
digraph rbTree {
label="刪除 node 節點前的紅黑樹";
labelloc="t";
fontsize=15;
node [shape=circle, style=filled, fontcolor=white];
A [label="", fillcolor=white, fontcolor=black];
B [label="", fillcolor=red];
D [label="", fillcolor=black];
E [label="", fillcolor=black];
G [label="", fillcolor=red, style=dashed];
F [label="", fillcolor=red];
C [label="", fillcolor=black, style=dashed];
A -> C;
A -> B;
B -> D;
B -> E;
E -> F;
E -> G;
{
rank="same";
tmp[label="tmp", shape=plaintext, fontcolor=black, fillcolor=white]
tmp -> A[color=red]
}
{
rank="same";
nod[label="node", shape=plaintext, fontcolor=black, fillcolor=white]
nod -> B[color=red]
}
{
rank="same";
succesor[label="succesor", shape=plaintext, fontcolor=black, fillcolor=white]
succesor -> E[color=red]
}
}
```
```graphviz
digraph rbTree {
label="刪除 node 節點後的紅黑樹(尚未平衡)";
labelloc="t";
fontsize=15;
node [shape=circle, style=filled, fontcolor=white];
A [label="", fillcolor=white, fontcolor=black];
B [label="", fillcolor=black];
D [label="", fillcolor=black];
E [label="", fillcolor=red];
C [label="", fillcolor=black, style=dashed];
A -> C;
A -> B;
B -> D;
B -> E;
{
rank="same";
war[label="右邊路徑黑節點數加一", shape=plaintext, fontcolor=black, fillcolor=white]
war -> A[color=red, style=dashed]
}
{
rank="same";
tmp[label="tmp", shape=plaintext, fontcolor=black, fillcolor=white]
tmp -> A[color=red]
}
{
rank="same";
succesor[label="succesor", shape=plaintext, fontcolor=black, fillcolor=white]
succesor -> B[color=red]
}
{
rank="same";
child2[label="child2", shape=plaintext, fontcolor=black, fillcolor=white]
child2 -> E[color=red]
}
}
```
```graphviz
digraph rbTree {
label="刪除 node 節點後的紅黑樹(重新平衡)";
labelloc="t";
fontsize=15;
node [shape=circle, style=filled, fontcolor=white];
A [label="", fillcolor=white, fontcolor=black];
B [label="", fillcolor=black];
D [label="", fillcolor=black];
E [label="", fillcolor=black];
C [label="", fillcolor=black, style=dashed];
A -> C;
A -> B;
B -> D;
B -> E;
{
rank="same";
war[label="轉為黑色節點", shape=plaintext, fontcolor=black, fillcolor=white]
war -> E[color=red, style=dashed]
}
{
rank="same";
tmp[label="tmp", shape=plaintext, fontcolor=black, fillcolor=white]
tmp -> A[color=red]
}
{
rank="same";
succesor[label="succesor", shape=plaintext, fontcolor=black, fillcolor=white]
succesor -> B[color=red]
}
{
rank="same";
child2[label="child2", shape=plaintext, fontcolor=black, fillcolor=white]
child2 -> E[color=red]
}
}
```
3. **Case3 如果刪除節點有兩個子節點，且刪除節點的右子節點不是後繼節點:**
持續直到找到後繼節點 (succesor) 為止:
``` c
do {
parent = successor;
successor = tmp;
tmp = tmp->rb_left;
} while (tmp);
```
將後繼節點往上拉到刪除節點的右子節點:
``` c
child2 = successor->rb_right;
WRITE_ONCE(parent->rb_left, child2);
WRITE_ONCE(successor->rb_right, child);
rb_set_parent(child, successor);
augment->copy(node, successor);
augment->propagate(parent, successor);
```
此時欲替代刪除節點的後繼節點已變成刪除節點的右子節點，與 Case2 情況相同，因此後續交換節點與平衡方式等同於 Case2 作法。
在 `lib/rbtree.c` 中的基本輔助函數 `rb_set_black` 與 `*rb_red_parent`，前者用於設置輸入節點的顏色為黑色，後者則是獲取紅色節點 `*red` 的親代節點。
``` c
static inline void rb_set_black(struct rb_node *rb)
{
rb->__rb_parent_color |= RB_BLACK;
}
static inline struct rb_node *rb_red_parent(struct rb_node *red)
{
return (struct rb_node *)red->__rb_parent_color;
}
```
`__rb_rotate_set_parents` 在旋轉操作中設置親代節點和顏色，old 節點被替換成 new 節點，且更新親代節點指針和顏色。
``` c
static inline void __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, struct rb_root *root, int color)
{
struct rb_node *parent = rb_parent(old);
new->__rb_parent_color = old->__rb_parent_color;
rb_set_parent_color(old, new, color); //Set new as the parent node of old, and set old to have the specified color.
__rb_change_child(old, new, parent, root); //Replace the position of the node old with the node new.
}
```
:::danger
注意看[第四週測驗題](https://hackmd.io/@sysprog/linux2024-quiz4)關於 XTree 的描述：
> 名稱沒特別意思，不用去Google搜尋
不要過度依賴 Google 和 ChatGPT，要能夠自行分辨！
:::
## TODO: 研究 AVL tree 和紅黑樹特性和實作手法
> 閱讀《Demystifying the Linux CPU Scheduler》第三章關於 AVL tree vs. rbtree 的討論，注意 CFS 總是存取具備最小 vruntime 的節點，因此 Linux 核心的紅黑樹特別處理 cache (不是 CPU cache，而是著重減少非必要的記憶體存取，當 CFS 總是要取得數值最小的節點時)。
:::danger
務必使用本課程教材規範的術語，process 譯作「行程」。
:::
在 linux 核心中紅黑樹資料結構應用在任務的排程器當中，系統將可執行的任務儲存在紅黑樹，再以執行時間的線性順序插入到行程中，且因紅黑樹的自平衡搜尋樹特性，樹高會與基本操作(插入、刪除和搜尋)的時間成本成正比，因此在平衡過程中會盡可能減低樹的高度以降低時間成本。
:::danger
提供關於樹高的數學證明。
:::
**紅黑樹三種操作的時間複雜度計算**
從前一個 TODO 的樹高證明 $h = O(\log{n})$ 來對紅黑樹三種操作的時間成本做推導:
1. 搜尋操作:
在最壞情況下從根結點遍歷到樹葉節點的時間複雜度為 $O(h)=O(\log{n})$
3. 插入操作:
使用二元搜尋樹的方法尋找欲插入位置插入新節點，所需的時間複雜度為 $O(\log{n})$，接著須對紅黑樹做重新平衡的操作保持紅黑樹規則(顏色改變或旋轉)，每次進行的時間複雜度為 $O(1)$，因此插入操作的總時間複雜度為:$O(\log{n})+O(1)=O(\log{n})$
3. 刪除操作:
同插入操作分為搜尋刪除節點的時間複雜度以及重新平衡的時間成本，總時間複雜度為: $O(\log{n})+O(1)=O(\log{n})$
CPU 排程器在選取下一個要執行的任務時會依據 vruntime 最小來做選擇，因此需找出紅黑樹最左邊節點，一般紅黑樹在 n 個節點下樹高 ≤ 2 log2(n + 1)，搜尋的時間複雜度為 $O(\log{n})$，然而在 [lib/rbtree.c](https://elixir.bootlin.com/linux/v5.10/source/lib/rbtree.c) 中可看到紅黑樹存在有快取和非快取兩種結構的版本，有快取版本中用來儲存根節點位址的結構體 `rb_root_cached` 會多儲存最左邊節點的資訊，且以多個更新操作去維護他，此時對最小節點的搜尋成本降為 $O(1)$，可顯著加速搜尋過程，CFS 中採用快取版本來維護最小執行時間的任務。
:::danger
提供對應的數學證明。
:::
**cache 結構下的操作時間複雜度計算**
- 插入操作:
插入新節點位置所需的搜尋時間成本為 $O(\log{n})$ ，此時須對 cache 內部存放的最左節點做更新，時間複雜度為 $O(1)$ ，再對整棵樹做重新平衡，因此總共的時間複雜度計算公式為: $O(\log{n})+O(1)+O(1)=O(\log{n})$
- 刪除操作:
如同插入操作，在刪除節點後也須對 cache 更新最左節點，且重新平衡紅黑樹，因此總共的時間複雜度計算公式為: $O(\log{n})+O(1)+O(1)=O(\log{n})$
- 搜尋操作:
在搜尋操作下找尋最左節點的位置一般使用二元樹搜尋法，時間成本為 $O(\log{n})$ ，但由於 cache 結構除了儲存根節點資訊以外也會存取整棵樹的最左節點位址，且透過維護操作更新資訊使得 cache 內部一直保有準確的最左節點資訊，因此只須對根節點進行存取就能直接找到目標節點，總共時間複雜度降為 $O(1)$ 。
若任務是被阻止的不會再次進入 runqueue，但若是遇到 timeslice 結束或是被其他任務搶先則會插入到更新執行時間後的紅黑樹中，且可能不會在原先的位置(經過 $（\log{n}）$ 時間的重新平衡)。
```graphviz
digraph rbTree {
node [shape=circle, style=filled, fontcolor=white];
A [label="", fillcolor=black, fontcolor=white];
B [label="", fillcolor=red];
D [label="", fillcolor=black];
E [label="", fillcolor=black];
C [label="", fillcolor=black];
G [label="", fillcolor=red, style=dashed];
F [label="", fillcolor=red];
A -> C;
A -> B;
B -> D;
B -> E;
E -> G;
E -> F;
{
rank="same";
root[label="root", shape=plaintext, fontcolor=black, fillcolor=white]
root -> A[color=red]
}
{
rank="same";
succesor[label="最淺樹葉節點", shape=plaintext, fontcolor=black, fillcolor=white]
succesor -> C[color=red]
}
{
rank="same";
child2[label="最深樹葉節點", shape=plaintext, fontcolor=black, fillcolor=white]
child2 -> F[color=red]
}
}
```
:::danger
以 Graphviz 或其他向量圖形描述方式重新製圖。
:::
以上圖範例來看，左邊以一個黑色子節點代表最淺的樹葉節點，右邊則利用紅黑穿插來增加樹高(不能有連續紅節點情況)，且要符合每條路徑內的黑節點數量一致，因此最深可達樹高 3 的樹葉節點，確保了最深樹葉節點的樹高不會超過最淺樹葉節點的兩倍。
:::danger
提供數學證明
:::
根據上述內容及前置作業對紅黑樹的基本認知，紅黑樹的優點可以分為下面兩點:
1. 插入和刪除操作的及時性:
在紅黑樹的插入和刪除操作中通常只需要最多兩次和三次旋轉，可使得樹迅速達到平衡保持及時性能，且這些操作的最壞情況皆有一個上限 $O(\log{n})$。
2. 搜尋時間雖相較於 AVL tree 略慢，但最糟情況下還是可達到 $O(\log{n})$
:::danger
注意用語：
* real-time 是「即時」，而非「實時」
提供關於最壞狀況的數學證明。
:::
將紅黑樹與常使用的 AVL tree 做比較，列出了兩結構在時間、空間及使用場景下的差異性，且由於 CFS 需要頻繁的插入和刪除，因此紅黑樹更適合 CFS。
| | rbtree | AVL tree |
| -------- | ------ | --------------------------------------------------- |
| 平衡性 | 較低，但相較於AVL tree 減少了每次操作需要重新平衡的次數 | 較高，AVL tree 有嚴格規定左右子樹之間的高度不能大於2 |
| 空間需求 | 較低，只需一位元儲存顏色資訊 | 較高，需要一整個整數變量來儲存平衡因子 |
| 搜尋效率 | 較低，平衡狀態不如 AVL tree，時間複雜度為 $𝑂(2×log(𝑛+1))$ | 較高，屬於高度平衡結構因此時間複雜度為 $𝑂(1.44×log(𝑛+2))$ |
| 應用場景 | 適用於頻繁添加/刪除節點的場景 | 適用在需密集查詢資料的場景 |
## TODO: 設計實驗
> 針對上述 rbtree, AVL tree, XTree 等平衡二元樹的使用場景，設計對應的實驗，應涵蓋多種資料分布，對應到真實世界的應用場景。
設計紅黑樹測試內容，引入 [rbtree.c](https://github.com/Wufangni/rbtree/blob/main/rbtree.c) 及 [rbtree.h](https://github.com/Wufangni/rbtree/blob/main/rbtree.h) 並撰寫測試檔 rbtree-tst.c，首先建立欲操作的紅黑樹節點結構 `my_node`，包含一個節點值 key 及紅黑樹存放指針結構 `rb_node` 。
``` c
struct my_node {
int key;
struct rb_node rb;
};
```
加入搜尋、插入 `my_insert` 、刪除等操作，且在插入及刪除節點時使用紅黑樹平衡函式 `rb_insert_color` 及 `rb_erase` ，避免紅黑樹規則被破壞。
新增紅黑樹根節點 `tree`，使用 `clock_t` 紀錄操作開始與結束的時間，且定義要紀錄的最大節點數 `max_node_count` 、每次操作的節點數量 `step_size` ，以及迭代次數 `iterations` ，實驗會以多次迭代的平均作為該次操作的計算結果。
- step_size : 須持續往上遞增直到達到最大節點數上限
- iterations : 設計迭代次數取 10 次操作結果的平均值
``` c
struct rb_root tree = RB_ROOT;
clock_t start, end;
int max_node_count = 250;
int step_size = 10;
int iterations = 10;
```
### 測試執行時間差異
:::danger
區分「函數」和「函式」，前者要符合數學的定義。
:::
新增用來計算操作時長的函式 `get_time_in_seconds`。
:::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
:::
``` c
double get_time_in_seconds(clock_t start, clock_t end) {
return (double)(end - start) / CLOCKS_PER_SEC;
}
```
n 等同於 `step_size`，每次操作會採用 `rand()` 對該次操作的全部節點指定隨機值。
``` c
int* keys = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
keys[i] = rand() % 1000000;
}
```
**計算插入節點操作**
:::danger
注意用語，參見本課程教材的書寫風格。
:::
建立新的插入節點 `*new_node` 並指定 key 值，`start = clock()` 和 `end = clock()` 分別紀錄操作開始與結束的時間，且使用 `get_time_in_seconds` 計算總操作時長。
``` c
for (int i = 0; i < n; i++) {
struct my_node *new_node = (struct my_node *)malloc(sizeof(struct my_node));
new_node->key = keys[i];
start = clock();
my_insert(&tree, new_node);
end = clock();
total_insert_time += get_time_in_seconds(start, end);
}
```
**計算搜尋節點操作**
與插入操作相同計算方式，分別紀錄開始與結束時間並使用 `get_time_in_seconds` 取得總操作時長。
``` c
for (int i = 0; i < n; i++) {
start = clock();
my_search(&tree, keys[i]);
end = clock();
total_search_time += get_time_in_seconds(start, end);
}
```
**計算刪除節點操作**
先利用 `my_search` 搜尋欲刪除的節點，後續計算方式與插入操作相同，分別紀錄開始與結束時間並使用 `get_time_in_seconds` 取得總操作時長。
``` c
for (int i = 0; i < n; i++) {
struct rb_node *node = my_search(&tree, keys[i]);
if (node) {
struct my_node *data = rb_entry(node, struct my_node, rb);
start = clock();
my_delete(&tree, data);
end = clock();
total_delete_time += get_time_in_seconds(start, end);
}
}
```
最後在每次操作結束後釋放儲存節點值的記憶體 `free(keys)` 。
>完整程式碼在 [Wufangni/rbtree](https://github.com/Wufangni/rbtree)
- 此為最大節點數達到 250 時，分別對插入搜尋刪除三種操作時長的紀錄
- 此為最大節點數達到 1000 時，分別對插入搜尋刪除三種操作時長的紀錄
最大節點數增加到1000時可明顯分別出三個操作下時間長度的差異，插入和刪除操作因多次重平衡（旋轉和上色）所需時間會高於搜尋操作。
:::info
圖表中最後呈現結果反而在刪除操作時效能會優於搜尋操作，但搜尋時不需要做重新平衡，理應低於刪除操作的執行時長，但只有在初期實驗（最大節點數 50 以內）有呈現這個趨勢，目前還沒找出能解釋的原因。
:::
此外也分別對不同迭代次數做實驗，以下皆為 `max_node_count = 250` 時不同 `iterations` 的實驗結果：
- `iterations = 1`
- `iterations = 5`
- `iterations = 10`
- `iterations = 50`
可看到若沒有設置迭代次數（`iterations = 1`）只單靠一次操作時長做紀錄，會因每次操作的細微差異造成不穩定的曲線狀態，在三種不同操作下的辨識程度會非常低，難以區分各操作的效能優劣，隨著迭代次數的增加取平均後可看到不同操作分佈逐漸分開，曲線也不會像單一次數那樣呈現震盪，若是迭代次數設置太大（`iterations = 50`）則容易造成分佈相似的操作更緊密，差異較大的分的更明顯的現象，對於原本比較接近的刪除和搜尋兩操作會更不易於分辨。
### 測試旋轉次數差異
在 `rbtree.h` 檔案中新增外部宣告 `rb_rotation_count`，用於紀錄旋轉次數。
``` c
extern unsigned long rb_rotation_count;
void reset_rb_rotation_count(void);
```
在 `rbtree.c` 中加入 `reset_rb_rotation_count` 函式
``` c
unsigned long rb_rotation_count = 0;
void reset_rb_rotation_count(void) {
rb_rotation_count = 0;
}
```
更改 `__rb_rotate_left` 和 `__rb_rotate_right`，增加 `rb_rotation_count++` 以計算每次左旋和右旋的次數。
``` c
static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) {
rb_rotation_count++; // Increment rotation count
struct rb_node *right = node->rb_right;
struct rb_node *parent = rb_parent(node);
if ((node->rb_right = right->rb_left))
rb_set_parent(right->rb_left, node);
right->rb_left = node;
rb_set_parent(right, parent);
if (parent) {
if (node == parent->rb_left)
parent->rb_left = right;
else
parent->rb_right = right;
} else
root->rb_node = right;
rb_set_parent(node, right);
}
```
修改 Makefile
``` c
CC = gcc
CFLAGS = -Wall -g
OBJ = rbtree.o rbtree-tst.o
all: rbtree-tst
rbtree-tst: $(OBJ)
$(CC) $(CFLAGS) -o $@ $^
rbtree.o: rbtree.c rbtree.h
$(CC) $(CFLAGS) -c rbtree.c
rbtree-tst.o: rbtree-tst.c rbtree.h
$(CC) $(CFLAGS) -c rbtree-tst.c
clean:
rm -f *.o rbtree-tst rbtree_performance_time.dat rbtree_performance_rotation.dat rbtree_performance_time.gnuplot rbtree_performance_rotation.gnuplot rbtree_performance_time.png rbtree_performance_rotation.png
```
- 測試在最大節點數為 250 時三個操作的旋轉次數
根據圖表呈現插入操作的旋轉次數使用最多，其次為刪除操作，驗證了兩操作在時間總長實驗下的差異性（插入所花時間明顯高於刪除），而搜尋操作因沒有直接對樹的本身結構做改變則不須重新平衡，故旋轉次數為零。
### 測試 cache 未命中次數
cache miss 作為一個新的判斷效能的依據，若在執行過程中產生 miss 則須從記憶體再做一次存取的操作，造成效能降低，因此使用 `perf` 來統計 Data Cache Misses 總次數，並對不同操作進行了分析及比較。
新增 `measure_cache_misses` 函數，建立一個 command 命令用來統計插入、刪除和搜尋操作的 cache 未命中次數。
``` c
char command[256];
sprintf(command, "perf stat -e cache-misses ./rbtree-tst-perf-helper %s %d 2>&1 | grep 'cache-misses' | awk '{print $1}'", operation, n);
```
打開進程來執行剛剛建立的 command，並連接到 perf_output
``` c
FILE* perf_output = popen(command, "r");
if (!perf_output) {
perror("Error running perf command");
exit(1);
}
```
建立一個儲存 cache 輸出結果的緩衝區，並從 perf_output 讀取一行輸出到 buffer，轉換型態存進 `*cache_misses` 中，最後關閉剛剛被打開的 perf_output。
``` c
char buffer[128];
if (fgets(buffer, sizeof(buffer), perf_output) != NULL) {
*cache_misses = atol(buffer);
} else {
*cache_misses = 0;
}
pclose(perf_output);
```
在插入刪除，及搜尋操作下呼叫 `measure_cache_misses` 函數並以不同變數累加該次的 cache miss，最後除以迭代次數取的平均值。
:::danger
注意書寫規範：
* 程式碼註解不該出現中文，總是用美式英語書寫
* 用流暢的漢語書寫
:::
``` c
//Insert Operation
long insert_cache_misses;
measure_cache_misses("insert", n, &insert_cache_misses);
total_insert_cache_misses += insert_cache_misses;
//Search Operation
long search_cache_misses;
measure_cache_misses("search", n, &search_cache_misses);
total_search_cache_misses += search_cache_misses;
//Delete Operation
long delete_cache_misses;
measure_cache_misses("delete", n, &delete_cache_misses);
total_delete_cache_misses += delete_cache_misses;
```
- 測試在最大節點數為 5000 時三個操作的 cache miss 次數
可看到在插入操作時的 miss 情況會比較多，與執行所花時長呈現正相關，表示插入操作執行過程中會比另兩個操作多花費了大量重新存取資料的時間。
### rbtree vs. AVL tree
實做 AVL tree 的兩個檔案 [avltree.c](https://github.com/Wufangni/rbtree/blob/main/avltree.c) 及 [avltree.h](https://github.com/Wufangni/rbtree/blob/main/avltree.h)，並新增 [avlVSrb-tst.c](https://github.com/Wufangni/rbtree/blob/main/avlVSrb-tst.c) 測試檔，引入兩種資料結構和分別紀錄在插入刪除和搜尋三個操作下的執行時間。
- 插入操作下的 rbtree vs AVL tree
- 刪除操作下的 rbtree vs AVL tree
- 搜尋操作下的 rbtree vs AVL tree
根據兩資料結構的性質，rbtree 較適合進行大量插入刪除的操作，而在實驗結果中可看到在插入操作過程中 rbtree 的執行時間明顯低於 AVL tree，而在刪除與搜尋兩操作執行時間差異不大，較難對此做區分。
:::danger
你該改善測驗題裡頭的 XTree，而非現有論文的 XTree。
錯把馮京當馬涼
:::
Sign in with Wallet
Connect another wallet