最速のツリートラバーサル

Question

私はかなり大きなツリーデータ構造を持っています（ノードの削除や追加など）。私は、すべてのノードを（7のような特定の幅の深さまで）訪問し、それをリストに入れる、幅広い最初のアプローチを使用してツリーを走査しなければなりません。次に、関数はノードをループし、情報がリストの内部にある場合はtrueを返します。

これは、ノードをループするのに多くの時間がかかります。私はすべての単一のノードをすべての単一の子ノードにマップしてから、辞書を使用してノードをプルし、そのすべての子を（再帰的に）取得する必要があるとは思わない。私はこれをどのようにするべきですか？最速の方法は

Dictionary<Node, List<Node>>

• ノード、すべての子のリスト（子供たちの子供を含む...）のように、互いの間のすべてのノードをマップすることで、その後のノードを引き、そのような2,000人の子供速い取得します。しかし、ノードがどこにでも追加または削除された場合、すべての辞書ノードを更新する必要があります（これは面倒なようです）。もう1つの方法は、実行中に動的にループすることです（時間がかかります）。これは、ツリーの生成中、または実行時にループする間に、すべてを最初から一緒にマッピングすることです。

この状況を処理する最善の方法は何ですか？任意のアイデア、ポインタ、コメント、任意のものが役立ちます。現在のところ、この操作にはプログラム実行時間の約25％が必要です。

Answer 1

述語を評価するだけの場合は、ツリーをトラバースするときに直接行うことができます。リストをキャッシュしない限り、ツリー全体を最初にリストに入れる必要はありません。ツリーノード上の述語を直接評価することで、興味のある情報を最初に見つけたときに早期にトラバースを短絡/停止することができます。