4

ここに示されている方法を使用する：http：//cslibrary.stanford.edu/110/BinaryTrees.html#java

12. countTrees（）ソリューション（Java）
/ **
 キー値1...numKeysの場合、構造的に一意な数
 それらのキーを格納する二分探索木は可能ですか？

 戦略：各値がルートになる可能性があることを考慮してください。
 左右のサブツリーのサイズを再帰的に見つけます。
* /
public static int countTrees（int numKeys）{
  if（numKeys <= 1）{
    return（1）;
  }
  そうしないと {
    //ルートに1つの値があり、残りは何でも
    //左右にそれぞれ独自のサブツリーを形成します。
    //ルートになる可能性のあるすべての値を繰り返し処理します...
    int sum = 0;
    int左、右、ルート;

    for（root = 1; root <= numKeys; root ++）{
      左=countTrees（root-1）;
      right = countTrees（numKeys-root）;

      //このルートを持つ可能なツリーの数==left* right
      合計+=左*右;
    }

    return（sum）;
  }
}

n（n-1）（n-2）... 1、つまりn！

メモ化ツールを使用する場合、複雑さはO（n）ですか？

4

3 に答える 3

3

ノード数nの完全な二分木の数はn番目のカタラン数です。カタラン数は次のように計算されます

代替テキスト

これは複雑さO（n）です。

http://mathworld.wolfram.com/BinaryTree.html

http://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics

于 2010-03-29T04:43:46.720 に答える
0

countTrees特定のノード数に対してこのアルゴリズムが使用する呼び出しの数を数えるのは簡単です。数回の試行の後、n>=2に対して5*3 ^（n-2）の呼び出しが必要であるように見えます。これは、n！よりもはるかにゆっくりと成長します。この主張の証拠は、読者の練習問題として残されています。:-)

あなたが提案したように、メモ化されたバージョンにはO（n）呼び出しが必要でした。

ちなみに、n個のノードを持つ二分木の数はn番目のカタラン数に等しくなります。C nを計算するための明白なアプローチはすべて、nで線形であるように見えるので、メモ化されたの実装countTreesがおそらく最善の方法です。

于 2010-03-29T04:42:27.490 に答える
0

ルックアップテーブルへのヒット数はわかりませんが、メモ化されたバージョンは作成されます（これは間違いなく超線形であり、関数呼び出しのオーバーヘッドがあります）が、数学的な証明により、n番目のカタランと同じ結果が得られます数、1つは線形時間の表形式の方法をすばやく調理することができます：

    int C=1;
    for (int i=1; i<=n; i++)
    {
        C = (2*(2*(i-1)+1)*C/((i-1)+2));
    }
    return C;

ここでメモ化と集計の違いに注意してください

于 2015-01-27T20:04:22.783 に答える