10

整数の配列を指定しますarr = [5, 6, 1]。この入力を同じ順序で使用して BST を構築すると、「5」がルート、「6」が右の子、「1」が左の子になります。

入力を [5,1,6] に変更しても、BST 構造は同じままです。

整数の配列が与えられた場合、元の配列順序で形成された BST と同じ BST になる入力配列の異なる順列の数を見つける方法は?

4

4 に答える 4

13

あなたの質問は、特定の BST のトポロジー順序の数を数える質問と同じです。

たとえば、BST の場合

  10
 /  \
5   20
 \7 | \
    15 30

一連のトポロジー順序付けは、次のように手動で数えることができます: 順序付けごとに 10 開始します。20 で始まるサブツリーのトポロジー順序の数は、(20, 15, 30) と (20, 30, 15) の 2 つです。5 で始まるサブツリーの順序は (5, 7) の 1 つだけです。これらの 2 つのシーケンスは任意の方法でインターリーブすることができ、2 x 10 のインターリーブにつながり、同じ BST を生成する 20 の入力を生成します。最初の 10 は、ケース (20、15、30) について以下に列挙されています。

 10 5 7 20 15 30
 10 5 20 7 15 30
 10 5 20 15 7 30
 10 5 20 15 30 7
 10 20 5 7 15 30
 10 20 5 15 7 30
 10 20 5 15 30 7
 10 20 15 5 7 30
 10 20 15 5 30 7
 10 20 15 30 5 7

(20、30、15) の場合も同様です --- 次の入力のいずれかが同じ BST を生成することを確認できます。

この例では、順序数を計算するための再帰規則も提供します。リーフの場合、この数は 1 です。1 つの子を持つ非リーフ ノードの場合、この数は子のトポロジー順序の数に等しくなります。サブツリー サイズ |L| を持つ 2 つの子を持つ非リーフ ノードの場合 および |R| で、どちらも l 順序と r 順序があり、それぞれの数は次のようになります。

  l x r x INT(|L|, |R|)

ここで、INT は |L| の可能なインターリーブの数です。と |R| 要素。これは (|L| + |R|) で簡単に計算できます! / (|L|! x |R|!)。上記の例では、次の再帰計算が得られます。

  Ord(15) = 1
  Ord(30) = 1
  Ord(20) = 1 x 1 x INT(1, 1) = 2  ; INT(1, 1) = 2! / 1 = 2
  Ord(7) = 1
  Ord(5) = 1
  Ord(10) = 1 x 2 x INT(2, 3) = 2 x 5! / (2! x 3!) = 2 x 120 / 12 = 2 x 10 = 20

これで問題は解決します。

注: このソリューションは、BST 内のすべてのノードが異なるキーを持っていることを前提としています。

于 2009-11-10T17:34:48.860 に答える
1

説明してくれてありがとうantti.huima! これは私が理解するのを助けました。ここにいくつかのC++があります：

#include <vector>
#include <iostream>

using namespace std;

int factorial(int x) {
  return (x <= 1) ? 1 : x * factorial(x - 1);
}

int f(int a, int b) {
  return factorial(a + b) / (factorial(a) * factorial(b));
}

template <typename T>
int n(vector<T>& P) {
  if (P.size() <= 1) return 1;
  vector<T> L, R;
  for (int i = 1; i < P.size(); i++) {
    if (P[i] < P[0])
      L.push_back(P[i]);
    else
      R.push_back(P[i]);
  }
  return n(L) * n(R) * f(L.size(), R.size());
}

int main(int argc, char *argv[]) {
  vector<int> a = { 10, 5, 7, 20, 15, 30 };
  cout << n(a) << endl;
  return 0;
}
于 2013-03-06T02:59:58.710 に答える
-1

これを逆方向に行うことができます。BSTが与えられた場合、このBSTを生成する可能性のある整数のすべての配列を列挙します。

できませんでした（非決定性を使用して...）

  1. ルートを放出し、放出されたセットに追加します。
  2. 放出されたセットにはないが、親が存在するツリーから非決定論的にアイテムを選択し、放出されたセットに追加して放出します。
  3. すべてが放出されるまで2を繰り返します。

非決定性はあなたにそのようなすべての配列を与えるでしょう。次に、それらを数えることができます。

于 2009-11-09T15:15:56.107 に答える