Try   HackMD

2025q1 Quiz 5,6

Q3

目標

  • 了解rb_tree insertion, deletion
  • map 實作

完整程式

插入節點

插入節點主要分成三個步驟

  1. 找到插入節點的位置
  2. 插入節點
  3. 旋轉,重新著色紅黑數




map_node_t **pnode;

rb_link_node(node, parent, pnode);
rb_insert_color(node, &map->root);

內迴圈if/else邏輯是對稱,差別只在左右節點
情形一 叔叔節點是紅色







%0



G

G



P

P



G->P





U

U



G->U





N

N



P->N

進行顏色對調並且往上再平衡

node = gparent







%0



G

G (new N)



P

P



G->P





U

U



G->U





N

N



P->N

情形二 叔叔節點是黑色
2-1 : zig-zag情形







%0



G

G



P

P



G->P





U

U



G->U





N

N (right child)



P->N

親代節點左旋轉







%0



G

G



a0

N



G->a0





a1

U



G->a1





P

P



a0->P

2-2 右旋轉祖父節點







%0



G

G (left child) 



a0

N (right child)



G->a0





P

P



a1

U



a1->G





a0->P






























































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的解說,對應到核心的程式碼

主要判斷條件

  • 要刪除的節點是否有兩個子節點
    • 有






%0



G

G



p0

x



G->p0





p1

P



G->p1





u

U



p1->u





n

N



p1->n





c0

c0



n->c0





c1

c1



n->c1





a0

a0



c1->a0





a1

a1



c1->a1





t0

t0



a0->t0





t1

t1



a0->t1

以此圖為例,假設刪除節點N
找到右子樹的最小節點t0取代N
如果t0有右子樹, 變成原本親代節點的左子樹

  • 沒有
    直接把剩餘子節點取代刪除節點






%0



G

G



p0

x



G->p0





p1

P



G->p1





u

U



p1->u





n

N



p1->n





c1

c1



n->c1





a0

a0



c1->a0





a1

a1



c1->a1





t0

t0



a0->t0





t1

t1



a0->t1

此圖為例,直接讓c1當節點P的右子節點

如果節點node是黑色節點
需要進行樹的再平衡






































































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節點的左節點是紅色,右節點是黑色







%0



p

P



n

N



p->n





o

o



p->o





l

l



o->l





r

b



o->r

對other右旋轉並且重新著色,改變other指標指到l







%0



p

P



n

N



p->n





l

l



p->l





o

o



l->o





r

b



o->r

結束上述條件判斷後







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左旋轉並且顏色對調







%0



o

O



p

P



o->p





x

x



o->x





n

N



p->n





y

y



x->y








































































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);
}
Last changed by 
 
Brian Pan
0
4

Read more

linux2025-homework5

<input class="task-list-item-checkbox"type="checkbox">lab0c

Jun 15, 2025
Discussion

結論：ktcp略優於ebpf

Jun 12, 2025
Linux 核心專題筆記

2023開發紀錄

Jun 12, 2025
2025q1 Homework2 (lab0)

contributed by < Brianpan >

May 17, 2025
Read more from Brian Pan
Published on HackMD