Уникальные двоичные деревья поиска

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)

так что это о (п ^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-й каталонский номер. Значение можно определить рекурсивно, выбрав в качестве корня любой из n узлов, а затем выбрав все возможные способы организации левого и правого поддеревьев корня, что приведет к следующему соотношению рекуррентности:

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

где C_0 = 1.