2023q1 Homework4 (quiz4)

contributed by < DokiDokiPB >

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

• 透過以上 USFCA 大學的 B tree 視覺化工具 顯示 2-3 tree
• 使用 線上工具 ysangkok.github.io 繪製 B-tree 的 Graphviz code

測驗 1

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

• 從 GitHub 搜尋簡單的程式碼與介紹，初步了解最基本的紅黑樹與 B tree 介紹。
  • anandarao/Red-Black-Tree 實作
  • 資料結構與演算法：Red Black Tree 紅黑樹 part 1 by Joseph
  • 閱讀教材的簡報 Left-Leaning Red-Black Trees，照著簡報中了解 LLRBT 對應的 2-3 樹與 2-3-4 樹。
  • Nicholas Tsai B Tree Deletion

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

$\to$ 原本 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 個空白縮排。

jserv

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

轉換成

若 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 之後，依據左傾的規定，必須左旋

轉換成

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

轉換成

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

轉換成

tree_remove() 函式

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

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

jserv

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

推敲其原理

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

對應 LLRBT

移除元素 2 的節點

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

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

• 往上走訪過程對應到以下程式碼，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 後的圖例：

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

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

xx