Число двоичных деревьев поиска над n отдельными элементами

Ответ 1

Учитывая n элементов, число двоичных деревьев поиска, которые могут быть сделаны из этих элементов, дается nth Каталонский номер (обозначается C < суб > псуб > ). Это равно

Интуитивно, каталонские числа представляют количество способов создания структуры из n элементов, которые производятся следующим образом:

• Закажите элементы как 1, 2, 3,..., n.
• Выберите один из этих элементов для использования в качестве элемента сворачивания. Это разбивает оставшиеся элементы на две группы: те, которые идут перед элементом и те, которые приходят после.
• Рекурсивно строить структуры из этих двух групп.
• Объедините эти две структуры вместе с одним удаленным элементом, чтобы получить окончательную структуру.

Этот шаблон отлично соответствует способам, с помощью которых вы можете построить BST из набора из n элементов. Выберите один элемент для использования в качестве корня дерева. Все меньшие элементы должны идти влево, а все более крупные элементы должны идти вправо. Оттуда вы можете построить меньшие BST из элементов слева и справа, а затем слить их вместе с корнем node, чтобы сформировать общий BST. Количество способов, которые вы можете сделать с помощью n элементов, определяется C _n, и поэтому число возможных BST определяется n-м каталонским числом.

Надеюсь, это поможет!

Ответ 2

Я уверен, что этот вопрос состоит не только в подсчете с использованием математической формулы. Я вынул некоторое время и написал программу и объяснение или идею расчета для того же самого.

Я попытался решить его с помощью рекурсии и динамического программирования. Надеюсь, это поможет.

Формула уже присутствует в предыдущем ответе:

Итак, если вы заинтересованы в изучении решения и понимании apporach, вы всегда можете проверить мою статью Count Binary Search Trees, созданные из N уникальных элементов

Ответ 3

Пусть T (n) - число bsts из n элементов.

Учитывая n различных упорядоченных элементов, пронумерованных от 1 до n, мы выбираем я как корень.

Это оставляет (1..i-1) в левом поддереве для комбинаций T (i-1) и (i + 1..n) в правом поддереве для комбинаций T (n-i).

Таким образом:

T(n) = sum_i=1^n(T(i-1) * T(n-i))

и, конечно, T (1) = 1