tree - ユニークな二分探索木

Question

整数のセットが与えられた場合、それから構築できる一意の二分探索木がいくつあるかを調べますか？

私によると、答えは整数セットのサイズによって異なります。セット整数のサイズがnの場合、「n」個の一意の二分探索木を作成できます。

答えがわからない..私は正しいですか？

Answer 1

これは、動的計画法を使用することで解決できます。

numTrees(i+1)=append the last node to the rightmost leaf of bst(i)[numTrees(i)] +
              append the last node as the root of bst(i)[numTrees(i)] +
              insert the last node as non-leaf node sum(k=1...i)(bst(k-1)*bst(i-k)

だからそれはo（n ^ 2）解です。

public int numTrees(int n) {
    if(n == 0 || n == 1 || n == 2)
        return n;
    int bst[] = new int[n+1];
    bst[0] = 1;
    bst[1] = 1;
    bst[2] = 2;
    for (int i=3; i<=n; i++) {
        for (int j=1; j<i-1; j++) {
            bst[i] += bst[j]*bst[i-1-j];
        }
        bst[i] += 2*bst[i-1];
    }
    return bst[n];
}

Answer 2

数値は C_n で、C_n は n 番目のCatalan Numberです。値は、n 個のノードのいずれかをルートとして選択し、ルートの左右のサブツリーを編成するすべての可能な方法を採用することで、再帰的に定義できます。これにより、次の再帰関係が導かれます。

C_n = sum_{i = 0}^{n - 1} C_i * C_{n - 1 - i},

ここで、C_0 = 1 です。