幅優先検索の推奨ツリータイプ

幅優先検索を実装する場合は、推奨タイプのツリーがどのようなものか聞いてきました。幅優先検索の推奨ツリータイプ

私はred-black/radix/triesのようなものでは特に有利なことはありませんでした。

使用するのに最適な種類は何ですか？

2016-05-23 Oli

どのように「ベスト」ですか？ [left-child right-sibling]（https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree）表現は、一般的なツリーの幅優先探索に非常に便利です。彼はバイナリーツリーや一般的なツリーについて特に質問しましたか？ –

彼は本当にそれに描かれません...チーム/製品に基づいて、私はこれがすでに実装しているものだと思っています。そして、私は同じことに着陸するかどうかを見たいと思っていました。全体の議論の一部！多方向のツリーは、彼が記述した問題に適用可能なようです（1つの次元に沿ってバケット化された番号を格納し、次に別の次元に格納し、次に別の次元に格納する）。 – Oli

しかし、あなたのリンクを読んで、私はなぜそれが最善であるかはっきりしません - 最初のレイヤーを取得するために片方だけをフォローするので、実装が簡単であることを意味しますか？ – Oli

すぐに2つの質問をします。

なぜ最初に息をする検索をしていますか？
他に何か木で同時にやっていますか？

一般に、幅優先探索を行う理由は、ルートに近い回答が必要なためです。あなたの木は、 "根の近く"が検索を行うためのあなたの基準と一致するような形にする必要があります。そして、その基準に合った形の木が必要です。これは、根から葉までの距離を最小限に抑えるように形状を最適化することとは一般に非常に異なります（赤黒の木のように）。

また、他に何をしているのかという心配は、これが共有データ構造であれば、すべてをロックしているということです。したがって、あなたが持つロックと競合と、それをどのように扱うのかを慎重に考えてください。

出典

2016-05-23 18:46:09 btilly

幅優先検索の推奨ツリータイプ

答えて

関連する問題