Число связанных с BST связанных списков чисел

Question

Предположим, у меня есть связанный список положительных чисел, сколько из них BST могут быть сгенерированы из них, при условии, что все узлы все, необходимые для формирования дерева?

И наоборот, сколько BST может быть сгенерировано при условии, что любое число из списка связанных узлов может существовать в этих деревьях?

Бонус: сколько сбалансированных BST можно сформировать? Любая помощь или руководство получают большую оценку.

Answer 1

Вы можете использовать динамическое программирование для вычисления этого.

Просто отметьте, что неважно, какие цифры, сколько именно. Другими словами, для любых n различных целых чисел существует одинаковое количество разных BST. Назовем это число f (n).

Тогда, если вы знаете, F (K) для к < п, можно получить п (п):

f(n) = Sum (f(i) + f(n-1-i), i = 0,1,2,...,n-1) 

Каждое слагаемое представляет собой количество деревьев, для которых (1 + I) -го Наименьшее число находится в корне (таким образом, в левом поддереве, где находятся числа i, а в правом поддереве есть n-1-i). Итак, DP решает это.

Сейчас общее количество BSTs (с любыми узлами из списка) является только сумма:

Sum (Binomial(n,k) * f(k), k=1,2,3,...,n) 

Это потому, что вы можете выбрать к из них в Binomial(n,k) способами, и тогда вы знаете, что есть f(k) BST для них.