Tarjanのトップダウン赤い黒のツリーの効率

Tarjanのトップダウン赤い黒のツリーアルゴリズムと他の赤い黒ツリーアルゴリズム（例えば、Robert Sedgewickのアルゴリズム）との関係については、私は疑問に思います。誰もトップダウンアルゴリズムとボトムアップアルゴリズムの結果を比較しましたか？私はそれが後で並行させることを計画しているので、私が基本アルゴリズムとして持っている必要があるアルゴリズムを決めるのに役立つので教えてください。（トップダウンとボトムアップの比較だけでなく、これらの研究者によるさまざまなアルゴリズム間の比較も欲しいです）Tarjanのトップダウン赤い黒のツリーの効率

出典

2016-05-27 Shreyas Gokhale

私はこの分野でほとんど仕事がありませんでした。異なるバランスのとれたBST（AVL対RB対Splay）の間で実行されたいくつかのパフォーマンステストがありますが、私の知る限りでは、赤黒のツリーの亜種について実行されたものは逸話的です。ある特定のケースでの実装。

赤黒のツリーを実装することに決めた場合は、いくつかのバリアントと言語を選択し、ユースケースに応じてベンチマークする必要があります。 - Javaの - GPLv3の - （Sedgewick /ウェイン）

Left-Leaning RB Tree：あなたは私の知るいくつかの主要な味ですここでは、ネット上に赤、黒の木の種類のいくつかのオープンソース実装を見つけることができます
再帰BU反復TDインサート/削除、削除/挿入 - C - MIT状 - 再帰BUインサート
（eternallyconfuzzled）、再帰TD削除 - ジャワ - MIT - （me）

は、これらの実装されています彼らはすべて持っているのでスペース効率的親ポインタを使用しない共通点。ただし、それらを適切にベンチマークし、必要に応じて最適化する必要があります。

出典

2016-05-27 08:49:14

ありがとうございます！なぜ親ポインタが問題になるのか説明できますか？ –

可能な限りスペース効率が必要な場合は、問題があります。効率性を調べる場合は、私が指摘した実装と親ポインタを使用する実装を比較する必要があります。親ポインタには問題ありません。 –

わかりました！私は、それが別の方法で実装するのがより簡単になるため、私は親ポインタを使用していますが、再帰を実装する際に間違いを犯してしまい、本当にプログラムを駄目にすることがあります。 –

Tarjanのトップダウン赤い黒のツリーの効率

答えて

関連する問題