ツリーが他のサブツリーであるかどうかを調べる

https://stackoverflow.com/questions/1017821

06-07-2019
|

質問

文字データを保存する2つのバイナリツリーT1とT2があり、重複が許可されています。
T2がT1のサブツリーであるかどうかを確認するにはどうすればよいですか？。
T1には数百万のノードがあり、T2には数百のノードがあります。

解決

トラバースT1。現在のノードがT2のルートノードと等しい場合、両方のツリー（T2とT1の現在のサブツリー）を同時にトラバースします。現在のノードを比較します。それらが常に等しい場合、T2はT1のサブツリーです。

他のヒント

前処理を使用するアルゴリズムを提案します：

1）T1ツリーを前処理し、可能なすべてのサブツリールートのリストを保持します（キャッシュリストには数百万のエントリがあります）。

2）ルートのキャッシュリストをデータの降順でソートし、ルートに保持します。文字列を文字列に解析するなど、よりエレガントなソート機能を選択できます。

3）バイナリ検索を使用して、必要なサブツリーを見つけます。ノードの数がT2のノード数に等しくない（または深さが異なる）サブツリーをすばやく拒否できます。

ステップ1）および2）は1回だけ実行する必要があることに注意してください。その後、同じ前処理結果を使用して、多くのサブツリー候補をテストできます。

ツリーが何らかの方法でソートされていない場合、 brute-force 検索を実行する以外の方法はありません。ツリー T1 を歩いて確認しますツリー T2 の最初のノードに一致するノードに到達するかどうかを確認します。そうでない場合は、 T1 の走査を続けます。その場合、次のノードが一致するかどうかを確認して、 T2 の終わりを見つけます。この場合、ヒットします。ツリー T2 は実際には T1 。

T1 のすべての単一ノードの深さがわかっている場合（リーフからノードまで）、探しているサブツリーほど深くないノードはスキップできます。これにより、多くの不必要な比較を排除できます。 T1 と T2 のバランスが取れているとすると、ツリー T1 の深さは20（ 2 ** 20 ＆gt; 1,000,000 ）およびツリー T2 の深さは7（ 2 ** 7 ＆gt; 100 ）。 T1 の最初の13個の layer を歩くだけで（8192ノード-または14層と16384ノードですか？）、約90をスキップできます。 T1 の％...



ただし、 subtree で T2 のリーフノードが T1 のリーフノードでもある場合、最初のトラバーサルを実行できます。  T1 のすべてのノードの深さ（リーフからノードまでの距離）を計算し、 T2 と同じ深さのサブツリーのみをチェックします。



	
		
	
	
			メモリ/ストレージの制約がある場合（つまり、ツリーを事前に操作して別の形式で保存できない場合）、おそらく他の回答で提案されたブルートフォース検索よりも良いことはできません（トラバースP1はP2の一致するルートを探し、両方がトラバースしてノードが実際に一致するサブツリーのルートであるかどうかを判断し、一致しない場合は元のトラバーサルを続行します。この検索はO（n * m）で動作します。nはP1のサイズで、mはP2のサイズです。使用可能なツリーデータに応じた深さチェックおよびその他の潜在的な最適化により、この男は少し最適化されますが、一般的にはまだO（n * m）です。特定の状況によっては、これが唯一の合理的なアプローチかもしれません。

メモリ/ストレージの制約がなく、少し複雑でも構わない場合は、最長の共通部分文字列の問題一般化されたサフィックスツリー。同様の問題に関するこれに関するいくつかの議論はこちら。時間があれば、戻って実装の詳細を編集するかもしれません。
	


	
		
	
	
			両方のツリーのルートが指定され、ノードが同じタイプである場合、T2のルートがT1にあることを確認するだけでは不十分なのはなぜですか？

「ツリーTを指定した」と仮定しています。 Tのルートへのポインタとノードのデータ型を指定することを意味します。

よろしく。
	


	
		
	
	
			私の考えが正しいかどうかはわかりません。それにもかかわらず、あなたの永続的な。 


ツリー1でポストオーダーウォークを実施＆amp;ツリー2、P1およびP2と呼びます。
 P1と＆amp;を比較P2。それらが異なる場合。ツリーはサブツリーではありません。終了します。
同じ場合、またはP1がP2に含まれる場合。どのサブツリーを決定できます。
	


	
		
	
	
			私たちは総当たりで行く必要があると思いますが、なぜT1でT2のルートを見つけた後にツリーを一致させる必要があるのでしょうか。
ツリーが同一であるかどうかを確認する必要がない場合とは異なります（その後、ツリー全体を比較する必要があるだけです）。

値ではなく、ツリーT1およびT2のポインターが与えられます。

ノードT2（ポインター）がT1ツリーに存在する場合。 

ツリーT2はT1のサブツリーです。



編集：

 T2は実際にはオブジェクトごとに異なるツリーであると言われ、T1にサブツリーがあるかどうかを調べる必要があります。これはT2と同じです

これは機能しません。

そして、ここですでに説明した解決策に進む以外の選択肢はありません。 
	


	
		
	
	
			 T1を親ツリーとし、T2をT1のサブツリーとなるツリーとして考えてみましょう。以下をせよ。 T1およびT2は、バランス係数のない2進ツリーであると仮定しています。

 1）T1でT2のルートを検索します。見つからない場合、T2はサブツリーではありません。 BTで要素を検索するにはO（n）時間かかります。

 2）要素が見つかった場合、T2のノードルート要素からのT1の事前順序走査を行います。これにはo（n）時間かかります。 T2の先行予約走査も行います。 O（n）時間かかります。事前注文トラバーサルの結果はスタックに保存できます。スタックへの挿入にはO（1）のみが必要です。

 3）2つのスタックのサイズが等しくない場合、T2はサブツリーではありません。

 4）各スタックから1つの要素をポップし、等しいかどうかを確認します。不一致が発生した場合、T2はサブツリーではありません。

 5）T2に一致したすべての要素がサブツリーの場合。
	


	
		
	
	
			ツリーは不変ツリーであると想定しているため、サブツリーを変更することはありません（Schemeの用語では set-car！を実行しません）。葉または既存の木から新しい木を構築します。

次に、そのノードのすべてのノードを保持（またはサブツリー）ハッシュコードすることをお勧めします。 Cの用語では、tree-sを次のように宣言します

 struct tree_st {
   const unsigned hash;
   const bool isleaf;
   union {
     const char*leafstring; // when isleaf is true
     struct { // when isleaf is false
        const struct tree_st* left;
        const struct tree_st* right;
     };
   };
 };


次に、構築時にハッシュを計算し、ノードが等しいかどうかを最初に比較するときに、ハッシュが等しいかどうかを比較します。ほとんどの場合、ハッシュコードは異なります（コンテンツを比較する手間もかかりません）。

可能なリーフ構築関数は次のとおりです。

struct tree_st* make_leaf (const char*string) {
   assert (string != NULL);
   struct tree_st* t = malloc(sizeof(struct tree_st));
   if (!t) { perror("malloc"); exit(EXIT_FAILURE); };
   t->hash = hash_of_string(string);
   t->isleaf = true;
   t->leafstring = string;
   return t;
}


ハッシュコードを計算する関数は

unsigned tree_hash(const struct tree_st *t) {
  return (t==NULL)?0:t->hash;
}


 2つのサブツリーからノードを構築する関数 sleft ＆amp;  sright は

struct tree_st*make_node (const struct tree_st* sleft,
                          const struct tree_st* sright) {
   struct tree_st* t = malloc(sizeof(struct tree_st));
   if (!t) { perror("malloc"); exit(EXIT_FAILURE); };
   /// some hashing composition, e.g.
   unsigned h = (tree_hash(sleft)*313) ^ (tree_hash(sright)*617);
   t->hash = h;
   t->left = sleft;
   t->right = sright;
   return t;
 }


（2つのツリー tx ＆amp;  ty の）比較関数は、ハッシュコードが異なる場合に被比較数が異なることを利用します

bool equal_tree (const struct tree_st* tx, const struct tree_st* ty) {
  if (tx==ty) return true;
  if (tree_hash(tx) != tree_hash(ty)) return false;
  if (!tx || !ty) return false;
  if (tx->isleaf != ty->isleaf) return false;
  if (tx->isleaf) return !strcmp(tx->leafstring, ty->leafstring);
  else return equal_tree(tx->left, ty->left) 
              && equal_tree(tx->right, ty->right); 


} 

ほとんどの場合、 tree_hash（tx）！= tree_hash（ty）テストは成功し、再帰する必要はありません。

 ハッシュ処理について読んでください。

このような効率的なハッシュベースの equal_tree 関数を作成したら、他の回答（またはハンドブック）に記載されている手法を使用できます。
	


	
		
	
	
			簡単な方法の1つは、ツリーにis_equal（）メソッドを記述し、次のことを行うことです

bool contains_subtree(TNode*other) {
    // optimization
    if(nchildren < other->nchildren) return false;
    if(height < other->height) return false;

    // go for real check
    return is_equal(other) || (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other));
}


ツリーのハッシュコードを使用してis_equal（）を最適化できることに注意してください。ツリーの高さ、子の数、または値の範囲をハッシュコードとして取得することにより、簡単な方法で実行できます。 

bool is_equal(TNode*other) {
    if(x != other->x) return false;
    if(height != other->height) return false;
    if(nchildren != other->nchildren) return false;
    if(hashcode() != other->hashcode()) return false;
    // do other checking for example check if the children are equal ..
}


ツリーがリンクリストに似ている場合、O（n）時間かかります。比較する子を選択するときに、ヒューリスティックを使用することもできます。

bool contains_subtree(TNode*other) {
    // optimization
    if(nchildren < other->nchildren) return false;
    if(height < other->height) return false;

    // go for real check
    if(is_equal(other)) return true;
    if(left == NULL || right == NULL) {
          return (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other));
    }
    if(left->nchildren < right->nchildren) { // find in smaller child tree first
          return (left->contains_subtree(other)) || right->contains_subtree(other);
    } else {
          return (right->contains_subtree(other)) || left->contains_subtree(other);
    }
}


別の方法は、両方のツリーを文字列としてシリアル化し、2番目の文字列（T2から直列化）が最初の文字列（T1から直列化）のサブ文字列であるかどうかを調べることです。 

次のコードは予約注文でシリアル化されます。

   void serialize(ostream&strm) {
            strm << x << '(';
            if(left)
                    left->serialize(strm);
            strm << ',';
            if(right)
                    right->serialize(strm);
            strm << ')';
    }


また、たとえば Knuth＆＃8211; Morris＆＃8211; Prattアルゴリズムを使用して（おそらくO（n）時間で）部分文字列の存在を確認し、最終的にツリーがotherのサブツリーであるかどうかを確認します。 

再び、Burrows＆＃8211; Wheeler_transformを使用して文字列を効率的に圧縮できます。また、 bzgrep で圧縮データのサブストリングを検索することもできます。

別の方法は、ツリーのサブツリーを子の高さと数でソートすることです。 

bool compare(TNode*other) {
    if(height != other->height)
        return height < other->height;

    return nchildren < other->nchildren;
}


 O（n ^ 2）サブツリーがあることに注意してください。数を減らすために、高さに基づいた範囲を使用できます。たとえば、高さ1000〜1500のサブツリーのみに関心があります。

ソートされたデータが生成されると、バイナリ検索を実行し、O（lg n）時間のサブセットであるかどうかを調べることができます（ソートされたデータに重複がないことを考慮）。



	
		
			ライセンス： CC-BY-SA と 帰属
			所属していません StackOverflow