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

Учитывая n элементов, количество бинарных деревьев поиска, которые можно составить из этих элементов, определяется n-м каталонским числом (обозначается C_n). Это равно

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

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

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

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

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

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

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

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

Пусть T(n) будет количеством BST из n элементов.

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

Это оставляет (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