27

BST のプロパティを維持する 2 つのバイナリ検索ツリーをマージする方法は?

ツリーから各要素を取得して他の要素に挿入することにした場合、このメソッドの複雑さは次のようO(n1 * log(n2))になりn1ます。もう一方のツリー (たとえば)。この操作の後、1 つの BST だけがノードを持ちます。T1n2T2n1 + n2

私の質問は、O(n1 * log(n2)) よりもうまくできるでしょうか?

4

6 に答える 6

28

もう少し詳細なNaaffの答え：

  • BSTをソートされたリストにフラット化するのはO(N)です
    • ツリー全体での「順序どおりの」反復です。
    • 両方でやるとO(n1+n2)
  • 2 つのソート済みリストをマージして 1 つのソート済みリストにするのは O(n1+n2) です。
    • 両方のリストの先頭へのポインターを保持する
    • 小さい方の頭部を選択し、ポインタを進めます
    • これは、マージソートのマージがどのように機能するかです
  • ソートされたリストから完全にバランスの取れた BST を作成するのは O(N) です
    • アルゴリズムについては、以下のコード スニペットを参照してください[1]
    • この場合、ソートされたリストのサイズは n1+n2 です。だから O(n1+n2)
    • 結果のツリーは、リストのバイナリ検索の概念的な BST になります。

O(n1+n2) の 3 つのステップは、O(n1+n2) になります。

同じ桁の n1 と n2 の場合、O(n1 * log(n2)) よりも優れています。

[1] ソートされたリストからバランスの取れた BST を作成するアルゴリズム (Python で):

def create_balanced_search_tree(iterator, n):
    if n == 0:
        return None
    n_left = n//2
    n_right = n - 1 - n_left
    left = create_balanced_search_tree(iterator, n_left)
    node = iterator.next()
    right = create_balanced_search_tree(iterator, n_right)
    return {'left': left, 'node': node, 'right': right}
于 2009-06-18T00:14:33.117 に答える
1

ジョナサン、

ソート後、長さ n1+n2 のリストが得られます。そこから二分木を構築するには、log(n1+n2) 時間かかります。これはマージソートと同じですが、各再帰ステップで、マージソートアルゴリズムのように O(n1+n2) 項がありません。したがって、時間計算量は log(n1+n2) です。

今、問題全体の複雑さは O(n1+n2) です。

また、2 つのリストが同等のサイズである場合、このアプローチは適切であると言えます。サイズが比較できない場合は、小さなツリーのすべてのノードを大きなツリーに挿入することをお勧めします。これには O(n1*log(n2)) 時間がかかります。たとえば、サイズ 10 とサイズ 1024 の 2 つのツリーがあるとします。ここでは n1+n2 = 1034 で、n1log(n2) = 10*10 = 100 です。したがって、アプローチは 2 つのツリーのサイズに依存する必要があります。

于 2010-07-27T21:08:19.630 に答える
0

O(n1 * log(n2)) は、ソートされていないリストを 2 つ BST にマージしたとしても、平均的なシナリオです。リストがソートされたリストまたは BST であるという事実を利用していません。

私によると、1つのBSTにn1要素があり、他のBSTにn2要素があると仮定しましょう。ここで、1 つの BST を O(n1) のソート済み配列リスト L1 に変換します。

マージされた BST(BST、配列)

if (Array.size == 0) return BST if(Array.size ==1) BST に要素を挿入します。BSTを返します。

左の要素が < BST.rootnode で右の要素が >=BST.rootnode である配列のインデックスを見つけます。if(BST.rootNode.leftNode ==null ) //ie 左ノードなし { Index から 0 までのすべての配列を BST の左に挿入し、 } else { Merged BST(BST.leftNode, Array{0 to Index}) }

if(BST.rootNode.rightNode ==null)//ie 右ノードなし { Index から Array.size までのすべての配列を BST の右に挿入する } else { Merged BST(BST.rightNode, Array{Index to Array.size} ) }

BSTを返します。

このアルゴリズムは、サブ問題を処理するために配列と BST を分割するたびに O(n1 * log(n2)) よりも << 時間がかかります。

于 2010-08-30T10:12:43.920 に答える
-1

アイデアは、反復的な順序トラバーサルを使用することです。2つのBSTに2つの補助スタックを使用します。要素をソートされた形式で印刷する必要があるため、いずれかのツリーから小さな要素を取得するたびに、それを印刷します。要素が大きい場合は、次の反復のためにスタックにプッシュバックします。

于 2013-01-08T06:04:48.700 に答える