contributed by < DokiDokiPB
>
巨集展開後的程式碼 Github gist
其中用於觀察紅黑樹行為的函式為good()
並附上printTreeInorder()
用於印出紅黑樹結構
撰寫這題時候發現自己缺少閱讀
其中以下撰寫的內容的核心概念:
原本 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)
,並分成三段程式碼。這裡主要展示第二段與第三段
在以下圖例中,節點元素有 *
表示當前 *cnode
指向的節點
使用 clang-format
對上述程式碼進行一致排版,確保以 4 個空白縮排。
插入 1 元素之後,對應的示例圖
轉換成
若 2 為根節點,則最終會被標注為黑色
對應 else case /* Lean left. */
的程式碼,以示例圖表示其運作方式:
插入元素 7 之後,依據左傾的規定,必須左旋
轉換成
這裡以再加入一個元素 8 作為範例,對應 if case
的程式碼,分裂 4 樹
轉換成
再因為 LLRB 規則, 5*
要左旋,從
轉換成
tree_remove()
函式我決定直接跑一遍來看程式碼的作用。
在 ChatGPT 出來後,工程師寫程式碼的效率可以更高,其中對於絕大多數的軟體工程師,閱讀如紅黑樹移除節點的複雜程式碼,第一時間都無法知道或驗證程式碼作用。
自己不懂的話,不要拉其他人下水。
紅黑樹本身是 2-3 樹或 2-3-4 樹的變形,移除某個節點產生的平衡行為皆對應 2-3 tree 的操作。
巨集展開後的程式碼請參考 LLRBT_m.cpp
,這裡使用測試資料來了解其中的運作模式。
依序輸入測試資料:1, 2, 3, 4, 40, 41
,獲得
對應 LLRBT
依據步驟(這裡以「2」表示元素 2 的節點):
pathp
,紀錄到 2 的中序下一個的節點 3pathp
開始往上修正pathp->node
為 3,此時修改程指定的顏色,3 修改為黑色,1 修改為紅色。樹平衡並離開函式。在使用 GDB 觀察程式碼運作後,會發現這些步驟可以對應 2-3 樹中的行為:
xx