4

BST は、セットからのキーの各順列から (ノードの連続挿入によって) 生成されます。

{1、2、3、4、5、6、7、8、9、10、11}。

高さ 3 の木を決定する順列の数は?

4

2 に答える 2

0

チェックしなければならないノードの順列の数は 11 です! = 39,916,800 なので、これを力ずくで実行するプログラムを作成できます。C++ で書かれた 1 つのスケルトンを次に示します。

vector<int> values = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
unsigned numSuccesses = 0;
do {
    if (bstHeightOf(values) == 3) values++;
} while (next_permutation(values.begin(), values.end());

bstHeightOfここでは、指定されたノードを指定された順序で挿入することによって形成される BST の高さを計算する関数を記述するだけです。これは演習として残しておきます。

これらの観察を使用して、検索スペースをまとめて絞り込むことができます。

  1. 高さ 2 の BST のノードの最大数は 7 です。
  2. ルートを 1、2、3、9、10、または 11 にすることはできません。これは、1 つのサブツリーに 7 つを超えるノードが含まれるため、ツリー全体の高さが 3 を超えるためです。

可能性のあるルートがわかっている場合、1 つのオプションは、キー {1, 2, 3, ..., 11} を持つすべての BST を生成し (すべての順序をリストするのではなく、すべてのツリーをリストすることによって)、それをフィルタリングすることです。高さ 3 のノードのセットまで下げてから、この再帰アルゴリズムを使用して、値を挿入することによって各ツリーを構築できる方法の数を数えます。チェックするツリーの数は順序付けの数よりもはるかに少なく、各ツリーは線形時間でチェックできるため、これはおそらく上記のアプローチよりもはるかに高速です。

お役に立てれば！

于 2013-10-16T23:33:00.877 に答える
0

もっとトリッキーかもしれませんが、完全に手動で行うことができる templatetypdef の答えの代替です。

高さ 3 の完全な二分木を考えてみましょう。これには 15 個のノードがあります。11 個のノードを持つツリーを探しています。つまり、15 個のノードのうち 4 個が欠落しています。これらの欠落ノードが発生する可能性のあるパターンは、ほとんど労力をかけずに列挙できます。(ヒント: パターンを 2 つのグループに分けてこれを行いました。) これにより、ノードが 11 で高さ 3 の木のすべての形状が得られます。

これが完了したら、これらの木の形と探している実際の木との関係について推論する必要があります。(ヒント: この関係は非常に単純です。考えすぎないでください。)

これにより、要件を満たす結果のツリーを列挙できます。96 に到達すると、私と同じ結果になります。これらの木のそれぞれについて、その木を生み出す順列の数を見つける必要があります。

この部分はトリッキーな部分です。これらのツリーを小さなグループに分割する必要がある場合があります。対称性により、そのツリーを生成する順列の数はグループ内のすべてのツリーで同じであることがわかっています。例えば、

       6
      / \
     /   \
    3     8
   / \   / \
  2   5 7   10
 /   /     / \
1   4     9   11

は、それを生じさせる順列の数と同じになります。

       6
      / \
     /   \
    4     9
   / \   / \
  2   5 7   11
 / \     \  /
1   3    8 10

また、各グループに含まれるツリーの数も調べる必要があります。この例のクラスには 16 本の木が含まれています。(ヒント: 2 ～ 32 本の木からなる 7 つのグループに分けました。) 次に、各グループについて、そのような木を生み出す順列の数を見つける必要があります。これは紙の上で「再帰的に」決定できます。上記の 2 つのサンプル ツリーを含むクラスでは、12096 の順列が得られます。そのクラスには 16 の木が含まれているため、そのような木につながる順列の総数は 16*12069 = 193536 です。他の 6 つのクラスについても同じことを行い、合計を取得します。

このソリューションの特定の部分で困惑したり、不明な点がある場合は、遠慮なく質問してください。

于 2013-10-17T21:23:00.163 に答える