8

一連の値が与えられると、それらの値から形成できるさまざまな二分探索木が存在する可能性があります。たとえば、値 1、2、および 3 の場合、これらの値から作成できる 5 つの BST があります。

1      1      2      3      3
 \      \    / \    /      /
  2      3  1   3  1      2
   \    /           \    /
    3  2             2  1

バランスの取れた二分探索木に基づく多くのデータ構造は、必要な二分探索木の不変条件を壊すことなく BST を再形成するためのプリミティブとしてツリーの回転を使用します。次に示すように、ツリーの回転を使用して、ノードをその親の上に引き上げることができます。

                rotate
         u      right           v
        / \     ----->         / \
       v   C                  A   u
      / \       <-----           / \
     A   B      rotate          B   C
                 left

値のセットを含む BST が与えられた場合、その BST を同じ値のセットの任意の他の BST に変換することは常に可能ですか? たとえば、ツリーの回転を使用するだけで、上記の 5 つの BST のいずれかを他の BST のいずれかに変換できますか?

4

2 に答える 2

20

あなたの質問に対する答えは、BST で互いに異なるように見える等しい値を持つことが許可されているかどうかによって異なります。たとえば、BST がキーと値のペアを格納している場合、それらのキーと値のペアの 1 つの BST を、同じキーと値のペアの別の BST に変換できるとは限りません。

この理由は、実行されるツリーのローテーションの数に関係なく、BST 内のノードの順序どおりのトラバーサルが同じままであるためです。その結果、ノードの順不同のトラバーサルが異なる結果になる場合、ある BST から別の BST に変換することはできません。非常に単純なケースとして、数値 1 の 2 つのコピーを保持する BST があり、それぞれに異なる値 (A または B など) の注釈が付けられているとします。その場合、ツリーの回転を使用してこれら 2 つのツリーを相互に変換する方法はありません。

       1:a            1:b
         \             \
         1:b           1:a

これは、回転で作成できる一連の (非常に小さい!) 可能性のあるツリーをブルート フォースすることで確認できます。ただし、最初のツリーを順不同にトラバースすると 1:a, 1:b が得られ、2 番目のツリーを順不同にトラバーサルすると 1:b, 1:a が得られることに注意してください。したがって、ツリー間の変換に十分な回転数はありません。

一方、すべての値が異なる場合は、適切な数のツリー ローテーションを適用することで、2 つの BST 間で変換することが常に可能です。ノード数の帰納的引数を使用してこれを証明します。

単純な基本ケースとして、ツリーにノードがない場合、それらのノードを保持する可能性のある BST は 1 つだけです: 空のツリーです。したがって、開始ツリーと終了ツリーは常に同じでなければならないため、ノードがゼロの 2 つのツリー間で変換することは常に可能です。

誘導ステップでは、同じ値を持つ 0、1、2、..、n ノードの任意の 2 つの BST について、回転を使用して 1 つの BST から別の BST に常に変換できると仮定します。同じ n + 1 の値から作成された任意の 2 つの BST が与えられた場合、最初のツリーを 2 番目のツリーに常に変換できることを証明します。

これを行うには、重要な観察を行うことから始めます。BST 内の任意のノードが与えられた場合、ツリーの回転を適用して、そのノードをツリーのルートに引き上げることが常に可能です。これを行うには、次のアルゴリズムを適用できます。

while (target node is not the root) {
    if (node is a left child) {
        apply a right rotation to the node and its parent;
    } else {
        apply a left rotation to the node and its parent;
    }
}

これが機能する理由は、ノードが親とともに回転されるたびに、その高さが 1 ずつ増加するためです。その結果、上記のフォームの十分な数のローテーションを適用した後、ツリーの最上部までルートを取得できます。

これにより、回転を使用して任意の BST を別の BST に再形成するために使用できる非常に単純な再帰アルゴリズムが得られます。考え方は以下の通りです。まず、2 番目のツリーのルート ノードを確認します。最初のツリーでそのノードを見つけ (これは BST であるため、これは非常に簡単です!)、上記のアルゴリズムを使用してツリーのルートにプルアップします。この時点で、最初のツリーを次のプロパティを持つツリーに変更しました。

  1. 最初のツリーのルート ノードは、2 番目のツリーのルート ノードです。
  2. 最初のツリーの右側のサブツリーには、2 番目のツリーの右側のサブツリーと同じノードが含まれていますが、形状が異なる場合があります。
  3. 最初のツリーの左側のサブツリーには、2 番目のツリーの左側のサブツリーと同じノードが含まれますが、形状が異なる可能性があります。

したがって、この同じアルゴリズムを再帰的に適用して、左のサブツリーを 2 番目のツリーの左のサブツリーと同じ形状にし、右のサブツリーを 2 番目のツリーの右のサブツリーと同じ形状にすることができます。これらの左と右のサブツリーは、厳密にはそれぞれ n 個のノードしか持たない必要があるため、帰納的仮説により、常にこれを行うことが可能であることがわかり、アルゴリズムは意図したとおりに機能します。

要約すると、アルゴリズムは次のように機能します。

  1. 2 つのツリーが空であれば、完了です。
  2. 最初のツリーで 2 番目のツリーのルート ノードを見つけます。
  3. 回転を適用して、そのノードをルートまで持ち上げます。
  4. 最初のツリーの左側のサブツリーを再帰的に再形成して、2 番目のツリーの左側のサブツリーと同じ形状にします。
  5. 最初のツリーの右側のサブツリーを再帰的に再形成して、2 番目のツリーの右側のサブツリーと同じ形状にします。

このアルゴリズムの実行時間を分析するには、ステップ 1 から 3 を適用するには最大で O(h) ステップが必要であることに注意してください。ここで、h は最初のツリーの高さです。すべてのノードは、あるサブツリーのルートに 1 回だけ到達するため、これを合計 O(n) 回行います。n ノード ツリーの高さが O(n) を超えることはないため、これは、アルゴリズムが完了するまでに最大で O(n 2 ) の時間がかかることを意味します。はるかにうまくいく可能性があります (たとえば、2 つのツリーが既に同じ形状を持っている場合、これは時間 O(n) で実行されます) が、これは最悪の場合の境界を与えます。

お役に立てれば！

于 2012-12-25T04:37:17.997 に答える