文字データを格納する 2 つのバイナリ ツリー T1 と T2 があり、重複は許可されます。
T2 が T1 のサブツリーであるかどうかを調べるにはどうすればよいですか? .
T1 には数百万のノードがあり、T2 には数百のノードがあります。
12880 次
10 に答える
18
T1 をトラバースします。現在のノードが T2 のルート ノードと等しい場合は、両方のツリー (T2 と T1 の現在のサブツリー) を同時にトラバースします。現在のノードを比較します。それらが常に等しい場合、T2 は T1 のサブツリーです。
于 2009-06-19T12:59:59.650 に答える
3
前処理を使用するアルゴリズムを提案します。
1) T1 ツリーを前処理し、可能なすべてのサブツリー ルートのリストを保持します (キャッシュ リストには数百万のエントリがあります)。
2) ルートに保持されているデータの降順でルートのキャッシュされたリストをソートします。文字ツリーを解析して文字列にするなど、より洗練された並べ替え関数を選択することもできます。
3) 二分探索を使用して、必要なサブツリーを見つけます。ノード数がT2ノード数と等しくない（または深さが異なる）サブツリーをすぐに拒否できます。
ステップ 1) と 2) は 1 回だけ実行する必要があることに注意してください。その後、前処理された同じ結果を使用して、多くのサブツリー候補をテストできます。
于 2009-06-19T13:06:45.550 に答える
2
両方のツリーのルートが与えられ、ノードが同じタイプであるとすると、なぜT2のルートがT1にあることを確認するだけでは不十分なのですか？
「木Tが与えられた」とは、Tのルートとノードのデータ型へのポインタが与えられたことを意味すると思います。
よろしく。
于 2010-01-08T10:22:17.450 に答える
2
ツリーがどのような方法でもソートされていない場合、ブルート フォース検索を実行する以外に方法はありません。ツリーをウォークスルーし、ツリーT1の最初のノードに一致するノードに到達するかどうかを確認しますT2。そうでない場合は、トラバースを続けT1ます。もしそうなら、次のノードが一致するかどうかを確認し、 の終わりが見つかるまで続けます。T2この場合、ヒットがあります。あなたのツリーT2は確かに のサブツリーですT1。
(リーフからノードまで)のすべての単一ノードの深さがわかっている場合T1は、探しているサブツリーほど深くないノードをスキップできます。これにより、多くの不要な比較を排除できます。T1とT2がバランスが取れているとすると、treeT1の深さの合計は 20 ( 2**20> 1,000,000) になり、treeT2の深さは 7 ( 2**7> 100) になります。最初の 13層(8192 ノード、または 14 層と 16384 ノードですか?)を歩くだけで、約T190% をスキップできT1ます。
ただし、サブツリーT2によって、 のリーフ ノードが のリーフ ノードでもあることを意味する場合T1は、 の最初のトラバーサルを実行してT1、すべてのノードの深さ (リーフからノードまでの距離) を計算し、同じ深さを持つサブツリーのみをチェックできます。としてT2。
于 2009-06-19T13:04:05.510 に答える
2
メモリ/ストレージにバインドされている場合（つまり、ツリーを事前に操作して別の形式で保存できない場合）、他の回答で提案されているブルートフォース検索よりも優れた方法はおそらくないでしょう（P1をトラバースして探します） P2 の一致するルート、ノードが実際に一致するサブツリーのルートであるかどうかを判断するために両方をトラバースし、一致しない場合は元のトラバーサルを続行します)。この検索は O(n * m) で実行されます。ここで、n は P1 のサイズ、m は P2 のサイズです。利用可能なツリー データに応じて深度チェックやその他の潜在的な最適化を行うと、この人は少し最適化されますが、それでも一般的には O(n * m) です。特定の状況によっては、これが唯一の合理的なアプローチになる場合があります。
メモリ/ストレージに縛られておらず、多少の複雑さを気にしない場合は、一般化された接尾辞ツリーの助けを借りて、最も長い一般的な部分文字列の問題に減らすことで、これを O(n + m) に改善できると思います。同様の問題に関するこれに関する議論は、ここで見つけることができます。たぶん、もっと時間があれば、戻ってきて、実装の詳細を編集します。
于 2009-06-19T14:22:00.500 に答える
1
私の考えが正しいかどうかはわかりません。それにもかかわらず、あなたのパーソナリティのために。
- ツリー 1 とツリー 2 でポストオーダー ウォークを実行し、それを P1 と P2 と呼びます。
- P1 と P2 を比較します。それらが異なる場合。ツリーはサブツリーではありません。出口。
- それらが同じ場合、または P1 が P2 に含まれている場合。どちらがサブツリーであるかを決定できます。
于 2009-06-19T13:26:00.567 に答える
0
総当たり攻撃が必要だと思いますが、T1でT2のルートを見つけた後、なぜ木を一致させる必要があるのでしょうか。これは、ツリーが同一であるかどうかを確認する必要がない場合と同じではありません（ツリー全体を比較するだけで済みます）。
値ではなく、ツリーT1およびT2、ポインターが与えられます。
ノードT2（ポインター）がT1ツリーに存在する場合。
次に、ツリーT2はT1のサブツリーです。
編集：
T2が実際にはオブジェクトごとに異なるツリーであると言われている場合にのみ、T1にサブツリーがあるかどうかを確認する必要があります。これはT2と同じです。
その後、これは機能しません。
そして、ここですでに説明したソリューションを選択する以外に選択肢はありません。
于 2012-09-25T15:37:30.883 に答える