20

与えられた 2 つのバイナリ ツリーの構造と内容が等しいかどうかを調べる効率的なアルゴリズムは何でしょうか?

4

7 に答える 7

24

これは小さな問題ですが、以前の解決策を次のように適応させます...

eq(t1, t2) =
  t1.data=t2.data && eq(t1.left, t2.left) && eq(t1.right, t2.right)

その理由は、不一致が一般的である可能性が高く、さらに再発する前に、早期に検出（および比較を停止）することをお勧めします。もちろん、ここでは短絡&&演算子を想定しています。

また、これは、構造的に異なるツリーを正しく処理し、再帰を終了する際のいくつかの問題を覆い隠していることも指摘しておきます。基本的に、t1.leftなどのnullチェックが必要です。一方のツリーにnull .leftがあり、もう一方にはない場合、構造上の違いが見つかります。両方にnull.leftがある場合、違いはありませんが、リーフに到達しています。これ以上繰り返さないでください。両方の.left値がnull以外の場合にのみ、サブツリーをチェックするために再帰します。もちろん、同じことが.rightにも当てはまります。

たとえば（t1.left == t2.left）のチェックを含めることができますが、これは、サブツリーが2つのツリーで物理的に共有できる（同じデータ構造ノード）場合にのみ意味があります。このチェックは、不要な場所での繰り返しを回避するもう1つの方法です。t1.leftとt2.leftが同じ物理ノードである場合、これらのサブツリー全体が同一であることはすでにわかっています。

ACの実装は...

bool tree_compare (const node* t1, const node* t2)
{
  // Same node check - also handles both NULL case
  if (t1 == t2)  return true;

  // Gone past leaf on one side check
  if ((t1 == NULL) || (t2 == NULL))  return false;

  // Do data checks and recursion of tree
  return ((t1->data == t2->data) && tree_compare (t1->left,  t2->left )
                                 && tree_compare (t1->right, t2->right));
}

コメントに応じて編集...

これを使用した完全なツリー比較の実行時間は、最も簡単にO（n）として記述されます。ここで、nはツリーのサイズです。より複雑な境界を受け入れる場合は、O（minimum（n1、n2））などの小さい境界を取得できます。ここで、n1とn2はツリーのサイズです。

基本的に、再帰呼び出しは、左側のツリーの各ノードに対して（最大で）1回だけ行われ、右側のツリーの各ノードに対して（最大で）1回だけ行われるという説明です。関数自体（再帰を除く）は最大で一定量の作業のみを指定するため（ループはありません）、すべての再帰呼び出しを含む作業は、小さいツリーのサイズにその定数を掛けたものになります。

さらに分析して、木の交差点のアイデアを使用して、より複雑であるがより小さな境界を取得することもできますが、大きなOは上限を与えるだけであり、必ずしも可能な限り低い上限ではありません。これをコンポーネントとして使用してより大きなアルゴリズム/データ構造を構築しようとしているのでない限り、その分析を行う価値はおそらくありません。その結果、一部のプロパティが常にこれらのツリーに適用され、より厳密な境界が可能になることがわかっています。より大きなアルゴリズム。

ティガーバウンドを形成する1つの方法は、両方のツリーのノードへのパスのセットを検討することです。各ステップは、L（左のサブツリー）またはR（右のサブツリー）のいずれかです。したがって、ルートは空のパスで指定されます。ルートの左の子の右の子は「LR」です。関数「パス（T）」（数学的にはプログラムの一部ではない）を定義して、ツリーへの有効なパスのセットを表します。ノードごとに1つのパスです。

だから私たちは持っているかもしれません...

paths(t1) = { "", "L", "LR", "R", "RL" }
paths(t2) = { "", "L", "LL", "R", "RR" }

同じパス仕様が両方のツリーに適用されます。また、各再帰は、両方のツリーで常に同じ左/右リンクをたどります。したがって、再帰はこれらのセットの反復セクションのパスにアクセスします。これを使用して指定できる最も厳しい境界は、その交差のカーディナリティです（再帰呼び出しごとの作業には一定の境界があります）。

上記のツリー構造では、次のパスに対して再帰を実行します...

paths(t1) intersection paths(t2) = { "", "L", "R" }

したがって、この場合の作業は、tree_compare関数での非再帰的作業の最大コストの最大3倍に制限されます。

これは通常、不必要な詳細ですが、パスセットの共通部分は、最大でも最小の元のツリーのノード数と同じくらい大きいことは明らかです。そして、O（n）のnが、1つの元のツリーのノードの数を指している場合でも、両方のノードの合計を指している場合でも、これは明らかに最小値または交差点のいずれかよりも小さくありません。したがって、O（n）はそれほど厳密な境界ではありませんが、話しているサイズが少しあいまいであっても、有効な上限です。

于 2009-09-28T13:46:18.463 に答える
4

モジュロスタックオーバーフロー、

eq(t1, t2) =
    eq(t1.left, t2.left) && t1.data=t2.data && eq(t1.right, t2.right)

（これは、すべてのツリー構造化代数データ型の等式述語に一般化されます。構造化データの任意の部分について、そのサブパートのそれぞれが他のサブパートのそれぞれと等しいかどうかを確認してください。）

于 2009-09-27T05:23:57.950 に答える
3

また、2つのトラバーサル（プレオーダー、ポストオーダー、またはインオーダー）のいずれかを実行して、両方のツリーの結果を比較することもできます。それらが同じである場合、それらが同等であると確信できます。

于 2012-08-31T05:45:19.030 に答える
1

おそらく達成しようとしていることのより一般的な用語は、グラフ同型です。そのページでこれを行うためのいくつかのアルゴリズムがあります。

于 2009-09-27T05:07:41.083 に答える
1

証明された事実であるため、次の条件が満たされている限り、バイナリ ツリーを再作成できます。

  1. In-Order Traversal で検出される一連のノード。
  2. Pre-Order または Post-Order トラバーサルで検出される一連のノード

2 つのバイナリ ツリーが同じ順序および [前順または後順] のシーケンスを持つ場合、それらは構造的にも値に関しても等しくなければなりません。

各走査は O(n) 操作です。走査は合計 4 回行われ、同じタイプの走査の結果が比較されます。O(n) * 4 + 2 => O(n) したがって、時間の複雑さの合計次数は O(n) になります。

于 2013-09-17T22:48:26.373 に答える
0

私はそれを次のように書きます。次のコードは、ほとんどの関数型言語で機能します。データ型がハッシュ可能である場合（たとえば、辞書やリストではない場合）、Pythonでも機能します。

  • トポロジー的同等性（構造は同じ、つまりTree(1,Tree(2,3))==Tree(Tree(2,3),1)）：

    tree1==tree2意味set(tree1.children)==set(tree2.children)

  • 順序付けられた平等：

    tree1==tree2意味tree1.children==tree2.children

（Tree.childrenは子の順序付きリストです）

基本ケース（リーフ）はすでに等式が定義されているため、処理する必要はありません。

于 2011-10-12T01:32:52.847 に答える
0 
bool identical(node* root1,node* root2){
    if(root1 == NULL && root2 == NULL)
        return true;
    if(root1==NULL && root2!=NULL || root1!=NULL && root2 == NULL)
        return false;
    if(root1->data == root2->data){
        bool lIdetical = identical(root1->left,root2->left);
        if(!lIdentical)
            return false;
        bool rIdentical = identical(root1->right,root2->identical);
        return lIdentical && rIdentical;
    }
    else{
        printf("data1:%d vs data2:%d",root1->data,root2->data);
        return false;
    }
}

これが最も効率的かどうかはわかりませんが、これでうまくいくと思います。

于 2020-12-01T06:19:58.930 に答える