red-black-tree - 赤黒木-ダミーなしの要素の削除

Question

ダミーノード（つまり、リーフノードが実際にはnullポインターである）を使用せずに赤黒木で要素の削除を実装する方法のガイドを探しています。私がグーグル/ウィキペディアと標準的な文献（sedgewickとcormenなど）で見つけたすべての実装は、ダミーのNILノードを使用しています。これは避けたいと思います。

Answer 1

挿入については、岡崎のダブルレッド除去がすぐに機能します。通常どおり BST に挿入し、ルートに到達するまでダブルレッドを削除し続けます。

赤のノードを削除しても問題はありません。BST から 2 つの子を持つノードを決して削除しないことに注意してください。1 つの子を持つ黒のノードを削除する場合は、子を黒く着色すれば完了です。黒い葉 (ダミーではなく本物) の削除のみが問題です。Matt Might のアプローチは、ダミー ノードなしで機能させることができます。トリックは、マットの「バブリング」を使用して、最初に葉を赤くすることです。その後、単にそれを削除します。

これがコードによる解決策です。