0

Tarjan のトップダウン赤黒木アルゴリズムが、他の赤黒木アルゴリズム (たとえば、Robert Sedgewick によるもの) とどのように競合するのか疑問に思っています。さまざまなトップダウンおよびボトムアップ アルゴリズムの結果を比較した人はいますか? 後で並行処理を行う予定であるため、基本アルゴリズムとしてどのアルゴリズムを使用する必要があるかを判断するのに役立つので、お知らせください。（トップダウンとボトムアップだけでなく、これらの研究者によるさまざまなアルゴリズムの比較もお願いします！）

4

1 に答える 1

0

私が見つけた限りでは、この分野での仕事はほとんどありませんでした。異なるバランスの取れた BST (AVL 対 RB 対 splay) 間で実行されたパフォーマンス テストがいくつかありますが、私の知る限り、赤黒ツリーのバリアントに対して実行されたものは逸話的です: 「標準」に対する RB ツリーの 1 つのバリアントのベンチマーク1 つの特定のケースでの実装。

したがって、赤黒木を実装することに決めた場合は、いくつかのバリアントと言語を選択し、ユース ケースに従ってそれらをベンチマークする必要があります。ネット全体でさまざまな種類の赤黒ツリーのオープン ソース実装を見つけることができます。

  • 左寄りの RB ツリー- Java - GPLv3 - (Sedgewick/Wayne)
  • 再帰的な BU の挿入/削除、反復的な TD の挿入/削除 - C - MIT のような - (永遠に混乱)
  • 再帰的な BU 挿入、再帰的な TD 削除 - Java - MIT - ( me )

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

于 2016-05-27T08:49:14.313 に答える