6

ツリー (無制限の数のノードを持つことができる通常のツリーですが、クロスオーバーはありません。つまり、2 つの親ノードが同じ子ノードを指すことはありません) を使用するコードを書いています。とにかく、2つのこと：

1) ツリー内のサブツリーを見つけるためのよく知られたアルゴリズムはありますか?

2) このアルゴリズムを既に実装している Java ライブラリ (またはそのライブラリ) はありますか? 何もない場合でも、誰でも優れた汎用 Java ツリー ライブラリを推奨できますか?

これらのツリーは、検索機能のためではなく、ツリー形式でデータを保持するために使用したいと考えています。

少し拡張するには、特定のイベントが発生したときに何が起こるかの履歴を保持するために、ゲームの一部としてツリーを使用しています。たとえば、A は、別の 2 つの A をヒットできる 2 つの A をヒットできる B をヒットできます。

それは次のようになります。

    A
    |
    B
   /
  A 
 / \  
A   A
   / \
  A   A

もちろん、A と B だけではありません。私がやりたいことは (達成システムのために)、いつ A が 2 つの A にヒットしたかを知ることができるようにすることです:

  A
 / \
A   A

最初のツリーにそのサブツリーが含まれているかどうかを簡単に知りたいです。そして、そうする必要がなければ、そのためのすべてのコードを書く必要はありません:)

4

4 に答える 4

2

サブツリーに対する特定の制約を探していますか? そうでない場合は、単純なトラバーサルでサブツリーを識別することができます (基本的に、各ノードをサブツリーのルートとして扱います)。

ツリーに必要な API は、特定のアプリケーションによって大きく異なることがわかると思います。そのため、汎用的な実装はあまり役に立ちません。おそらく、ツリーがどのようなアプリケーションに使用されるかを教えていただければ、詳細を提供できます.

また、データ ストレージにツリーを使用しているだけの場合は、なぜツリーが必要なのかを自問することをお勧めします。その答えは、前の段落の質問にも答えるはずです。

于 2009-02-25T04:23:52.237 に答える
0

単純なトラバーサルよりも効率的な Knuth アルゴリズムの拡張があるのだろうか...

于 2009-02-25T05:22:52.533 に答える
0

1 つの大きな静的ツリーがあり、同じ大きなツリーで多くのサブツリーを検索する場合、ストレージの量に応じて、特定の深さまで、すべてのサブツリーのハッシュのセットで各ノードに注釈を付けることができます。その機能に費やすことを厭わない。次に、ハッシュ値から、そのハッシュ値を持つサブツリーのルートである一連のノードへのマップを作成します。次に、おそらくトラバーサルよりもはるかに安価な、それらのそれぞれをチェックして、同じ深さまでのクエリツリーのルートのハッシュを確認します。

于 2013-05-11T16:54:50.307 に答える