ツリーをトラバースするのに最も最適なアルゴリズム（アプローチ）は何ですか？

Question

ウィキペディアで述べたように、ツリーデータ構造をトラバースするための複数のアルゴリズムがあります。しかし、アルゴリズムの中には、他のグラフの組み合わせのようなものがあります。双方向検索は、ツリーではなく他のグラフではほとんど役に立ちます。しかし、木では木の終わりがほとんど分からず、根や子からしか始めることができません。

このケースでは、検索処理でマルチプロセッシングやマルチスレッドを組み込むことができるかもしれません。しかし、私はこれを説明している包括的なアプローチを見つけることができませんでした。

今、私の質問は基本的に何を我々は全体のデータ構造へのアクセスを持っていないとき（ファイルのディレクトリのようになどのインデックスにそれら、できるようにするには）木を横断する最も最適化された方法であるということですか？

Answer 1

バイナリ検索ツリーのトラバースを試行してください。検索の複雑さはnlognであり、トラバースはnであり、これは最高と考えられます。

例：http://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

Answer 2

最も最適化されたアルゴリズムは、通常、特定のユースケースやプラットフォーム向けに最適化です。

あなたが前順後順や、順序どおり行うかどうかは関係ありません。または、DFSまたはBFSのどちらを実行するのか。 重要なもの：

• ツリーはどのくらいですか？それは記憶に収まるのだろうか？
• 木はどれくらい深いですか？あなたは再帰を使うことができますか、明示的な別のスタックを使わなければなりませんか？
• ノードの子をどのように見つけるか。あなたはハードドライブ/ネットワークにアクセスする必要がありますか？
• トラバーサルで見つかったノードで何をしたいですか？この操作が十分に長い場合、トラバーサルを最適化する価値はありません。
• スレッド間でデータをどのように共有しますか？
• ツリー内のノードはどのように分散されていますか？それは均等な分布に似ていますか、あるいは非常に長いものと非常に短いものがありますか？
• ノードキーの大きさ（これは、データの局所性と1つのL1/L2キャッシュラインに収まるデータの量に影響します）