linux2023
contributed by < Paintako
>
1
閱讀前置處理器篇, 得知 x_prefix##
是透過 cpp
來展開產生程式碼的, 註釋也有提示 :
故產生出來的程式碼會像是 x_prefix##path_entry_t -> ex_path_entry_t
這段程式是 left-leaning 2-3 red-black trees
的實作
參考 LLRB
插入時, 先找到插入位置, 再從從樹葉一路往上到 root 調整
因為是左傾樹, 所以如果遇到插入時, 所以插入時遇到只有右子時需要往左調整
如果遇到連續兩個紅點 (or link), 則需要做 balance
而遇到 4 樹的情況, 需要做分裂
4 樹: node with 3 keys and 4 children
3、4 樹 in RB trees:
一開始不曉得為何 path
明明就是宣告成 array 的形式, 但卻可以直接賦值, 但後來想到, path 雖然是一個 array, 但 array 等同於指向 array[0] 的指針, 所以當我們使用 path->node 時, 相當於 path[0].node, 這樣的寫法可以省去紀錄 i, 並且只通過操作指標的方式取得 array 中的成員.
而這裡為何是 pathp[1]
? 因為我們只是操作 pointer, 而 pointer 的下一個成員即是樹中的下一個節點.
這邊插入一個新節點時, 從 root 開始比較, 並且把比較的結果 ( cmp ) 以及比較的節點紀錄在 path
中
找到要插入的位置後, 看 path
中前一個點 (父點) 的資訊, 前一個點中有 cmp
, 可以得知插入點是屬於左子 ( cmp < 0 ), 或者右子 (cmp > 0)
給定一節點 x, 考慮以下情形:
第一種 rotate_left
旋轉前:
旋轉後:
第二種 rotate_right
旋轉前:
旋轉後:
此段程式碼是檢查出現連續兩紅點的情形, 如果連續出現兩個紅點, 則旋轉調整, 而調整完後是 4 樹, 所以這邊先對 leftleft
調整成黑點, 則在調整完後, 就已經是 4 樹分裂的情形.
上面的是考慮 插入的點 > 比較節點
的情形, 如圖示
這種情況下, 比較節點有兩種情形:
沒有左子, 或者左子不是紅的 :
這種情況, 會先紀錄 cnode 的顏色, 並且左旋轉, 旋轉上來的 tnode 設為 cnode 的顏色, 並且因為旋轉後的 cnode 改成紅色, 並且往上繼續檢查
有左子, 並且左子是紅的, 也就是 4 樹, 如下圖:
這種情形只需調整顏色即可
Todo:
圖表改成 Graphviz
& TreeComparison
要刪除某個節點時, 一樣先從 root 一路往下尋找要刪除的點, 這邊我們假設已經找到要刪除的點, 用一個指針 nodep
記錄刪除地址, 再來往右子樹開始找, 找到 右子樹中最小的點
, 作為替代點, 這也就是為何 pathp->cmp
(第5行) 要設為 1 的原因.
接著, 判斷刪除點是否有 successor, 有的話把此點拉上來替代
這個點有三種情況:
首先是第一種情況: 後繼者在右子樹當中
pathp
, 並把連結顏色 assign 給後繼者再來考慮第二種情況, 也就是沒有右子, 但是有左子的情況, 有左子同樣判斷以下條件:
最後是第三種情況, 刪除點的位置位於 root, 這時只需要判斷 nodep == path
即可確定是不是刪除點 = root