紅黑樹 - 無dummys元素去除

Question

我正在尋找指導如何實現刪除紅黑樹中的元素而不使用虛擬節點（即葉節點實際上是空指針）。我在google/wikipedia和標準文獻（sedgewick和cormen at al）上找到的所有實現都使用虛擬NIL節點，我想避免這種情況。

Answer 1

對於插入，岡崎的雙紅消除開箱即用。像往常一樣插入BST，並繼續消除雙紅，直到到達根部。

刪除紅色節點絕不是問題。請注意，從不從BST刪除兩個孩子的節點。如果您刪除帶有一個孩子的黑色節點，請將孩子塗黑並完成。只有黑葉（真正的，而不是假人）的刪除是一個問題。 Matt Might's approach可以使無虛擬節點的工作。訣竅在於首先使用馬特的「鼓泡」將葉子變成紅色。然後簡單地刪除它。

Here是一個代碼解決方案。