## 紅黑樹實作: 研究紅黑樹 https://hackmd.io/@sysprog/rJbMiW3S3 紀錄問題並重現實驗 + extra
>[講解影片](https://www.youtube.com/watch?v=bqqZxfqZa9U)
### 介紹紅黑樹
#### 簡述紅黑樹
紅黑樹是 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}
}
```
> 以下規則參照 [Linux rbtree](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}
}
```
:::danger
在研究 [linux rbtree](https://elixir.bootlin.com/linux/v6.9.6/source/lib/rbtree.c) 的程式碼時，發現了註解錯誤，下圖中的 Sr 應為小寫 S 加上小寫 r，組成 sr，但如果 N 節點與 sl 節點都有子節點的話，此紅黑樹也會成立，所以也可能是作者省略，不過我認為在註解上的例子應該保持其簡單易懂，更改成 sr 會好一點。
:::
## 將 [treesort.c](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401) 整合到 lab0-c
[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
```
這是因為 `it_end`, `it_most`, `it_least` 有分配記憶體給他們，但分配給他們的空間並沒有被釋放，檢查程式碼發現，這三個變數並沒有被使用到，因此將 `cmap_calibrate` 註解，在 `cmap_new` 的宣告刪除
[commit 5eef13f](https://github.com/marsh-fish/lab0-c/commit/5eef13f5cbe1ab08d9a127eb7e48ba5282d485e2)
能夠成功釋放記憶體且不會跳出錯誤
```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) 的作法
## 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]
}
```
### 兩種紅黑樹實作方式比較
| 特徵 | Tree Sort | LLRBT |
| -------------- | -------------------------------------------------- | -------------------------------------------------- |
| 節點結構 | 包含==左子節點、右子節點和親代節點==的指標 | 包含==左子節點和右子節==點的指標，無親代節點直接紀錄 |
| 節點操作方式 | 通過節點的親代指標==直接獲取和操作==親代節點 | 使用==額外的路徑陣列==追蹤操作路徑並對紅黑樹進行平衡 |
| 空間佔用 | 需要額外的指標記錄親代節點，**佔用更多的內存空間** | 不需要額外的指標記錄親代節點，節省內存空間 |
| 平衡操作複雜度 | 平衡操作相對較簡單，直接==通過指標修改==節點的親代關係 | 平衡操作較複雜，需要使用==陣列記錄路徑==並進行調整 |
| 適用場景 |操作和追蹤節點的親代關係較為頻繁的場景 | 節點操作和平衡操作頻率較低的場景 |
## 紅黑樹實作的效能評比
利用 [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
```
我有修改原本的 `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 的假設是正確的，其他線圖的斜率也沒發生重大的變化，若所有方法都是線性增長的，可以推知資料再增大也不會有變化
Sign in with Wallet
Connect another wallet