22

この以前の質問では、値 1 ～ 7 を二分探索木に挿入して、次のような木になる方法がいくつあるかを尋ねました。

       4
     /   \
    2     6
   / \   / \
  1   3 5   7

（ちなみに、答えは80です）。

より一般的に、いくつかの値のセットを保持する任意の BST が与えられ、結果のツリーを生成することになる BST にそれらの値を挿入する方法がいくつあるか知りたいとします。これを決定するための効率的なアルゴリズムはありますか?

ありがとう！

4

2 に答える 2

34

これは、巧妙な再帰アルゴリズムを使用して解決できます。

基本的なケースとして、空のツリーが与えられた場合、そのツリーを構築する方法は 1 つだけです。値を挿入しないでください。

再帰的なケースでは、次のような BST があるとします。

              v
             / \
            L   R

ここで、v はルート、L と R はそれぞれ右部分木です。

この二分探索木を構築したい場合は、最初に v を挿入することから始めなければなりません。そうしないと、v はルートになりません。v を挿入した後、サブツリー L と R を再構築する順序で要素を挿入する必要があります。ここで注意が必要なのは、R を構築する前に L をすべて構築する必要がないことです。L からいくつかの要素を挿入し、次に R からいくつかの要素を挿入し、次に L からさらに要素を挿入し、次に R からさらに要素を挿入することができます。

幸いなことに、私たちができる有益な観察があります。S Lが、BST に挿入された場合に BST L を形成する要素のシーケンスであると仮定します。同様に、S Rを、BST に挿入された場合に BST R を形成する要素のシーケンスとします。シーケンス S Lおよび S Rの場合、v のみを含む BST に挿入すると、ツリーを構築する要素のシーケンスになります。

   v
  / \
 L   R

例として、次のツリーを考えてみましょう。

       4
     /   \
    2     6
   / \   / \
  1   3 5   7

左のサブツリー (1、2、3 を保持) を構築する 1 つの可能なシーケンスは 2、1、3 です。右のサブツリーを構築する 1 つの可能なシーケンスは 6、5、7 です。BST に挿入された場合のこれらのシーケンスの可能なインターリーブルート ノード 4 だけを含むと、上記の BST が構築されます。たとえば、次のシーケンスのいずれかが機能します。

 2, 1, 3, 6, 5, 7
 2, 6, 1, 5, 3, 7
 6, 5, 2, 1, 3, 7
 ...

L と R を構築する任意のシーケンス S Lと S Rが与えられると、それらを任意の順序でインターリーブできるため、v をルートとし、L をルートとするツリーを構築するシーケンスの数を求める適切な式を書き出すことができます。左のサブツリー、およびその右のサブツリーとして R:

# ウェイ = (# S Lと S Rのインターリーブ) × (# 可能な S L ) × (# 可能な S R )

考えてみれば、この積の最後の 2 項は、左右のサブツリーに作用する挿入シーケンスの数を再帰的に見つけることによって見つけることができます。これは、2 つのシーケンスに対して可能なインターリービングの数を割り出すことができれば、上記の式を再帰的に評価することで、特定のツリーを構築する可能な挿入シーケンスの数を決定できることを意味します。

では、インターリーブはいくつありますか? 長さが m と n で重複のない 2 つのシーケンスが与えられた場合、これらのシーケンスのインターリーブの数は次のように計算できます。順序を考える

L L L ... L R R R ... R
  m times     n times

このシーケンスの順列は、一連の L と R を返します。ここで、L の数は長さ m のシーケンスの要素の数に等しく、R の数は長さ n のシーケンスの要素の数に等しくなります。 . このシーケンスは、インターリーブを構築する方法を説明する方法として解釈できます。L が表示されるたびに、左側のシーケンスから要素を挿入し、R が表示されるたびに、右側のシーケンスから要素を挿入します。たとえば、シーケンス 4, 1, 0, 3 および 2, 7 を考えてみましょう。次に、順列 LLRLRL によってシーケンスが得られます。

 4, 1, 2, 0, 3, 7
 L  L  R  L  R  L

m 個の L と n 個の R のシーケンスから始めると、異なる順列の数は次のようになります。

(m + n)!
-------- = (m + n) choose m
 m!  n!

これは (m + n) 個あるから成り立ちます! L と R がすべて異なる場合に、それらを並べ替える可能な方法。そうではないので、すべての注文がカウントされます m! ん！L と R を区別できないように並べ替えることができるため、何度も繰り返します。これについて考える別の方法は、インターリーブでインデックスのセット {1, 2, 3, ..., m + n} を検討し、それらの m を選択して最初のシーケンスの要素で埋め、暗黙的に残りの部分は、正しいシーケンスの要素で構成されています。

わかりました... これで、長さ m と n の 2 つのシーケンスをインターリーブする方法の数を決定する方法が得られました。したがって、次のようになります。

# ウェイ = (# S Lと S Rのインターリーブ) × (# 可能な S L ) × (# 可能な S R )

= ((m + n) n を選択) × (可能な S Lの数) × (可能な S Rの数)

ここで、m は左側のサブツリーの要素数、n は右側のサブツリーの要素数です。わーい！

したがって、このアルゴリズムの擬似コードを書き出すことができます。

function countInsertionOrderings(Tree t) {
    if t is null, return 1;
    otherwise:
       let m = numElementsIn(t.left);
       let n = numElementsIn(t.right);
       return choose(m + n, n) * 
              countInsertionOrderings(t.left) *
              countInsertionOrderings(t.right);
}

このアルゴリズムは、合計 O(n) 回の乗算を実行します。ここで、n はツリー内のノードの数であり、すべてのノードを 1 回だけ訪問します (BST 内の要素の数が各ノードでキャッシュされていると仮定します)。ただし、これは、アルゴリズムが時間 O(n) で実行されることを意味するわけではありません。これらの数値を乗算するために必要な作業は、数値が大きくなるにつれて急速に増加するためです。

お役に立てれば！

于 2013-06-15T00:35:20.263 に答える