owned this note   changed 2 years ago  
Published Linked with GitHub

2023q1 Homework4 (quiz4)

contributed by < LiChiiiii >

測驗題目：quiz4

測驗一

在測驗一提供的程式碼中定義

typedef rb_tree(node_t) tree_t;
rb_gen(static, tree_, tree_t, node_t, link, node_cmp);

對照 rb.h 之巨集的使用，展開 rb_gen(static, ex_, ex_t, ex_node_t, ex_link, ex_cmp) 巨集可以得到插入、刪除等功能之函式。

推敲其設計思維

tree_insert()

將巨集 x_attr void x_prefix##insert(x_rbt_type *rbtree, x_type *node) 展開為 static void tree_insert (tree_t *rbtree, node_t *node) ，此函式將新節點插入紅黑樹中，主要有三個步驟：

  1. 根據節點的比較結果遞迴查找插入位置
  2. 依次從下往上檢查是否需要旋轉
  3. 將根節點設為黑色。

舉個例子來說，現在有一個紅黑樹。

digraph BST {
    graph[ordering="out"]
    node [shape=circle, fixedsize=true, style=filled,width=.5]
    
    2[fillcolor=red]
    
    A,B,C,D,E,F[fontsize=0,color=transparent] 
    7 -> {2 11}
    2 -> {1 5}
    1 -> {A B} 
    5 -> {C D}
    11 -> {E F}
    
}

我們想插入新的節點 3，會先用 BST 的概念尋找插入的位置。

  1. 3 與 7 比較，紀錄 cmp = -1 ，並往左進行下一層尋找。
  2. 3 與 2 比較，紀錄 cmp = 1 ，並往右進行下一層尋找。
  3. 3 與 5 比較，紀錄 cmp = -1 ，並往左進行下一層尋找，得到 NULL 跳出迴圈，把插入位置指向此節點，也就是 pathp->node = node 。
digraph BST {
    graph[ordering="out"]
    node [shape=circle, fixedsize=true, style=filled,width=.5]
    
    2,3[fillcolor=red]
    
    A,B,C,D,E,F[fontsize=0,color=transparent] 
    7 -> {2 11}
    2 -> {1 5}
    1 -> {A B} 
    5 -> {3 D}
    11 -> {E F} 
}

由於在尋找插入的位置的過程中，有依序紀錄經過每個節點及其 cmp 至名為 path 的陣列，因此當找到插入位置的同時，也得到了以下陣列 path 。

digraph path{
    // node [shape=plaintext, fontcolor=black, fontsize=18];
    // "Pointers:" -> "Values:" [color=white];

    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    pointers [label="<f0> | <f1> | <f2>pathp |<f3> pathp[1]", color=white];
    values [label="<f0> 7, -1 | <f1> 2, 1 | <f2> 5, -1 | <f3> 3", fillcolor=pink, style=filled];

    // { rank=same; "Pointers:"; pointers }
    // { rank=same; "Values:"; values }

    edge [color=black];
    pointers:f2 -> values:f2;
    pointers:f3 -> values:f3;
}

接下來將 pathp 反向回去，判斷每個 pathp 的 cmp 值來檢查是否需要旋轉。
如果 cmp < 0 ，且出現左邊狀況則進行旋轉成右邊的樣子。

digraph BST {
    graph[ordering="out"]
    node [shape=circle, fixedsize=true, style=filled,width=.7]
    
    left, leftleft [fillcolor=red]
    A,B[fontsize=0,color=transparent] 

    cnode -> left
    cnode -> A [color=transparent]
    left -> leftleft
    // left -> B [color=transparent]
    

    
    left_[fillcolor=red]
    A,B[fontsize=0,color=transparent] 
    left_ -> leftleft_
    left_ -> cnode_
}

x_type *left = pathp[1].node;                           
rbtn_left_set(x_type, x_field, cnode, left);            
if (!rbtn_red_get(x_type, x_field, left))               
    return;                                             
x_type *leftleft = rbtn_left_get(x_type, x_field, left);
if (leftleft && rbtn_red_get(x_type, x_field, leftleft)) {     
    /* Fix up 4-node. */    
    x_type *tnode;                                     
    rbtn_black_set(x_type, x_field, leftleft);                   
    rbtn_rotate_right(x_type, x_field, cnode, tnode);   
    cnode = tnode;                                      
}

如果 cmp >= 0 ，

  1. 出現左邊狀況則進行顏色轉換設定成右邊的樣子。
digraph BST {
    graph[ordering="out"]
    node [shape=circle, fixedsize=true, style=filled,width=.7]
    
    left, right [fillcolor=red]

    cnode -> left
    cnode -> right
    
    cnode_[fillcolor=red]
    cnode_ -> left_
    cnode_ -> right_
}
  1. 出現左邊狀況則進行旋轉成右邊的樣子。這邊是為了滿足 LLRBT 的左傾條件。
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]
}

x_type *right = pathp[1].node;   
rbtn_right_set(x_type, x_field, cnode, right);  
if (!rbtn_red_get(x_type, x_field, right)) 
    return;        
x_type *left = rbtn_left_get(x_type, x_field, cnode);  
if (left && rbtn_red_get(x_type, x_field, left)) {  
    /* Split 4-node. */    
    rbtn_black_set(x_type, x_field, left); 
    rbtn_black_set(x_type, x_field, right);     
    rbtn_red_set(x_type, x_field, cnode);          
} else { 
    /* Lean left. */    
    x_type *tnode;          
    bool tred = rbtn_red_get(x_type, x_field, cnode); 
    rbtn_rotate_left(x_type, x_field, cnode, tnode);    
    rbtn_color_set(x_type, x_field, tnode, BBBB);  
    rbtn_red_set(x_type, x_field, cnode);    
    cnode = tnode;        
}

最後將根節點設為黑色。

tree_remove()

將巨集 x_attr void x_prefix##remove(x_rbt_type *rbtree, x_type *node) 展開為 static void tree_remove(tree_t *rbtree, node_t *node) ，此函式用於刪除紅黑樹中的節點，跟 tree_insert() 一樣的方式去尋找要刪除的節點，只是額外加上 if(cmp==0) ，若條件式成立，則表示找到要刪除的節點，接著就是找出節點的 successor ，來為交換做準備。
舉個例子來說，現在有一個紅黑樹，我想刪除節點 2。

digraph BST {
    graph[ordering="out"]
    node [shape=circle, fixedsize=true, style=filled,width=.5]
    
    2[fillcolor=red]
    
    A,B,C,D,E,F[fontsize=0,color=transparent] 
    7 -> {2 11}
    2 -> {1 5}
    1 -> {A B} 
    5 -> {C D}
    11 -> {E F}
    
}

可以得到這個 path 陣列。

digraph path{
    // node [shape=plaintext, fontcolor=black, fontsize=18];
    // "Pointers:" -> "Values:" [color=white];

    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    pointers [label="<f0> | <f1>pathp ", color=white];
    values [label="<f0> 7, -1 | <f1> 2, -1 ", fillcolor=pink, style=filled];

    // { rank=same; "Pointers:"; pointers }
    // { rank=same; "Values:"; values }

    edge [color=black];
    pointers:f1 -> values:f1;
}

在 cmp == 0 時，代表找到想刪除的節點，也就是找到節點 2，會設定 pathp->cmp = 1 ，並尋找此節點的 successor 。

if (cmp == 0) {
/* Find node's successor, in preparation for swap. */    
    pathp->cmp = 1;                                       
    nodep = pathp;                                           
    for (pathp++; pathp->node; pathp++) {                     
        pathp->cmp = -1;                                     
        pathp[1].node = rbtn_left_get(x_type, x_field, pathp->node);                                
    }                                                         
    break;                                                    
}

因此 path 陣列會變成

digraph path{
    // node [shape=plaintext, fontcolor=black, fontsize=18];
    // "Pointers:" -> "Values:" [color=white];

    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    pointers [label="<f0>pathp[-1] | <f1>pathp | <f2>pathp[1] ", color=white];
    values [label="<f0> 7, -1 | <f1> 2, 1 | <f2> 1, -1", fillcolor=pink, style=filled];

    // { rank=same; "Pointers:"; pointers }
    // { rank=same; "Values:"; values }

    edge [color=black];
    pointers:f0 -> values:f0;
    pointers:f1 -> values:f1;
    pointers:f2 -> values:f2;
}

測驗二

測驗三

Select a repo