赤い黒い木のセンチネル節の利点？

Question

私は二重リンクリストを作成しました。センチネルノードの利点は明らかでした。ヌルチェックもリスト境界の特別なケースもありませんでした。

今、私は赤い黒い木を書いており、そのような概念に何らかの利益があるかどうかを調べようとしています。

私の実装は、this article （トップダウンの挿入/削除）の最後の二つの機能に基づいています。著者は、挿入/削除アルゴリズムのルートで特殊なケースを避けるために、 "ダミーツリールート"または "ヘッド"を使用します。著者のヘッドノードは機能自体にスコープされています。その有用性は限られているようです。

私が出会ったもう1つの記事は、頭の上の永久的な根を反復の「終わり」として使用していると言いました。これは興味深いと思われますが、私はそれを試して、エンドイテレータとしてNULLを使用するよりも本当の利点を見いだせませんでした。私はまた、すべての空の葉ノードを表すために共有のセンチネルを使用したいくつかの記事を見つけましたが、これは最初のケースよりもさらに無意味です。

赤ちゃんの赤い木の中でセンチネルノードがどのように役立つかを詳しく説明できますか？

Answer 1

赤黒のツリーの実装では、ほとんどの場合、すべての葉に1つの黒いセンチネルが使用されます。

最初にヌルをチェックせずに色をチェックできるときに、多くのヌルチェックが保存されます。

もちろん、親ポインタを使用する実装では機能しません。これらの実装では、葉のセンチネルは、通常、リーフの位置ごとに異なるセンチネルを割り当てる必要があるため、使用されません。これは、多くのメモリを浪費します。