# 2025q1 Quiz 5,6
## Q3
### 目標
- 了解rb_tree insertion, deletion
- map 實作
[完整程式](https://github.com/Brianpan/kernel-quiz56/blob/master/q3.c)
### 插入節點
插入節點主要分成三個步驟
1. 找到插入節點的位置
2. 插入節點
3. 旋轉,重新著色紅黑數
```cpp=
map_node_t **pnode;
rb_link_node(node, parent, pnode);
rb_insert_color(node, &map->root);
```
內迴圈if/else邏輯是對稱,差別只在左右節點
情形一 叔叔節點是紅色
```graphviz
digraph {
G[fontcolor="BLACK"]
P[fontcolor="RED"]
U[fontcolor="RED"]
N
G->P
G->U
P->N
}
```
進行顏色對調並且往上再平衡
```cpp=
node = gparent
```
```graphviz
digraph {
G[fontcolor="RED" label="G (new N)"]
P[fontcolor="BLACK"]
U[fontcolor="BLACK"]
N[fontcolor="RED"]
G->P
G->U
P->N
}
```
情形二 叔叔節點是黑色
2-1 : zig-zag情形
```graphviz
digraph {
G[fontcolor="RED"]
P[fontcolor="BLACK"]
U[fontcolor="BLACK"]
N[fontcolor="RED" label="N (right child)"]
G->P
G->U
P->N
}
```
親代節點左旋轉
```graphviz
digraph {
G[fontcolor="RED"]
P[label="P" fontcolor="BLACK"]
a0[label="N" fontcolor="RED"]
a1[label="U" fontcolor="BLACK"]
G->a0
G->a1
a0->P
}
```
2-2 右旋轉祖父節點
```graphviz
digraph {
G[label="G (left child) "fontcolor="RED"]
P[label="P" fontcolor="RED"]
a1[label="U" fontcolor="BLACK"]
a0[label="N (right child)" fontcolor="BLACK"]
a1->G
G->a0
a0->P
}
```
```cpp=
void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
struct rb_node *parent, *gparent;
while ((parent = rb_parent(node)) && rb_is_red(parent)) {
gparent = rb_parent(parent);
if (parent == gparent->rb_left) {
{
struct rb_node *uncle = gparent->rb_right;
if (uncle && rb_is_red(uncle)) {
rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(gparent);
node = gparent;
continue;
}
}
if (parent->rb_right == node) {
__rb_rotate_left(parent, root);
struct rb_node *tmp = parent;
parent = node;
node = tmp;
}
rb_set_black(parent);
rb_set_red(node);
__rb_rotate_right(gparent, root);
} else {
{
struct rb_node *uncle = gparent->rb_left;
if (uncle && rb_is_red(uncle)) {
rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(gparent);
node = gparent;
continue;
}
}
if (parent->rb_left == node) {
__rb_rotate_right(parent, root);
struct rb_node *tmp = parent;
parent = node;
node = tmp;
}
rb_set_black(parent);
rb_set_red(node);
__rb_rotate_left(gparent, root);
}
}
rb_set_black(root->rb_node);
}
```
### 刪除節點
### 刪除節點主函數
這裡可以參考`__rb_erase_augmented`的解說,對應到核心的程式碼
主要判斷條件
- 要刪除的節點是否有兩個子節點
- 有
```graphviz
digraph {
G[fontcolor="BLACK"]
p0[label="x" fontcolor="BLACK"]
p1[label="P" fontcolor="BLACK"]
u[label="U" fontcolor="BLACK"]
n[label="N" fontcolor="BLACK"]
G->p0
G->p1
p1->u
p1->n
n->c0
n->c1
c1->a0
c1->a1
a0->t0
a0->t1
}
```
以此圖為例,假設刪除節點N
找到右子樹的最小節點t0取代N
如果t0有右子樹, 變成原本親代節點的左子樹
- 沒有
直接把剩餘子節點取代刪除節點
```graphviz
digraph {
G[fontcolor="BLACK"]
p0[label="x" fontcolor="BLACK"]
p1[label="P" fontcolor="BLACK"]
u[label="U" fontcolor="BLACK"]
n[label="N" fontcolor="BLACK"]
G->p0
G->p1
p1->u
p1->n
n->c1
c1->a0
c1->a1
a0->t0
a0->t1
}
```
此圖為例,直接讓c1當節點P的右子節點
如果節點node是黑色節點
需要進行樹的再平衡
```cpp=
void rb_erase(struct rb_node *node, struct rb_root *root)
{
struct rb_node *child, *parent;
int color;
if (!node->rb_left)
child = node->rb_right;
else if (!node->rb_right)
child = node->rb_left;
// has 2 children
else {
struct rb_node *old = node, *left;
node = node->rb_right;
// node becomes smallest node in the right subtree
while ((left = node->rb_left))
node = left;
// replace orginal node(old) by node
if (rb_parent(old)) {
if (rb_parent(old)->rb_left == old)
rb_parent(old)->rb_left = node;
else
rb_parent(old)->rb_right = node;
} else {
root->rb_node = node;
}
child = node->rb_right;
parent = rb_parent(node);
color = rb_color(node);
// case: original node has no left child
if (parent == old) {
parent = node;
} else {
if (child)
rb_set_parent(child, parent);
parent->rb_left = child;
node->rb_right = old->rb_right;
rb_set_parent(old->rb_right, node);
}
node->rb_parent_color = old->rb_parent_color;
node->rb_left = old->rb_left;
rb_set_parent(old->rb_left, node);
goto color;
}
parent = rb_parent(node);
color = rb_color(node);
if (child)
rb_set_parent(child, parent);
if (parent) {
if (parent->rb_left == node)
parent->rb_left = child;
else
parent->rb_right = child;
} else {
root->rb_node = child;
}
color:
if (color == RB_BLACK)
__rb_erase_color(child, parent, root);
}
```
刪除節點的再平衡
if/else一樣是判斷是左節點還是右節點,看一邊即可
兄弟節點other是紅色,對親代節左旋轉並且重新著色
other->黑色
parent->紅色
- other節點所有子節點是黑色節點
變更other節點成紅色節點
要往上重新調整因為other親代節點的左右子節點不符合紅黑數條件
other節點的左節點是紅色,右節點是黑色
```graphviz
digraph {
p[label="P" fontcolor="RED"]
n[label="N" fontcolor="BLACK"]
o[label="o" fontcolor="BLACK"]
l[label="l" fontcolor="RED"]
r[label="b" fontcolor="BLACK"]
p->n
p->o
o->l
o->r
}
```
對other右旋轉並且重新著色,改變other指標指到l
```graphviz
digraph {
p[label="P" fontcolor="RED"]
n[label="N" fontcolor="BLACK"]
l[label="l" fontcolor="BLACK"]
o[label="o" fontcolor="RED"]
r[label="b" fontcolor="BLACK"]
p->n
p->l
l->o
o->r
}
```
結束上述條件判斷後
```cpp=
rb_set_color(other, rb_color(parent));
rb_set_black(parent);
rb_set_black(other->rb_left);
__rb_rotate_left(parent, root);
node = root->rb_node;
break;
```
就是把parent左旋轉並且顏色對調
```graphviz
digraph {
o[label="O" fontcolor="RED"]
p[label="P" fontcolor="BLACK"]
n[label="N" fontcolor="BLACK"]
x
y
o->p
o->x
x->y
p->n
}
```
```cpp=
static void __rb_erase_color(struct rb_node *node,
struct rb_node *parent,
struct rb_root *root)
{
struct rb_node *other;
while ((!node || rb_is_black(node)) && node != root->rb_node) {
if (parent->rb_left == node) {
other = parent->rb_right;
if (rb_is_red(other)) {
rb_set_black(other);
rb_set_red(parent);
__rb_rotate_left(parent, root);
other = parent->rb_right;
}
if ((!other->rb_left || rb_is_black(other->rb_left)) &&
(!other->rb_right || rb_is_black(other->rb_right))) {
rb_set_red(other);
node = parent;
parent = rb_parent(node);
} else {
if (!other->rb_right || rb_is_black(other->rb_right)) {
rb_set_black(other->rb_left);
rb_set_red(other);
__rb_rotate_right(other, root);
other = parent->rb_right;
}
rb_set_color(other, rb_color(parent));
rb_set_black(parent);
rb_set_black(other->rb_right);
__rb_rotate_right(parent, root);
node = root->rb_node;
break;
}
} else {
other = parent->rb_left;
if (rb_is_red(other)) {
rb_set_black(other);
rb_set_red(parent);
__rb_rotate_right(parent, root);
other = parent->rb_left;
}
if ((!other->rb_left || rb_is_black(other->rb_left)) &&
(!other->rb_right || rb_is_black(other->rb_right))) {
rb_set_red(other);
node = parent;
parent = rb_parent(node);
} else {
if (!other->rb_left || rb_is_black(other->rb_left)) {
rb_set_black(other->rb_right);
rb_set_red(other);
__rb_rotate_left(other, root);
other = parent->rb_left;
}
rb_set_color(other, rb_color(parent));
rb_set_black(parent);
rb_set_black(other->rb_left);
__rb_rotate_left(parent, root);
node = root->rb_node;
break;
}
}
}
if (node)
rb_set_black(node);
}
```
Sign in with Wallet
Connect another wallet