9

それぞれサイズ N の 2 つのソートされていない配列が与えられた場合、それらから構築された二分探索木が等しいかどうかを判断します。

したがって、配列の要素が選択され、基本的な (バランシングなし、赤黒なし、何もない) 二分探索ツリーに挿入されます。直接 2 つの配列が与えられた場合、それらが同じ二分探索木を生成するかどうかを判断できますか。

明らかな O(N 2 ) の最悪の場合の時間の複雑さの解決策があります。2 つのツリーを構築し、それらの等価性を比較します。

これに対する O(N) または O(N log N) ソリューションはありますか?

私が抽出しようとしている問題のアイデアは次のとおりです。BST の構築は、要素の相対位置に依存します。たとえば、一方の配列の 20 のすぐ隣に値 51 の要素がある場合、ツリーが等しくなるためには、もう一方の配列に 20 と 51 の間に要素があってはなりません (そうでない場合、20 の右の子は 51 ではなくその数になります)。 ）。

私はいくつかのアプローチを試しました：

  1. 単純なアプローチ: 2 つのツリーを作成して比較します。
  2. 配列を 2 つ (1 つの小さいサブ配列とピボットよりも大きい 1 つのサブ配列) に分割し、左の配列を左の子に再帰的に渡し、もう 1 つを右の子に渡す興味深い変形を使用しました。インプレースで生意気ですが、それでも O(N 2 ) です。
  3. 友人は、最長のサブシーケンスをそれに適用して見つけて比較しようとしましたが、それは正しくありません。
  4. おそらくLinkedHashMapで解決しようとしていましたが、その正しさを証明するのに苦労しています。

ヘルプ、およびこの問題を解決するためのヒントをいただければ幸いです。

4

4 に答える 4

1

概要

範囲最小クエリを使用して二分木を構築することで、単純なアプローチを O(N^2) から O(NlogN) に改善できると思います。

高速二分木構築

配列 A の二分木を構築したいとします。

アイデアは、最初に配列 B を構築することです。ここで、B[i] は A の i 番目に大きい要素の位置です。これは、O(NlogN) でソートすることによって実行できます。

次に、配列 B に対して範囲最小クエリを使用して、特定の範囲 a<=i<=b の B[i] の最小値を見つけることができます。言い換えると、これにより、a の最初の位置を見つけることができます。ここで、値は th と b 番目に大きい要素の間の範囲にあります。

RMQ は前処理に O(N) の時間がかかり、クエリは O(1) の時間で回答できます。

次に、各要素の左と右の子 (存在する場合) を再帰的に見つけて、それらが一致することを確認できます。

疑似コード

2 つの配列が A と A2 であると仮定します。簡単にするために、i 番目に大きい要素が i に等しくなるように A、A2 が前処理されていると仮定します。

find_children(1,N) が True の場合、ツリーは同一です。

find_children(low,high)
   if high==low
      return True
   node = A[RMQ(low,high)]
   return node == A2[RMQ2(low,high)]
          and find_children(low,node-1)
          and find_children(node+1,high)

この関数は、ツリー内のノード (および空の子ポインター) ごとに 1 回呼び出されるため、O(N) の時間がかかります。

全体として、前処理のソートに O(NlogN) かかるため、これは O(NlogN) です。

説明

要素 20 と 51 を二分木に入力したとします。20 がルートで、51 が右の子になります。51 の左側の子を見つけるには、20 より大きく 51 より小さい値を持つ配列内の最初の要素を見つける必要があります。この値は、範囲 20+1->51- に適用される範囲最小クエリによって与えられます。 1.

したがって、すべてのノードの左右の子を自然な方法で二分木に挿入するよりも高速に見つけることができます (理論上の最悪の場合にのみ高速になります。典型的な例では、他の方法の方が高速である可能性があります)。

于 2012-12-30T20:47:10.680 に答える
1

「2 つのツリーを構築して比較する」は O(N^2) である必要はありません。O(N) ではなく O(log N) で新しいノードの位置を見つけることができる補助データ構造を使用できるため、BST が構築されている場合でも、BST の構築は O(N log N) になります。バランスが取れていません。

BST 内の各空の位置 (つまり、ノードpos内の空き子スロット) には、関連付けられた間隔(a_pos,b_pos)(値の 1 つが +/- 無限大である可能性があります) があり、値の新しいノードが次の場合にのみv作成されます。pos値は間隔にあります。

間隔をバランスの取れた間隔ツリーに格納できるため、新しく到着する各値の位置を O(log N) で見つけることができます。インターバル ツリーの更新も、1 つのインターバルを 2 つに置き換えるだけなので、O(log N) です。

(実際には、間隔がオーバーラップすることはないため、補助構造は間隔ツリーではなく、単純な古い (バランスの取れた) BST にすることができます。)

例：

配列プレフィックス [1,10,2,9,3, ...] 用に構築された、次の非平衡 BST を使用します。

  1
 /  \
a  10
   / \
  2   f
 / \
b   9
   / \
  3   e
 / \
c   d

文字a-fは、新しいノードを配置できる場所 (nil リーフ) を示します。各文字には、次のように間隔が関連付けられています。

[-inf,1] -> a
[1,2] -> b
[2,3] -> c
[3,9] -> d
[9,10] -> e
[10, +inf] -> f

値の新しいノードは、属するv間隔によって決定される場所で BST に追加されます。vゼロはa、5 などにdなります。重要なアイデアは、この情報をツリーの外に格納することです。

上記のテーブルを (実際のツリー ノードへのリンクを使用して) 効率的に表すことができる場合、新しいノードをツリーに追加するには、O(テーブルへのアクセス) + O(1) かかります。O(1) は、ノードを配置する場所が既にわかっている場合、ノードを非平衡 BST に追加することを表します。5 を追加する場合、1、10、2、9、および 3 と比較する必要はありませんが、代わりにテーブルで検索され、直接 に配置されdます。

新しいノードを配置したら、明らかにテーブルも更新する必要があります。テーブルを表すデータ構造は、インターバル ツリー ( http://en.wikipedia.org/wiki/Interval_tree ) である可能性があります。

于 2012-12-30T22:18:38.563 に答える