1

私は次のものを持っているとしましょう：

   _____W_____
  |     |     |
 _T_   _L_   _X_
|   | |   | |   |
A   B A   B A   B

ご覧のとおり、これは標準ツリーです (Wに 3 つの子があることからもわかるように、バイナリ ツリーではありません)。私の目標は、A B下位レベル全体で子シーケンスが繰り返されているという事実を特定することです。

より一般的に言えば、ツリーのルートから始めて、自分の子供の子サブツリー セット (基本的には孫サブツリー セット) を見て、それらがツリー全体で同一であるかどうかを判断できるようにしたいと考えています。レベル、次に私の子供たちに再帰し、それぞれの小さなスコープで同じことを行います. ツリー全体の一番下まで、すすぎ、繰り返します。

T私が思いついた単純な解決策は、各サブツリー (この場合は、L、および)の幅優先 (または深さ優先) トラバーサルを実行し、X思いついた単語 (最初の文字を引いたもの) を比較することです。 ）。この場合の幅優先トラバーサルはTAB、 、LAB、およびを生成XABし、最初の文字を無視すると、それらがすべて であることがわかりますAB。しかし、ツリーが代わりに次のようになっていると想像してください。

   _____W_____
  |     |     |
 _T_   _L_   _X_
|   | |   | |   |
A   B Q   B A   B

A最初の をつかみ、それから をつかむことができれば、はるかに効率的でありQ、それらが同じではなく、検索を続けて短絡しても意味がないことに気付くでしょう。

ここで適用できる「明白な」アルゴリズムがあるかどうか、またはおそらく、この特定の問題のために作成されたアルゴリズムがあるかどうかを主に調べています。見たことがない、見つけられない、または検索方法がわからないのいずれかです。

（この質問には「Java」タグを付けました。これは、このツリー構造の実際の実装[および私が適用し、未回答の質問がない他のアルゴリズム]がたまたまその言語であるからです。疑似コードを翻訳できます。 、 同じように。）

編集- 上記の最初のツリーのいくつかの例のステップとして、これはより理にかなっているかもしれません:

  • W(ルート) から開始します。
  • 2 人以上の子供がいますか? この場合、はい、3: T, L, X.
  • T、L、およびXの子サブツリーを比較します。
  • 、、およびの子サブツリーのセットは、Tのスコープのレベル全体で同じですか? この場合、はい、それはずっとです。上記の 2 番目のツリーでは、答えはノーです。LXWA BQ
  • Wの子T、、、、LにドロップダウンしXます。上記の手順を繰り返します。T子供が2人以上いますか？はい、AそしてB。彼らには子供がいますか？上記の例では、いいえ、何もする必要はありません。しかし、 と が子、孫などを含む完全なサブツリーであると想像AしてくださいB。ここで問題になるのは、これらのサブツリーはのスコープのレベル全体でT同じですか? ではA son of T、 の子サブツリーのセットは の子サブツリーのセットと同一B son of Tですか?
4

1 に答える 1

1

注: 等値チェックを短絡することは、列挙戦略よりも「はるかに効率的」であるという主張は、テストが必要です。入力セットがそれほど大きくない場合、違いが生じる可能性は低く、大きい場合は、おそらく代表的なデータで測定する必要があります。

そうは言っても、すべてのサブツリーを左から右に比較し、すべてのセットを前もって生成するのではなく、ツリー全体で一度に 1 つずつ要素を調べようとするアルゴリズムの疑似コードを次に示します。

function AllLeavesEqual(tree):
  if (tree.children.size < 2):
    return true
  subtreeIterators = [GetLeafIterator(t) for subtree in tree.children]
  baseLeaves = subtreeIterators[0]
  comparisonLeaves = subtreeIterators[1:]
  pop one item off of each iterator
  while (baseLeaves.hasNext()):
    nextLeaf = baseLeaves.next()
    for comparisonIterator in comparisonLeaves:
      if (!comparisonIterator.hasNext() or comparisonIterator.next() != nextLeaf):
        return false

  return true iff no iterator in comparisonLeaves satisfies iterator.hasNext()

function GetLabelIterator(tree):
  return Iterator:
    stack = Stack(tree)

    define next():
      t = Pop(stack)
      push each of t.children onto stack in reverse order
      return t.label

    define isEmpty():
      return stack.isEmpty()

ここで行っているのは、すべてのサブツリーのすべてのラベルが等しいかどうかをチェックすることです。秘訣は、ラベル セットを具体化するのではなく、イテレータを使用して、各サブツリーの事前順序走査を遅延して効果的に実行することです。必要なレイジー ツリー ノード列挙の他の方法を使用することもできます。

2 つの点に注意してください。まず、このトラバーサルは、必要なレベル順のトラバーサルではないことに注意してください。代わりに、事前注文トラバーサルです。レベル順トラバーサルを使用することが本当に重要な場合は、上で書いたイテレータをそのように列挙するイテレータに置き換える必要があります。第二に、説明したように、このアルゴリズムは構造的等価性をチェックせず、順序付けられたトラバーサルの等価性のみをチェックします。問題がある場合、これは簡単に修正できます。

于 2013-10-08T01:15:07.100 に答える