2

2 つのツリーは、同じ要素セットを含むが構造が異なる場合、同一であると言われます。例: 4,3,5 および 5,4,3

2 つのツリーが同一かどうかを確認する方法は?

私が考えることができる1つのアプローチは、ハッシュを使用することです。最初のツリーの要素ごとに、対応するカウントがインクリメントされます。2 番目のツリーの要素ごとに、カウントが減少します。最後に、ハッシュは空です。ツリーが同一であると確信しています。時間の複雑さ: O(N) 空間の複雑さ: O(N)

ただし、このアプローチでは、ツリーが BST であるか単純な BINARY TREE であるかは使用されません。

アプローチ 2: 配列内の両方のツリーを順番にトラバーサルします。ソートされたデータを持つ2つの配列があります。線形検索を実行して、配列が同一であるかどうかを確認します。時間の複雑さ: O(N) 空間の複雑さ: O(N)

しかし、より良い解決策が存在することを知りたかったのですか？

4

3 に答える 3

6

これは、同じ構造と要素という意味でのツリーの同一性の後である、元の言い回しの質問に答えます。

インオーダー (またはその他の) シーケンシャル化の比較は機能しません。異なるツリーは同じトラバーサルを持ちます。たとえば、木々

ここに画像の説明を入力
[ソース]

同じ in-order traversal を持っていますa,b,c,d,e。2 つの(異なる) トラバーサルを使用して、それらが同じかどうかをそれぞれ確認できます。

ただし、古典的な解決策は再帰アルゴリズムです。

  equal Leaf(x)       Leaf(y)       => x == y
| equal Node(x,l1,r1) Node(y,l2,r2) => x == y && equal(l1,l2) && equal(r1,r2)
| equal _             _             => false;

両方のツリーでツリー トラバーサルを同時に実行し、時間 Θ(n) (n はそれぞれのノード数の最大値) を要します。

更新された質問に関しては、要素ごとの同等性について順序通りのトラバーサルをチェックするだけで十分です。定義上、BST の順序通りのトラバーサルは格納された要素の並べ替えられたリストであるため、このアプローチは正しいことに注意してください。再帰的な形式では、これはアルゴリズムです:

  inorder Leaf(x)     = [x]
| inorder Node(x,l,r) = (inorder l) ++ [x] ++ (inorder r);

  equal []     []     = true
| equal x1::r1 x2::r2 = x1 == x2 && (equal r1 r2)
| equal _      _      = false;

  sameElems t1 t2 = let 
                      e1 = inorder t1
                      e2 = inorder t2
                    in
                      equal e1 e2
                    end;

リストの連結が時間 O(1) で実行できる場合、これは時間 Θ(n) および空間 Θ(n) で実行されます。反復ソリューションは確かに優れており、おそらくより良い定数を持っています。

このチェックを o(n) 時間で実行したい場合、すべての要素を調べることさえできません。一般に、両方のツリーにはペアごとに異なる要素が含まれているため、範囲を利用することはできません。したがって、すべての一般的な要素の等価性チェックには Ω(n) の時間がかかります (より高速なアルゴリズムを想定し、失敗する 2 つのツリーを構築します)。

ただし、スペースは O(n) よりもうまく処理できます。巧妙に順番に実装する場合¹、必要な追加スペースは O(1) だけです (現在の要素へのポインター、いくつかの管理カウンター/フラグ)。

  1. このアルゴリズムはツリーを一時的に破棄するため、同時設定には適していないことに注意してください。
于 2012-06-08T20:00:07.917 に答える
1

ハッシュの問題は、2つのバイナリ検索ツリーが{2, 1, 3}あり{0, 0, 6}、それらが同じ合計ハッシュコードを持つ可能性があり、それでも異なる要素がある場合です。

インオーダートラバーサル法はおそらく最も効率的な方法であり、平等の比較を行う必要があることをO(n)考えると、これまでで最高の方法であると私は考えています。n

于 2012-06-08T15:50:15.387 に答える
1

後者の最悪の場合の時間は O(N) ですが、最良の場合 (順序通りのトラバーサルの最初の要素が異なる場合) は Ω(1) になるため、後者の解決策は前者よりも優れているようです。前者のベストケースの時間は、確実に知るために最後まで待たなければならないため、Ω(N) のままです。

ただし、後者の最適化として、すべてのデータのコピーを作成するのではなく、各ツリーの現在の要素へのポインターを使用することはできませんか? ツリーの順序通りのトラバーサル (少なくとも自然順序付け) のアルゴリズムでは、データのコピーを作成する必要はありません。そうすれば、スペースの複雑さは O(1) になります。

于 2012-06-08T15:52:30.433 に答える