Try   HackMD

2023q1 Homework4 (quiz4)

contributed by < DokiDokiPB >

巨集展開後的程式碼 Github gist
其中用於觀察紅黑樹行為的函式為 good()
並附上 printTreeInorder() 用於印出紅黑樹結構

測驗 1

撰寫這題時候發現自己缺少閱讀

其中以下撰寫的內容的核心概念:

原本 2-3 樹或 2-3-4 樹對應多種紅黑樹,但是限制為左傾紅黑樹後,便成為一對一的關係,只對應一種紅黑樹。
因此在了解原理與程式碼運作上,可以先透過 2-3 樹行為去了解紅黑樹插入與移除行為。

了解其原理

根據註釋,這裡使用的是 C macro implementation of left-leaning 2-3 red-black trees.

tree_insert() 函式

透過 USFCA 大學的 B tree 視覺化工具 加入節點,可以很好的了解依序輸入後獲得的 2-3 樹,就能對照 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),並分成三段程式碼。這裡主要展示第二段與第三段

  • 第一段程式碼:紅黑樹也是一種二元搜尋樹,紀錄走訪過的節點
  • 第二段程式碼:透過修改顏色的方式,消去 4 樹成為 2 樹與 3 樹
  • 第三段程式碼:將 4 樹分裂、將 2 樹右傾改為左傾

在以下圖例中,節點元素有 * 表示當前 *cnode 指向的節點

第二段程式碼
for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) {              \
    x_type *cnode = pathp->node;                                             \
    if (pathp->cmp < 0) {                                                    \
        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(node_t, link, leftleft);                              \
            rbtn_rotate_right(x_type, x_field, cnode, tnode);                    \
            cnode = tnode;                                                       \
            }                                                                      \
        } else {                                                                 \
            /* ... */                                                              \
        }                                                                        \
    pathp->node = cnode;                                                     \
}          

使用 clang-format 對上述程式碼進行一致排版,確保以 4 個空白縮排。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

插入 1 元素之後,對應的示例圖







BST



2

2



1

1



2->1





n2

n2



2->n2





3

3*



3->2





n1

n1



3->n1





轉換成







BST



1

1



3

3



2

2*



2->1





2->3





若 2 為根節點,則最終會被標注為黑色

第三段程式碼

for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--)            \
{                                                                      \
    x_type *cnode = pathp->node;
    if (pathp->cmp < 0)                                                \
    {
    ...
    }else{
        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, tred);              \
            rbtn_red_set(x_type, x_field, cnode);                      \
            cnode = tnode;                                             \
        }     
    }
    pathp->node = cnode;
}            

對應 else case /* Lean left. */ 的程式碼,以示例圖表示其運作方式:
插入元素 7 之後,依據左傾的規定,必須左旋







BST



4

4



5

5



5->4





6

6*



5->6





7

7



6->7





n1

n1



6->n1





n2

n2



轉換成







BST



4

4



5

5



5->4





7

7*



5->7





n1

n1



7->n1





6

6



7->6





n2

n2



這裡以再加入一個元素 8 作為範例,對應 if case 的程式碼,分裂 4 樹







BST



4

4



5

5



5->4





7

7*



5->7





8

8



7->8





6

6



7->6





轉換成







BST



4

4



5

5



5->4





7

7*



5->7





6

6



8

8



7->6





7->8





再因為 LLRB 規則, 5* 要左旋,從







BST



4

4



5

5*



5->4





7

7



5->7





6

6



8

8



7->6





7->8





轉換成







BST



4

4



6

6



8

8



7

7*



7->8





5

5



7->5





5->4





5->6





tree_remove() 函式

我決定直接跑一遍來看程式碼的作用。
在 ChatGPT 出來後,工程師寫程式碼的效率可以更高,其中對於絕大多數的軟體工程師,閱讀如紅黑樹移除節點的複雜程式碼,第一時間都無法知道或驗證程式碼作用。

自己不懂的話,不要拉其他人下水。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

紅黑樹本身是 2-3 樹或 2-3-4 樹的變形,移除某個節點產生的平衡行為皆對應 2-3 tree 的操作。

推敲其原理

巨集展開後的程式碼請參考 LLRBT_m.cpp,這裡使用測試資料來了解其中的運作模式。
依序輸入測試資料:1, 2, 3, 4, 40, 41,獲得







g



node0

 

2

 

4

 



node1

 

1

 



node0:f0->node1





node2

 

3

 



node0:f1->node2





node3

 

40

 

41

 



node0:f2->node3





對應 LLRBT







這圖片很難調整的二元樹的拉



2

2



3

3



2->3





1

1



2->1





n3

n3



2->n3





40

40



4

4



4->2





41

41



4->41





41->40





n1

n1



41->n1





n2

n2



41->n2





移除元素 2 的節點

依據步驟(這裡以「2」表示元素 2 的節點):

  • 程式碼找到 2 ,並紀錄沿途走過的路徑 pathp,紀錄到 2 的中序下一個的節點 3
  • 2 與 3 對調,3 變為紅色,2 變為黑色並且被移除,並從 pathp 開始往上修正






這圖片很難調整的二元樹的拉



40

40



3

3



1

1



3->1





2

2



3->2





n3

n3



3->n3





4

4



4->3





41

41



4->41





41->40





n1

n1



41->n1





n2

n2



41->n2





  • 往上走訪過程對應到以下程式碼,pathp->node 為 3,此時修改程指定的顏色,3 修改為黑色,1 修改為紅色。樹平衡並離開函式。
if (leftleft && rbtn_red_get(x_type, x_field, leftleft)) {
    /* ... */
}else{
    /*        ||                                      */
    /*      pathp(r)                                  */
    /*     /        \\                                */
    /*   (b)        (b)                               */
    /*   /                                            */
    /* (b)                                            */
    rbtn_red_set(x_type, x_field, left);
    rbtn_black_set(x_type, x_field, pathp->node);
    return;
}

在使用 GDB 觀察程式碼運作後,會發現這些步驟可以對應 2-3 樹中的行為:

  • 原本的 2-3 樹,替換並移除 2 後的圖例:






g



node0

 

3

 

4

 



node1

 

1

 



node0:f0->node1





node2

 

X

 



node0:f1->node2





node3

 

40

 

41

 



node0:f2->node3





  • 該節點有 underflow,需要進行節點合併,這裡跟左邊節點合併
  • 並且將 3 傳入至該合併的節點






g



node0

 

4

 



node1

 

1

 

3

 



node0:f0->node1





node2

 

40

 

41

 



node0:f1->node2





延伸問題開發出的效能評比程式,分析不同 rbtree 實作

xx