Сколько двоичных деревьев поиска можно построить из n отдельных элементов? И как мы можем найти математически доказанную формулу для этого?Число двоичных деревьев поиска над n отдельными элементами
Пример: Если мы имеем 3 различных элементов, скажем, 1, 2, 3, существует 5 двоичного дерева поиска.
С учетом п элементов, число бинарных деревьев поиска, которые могут быть сделаны из этих элементов задается п-й Catalan number (обозначаемого C п). Это равно
Наглядно каталонские числа представляют число способов, которыми вы можете создать структуру из п элементов, производятся следующим образом:
Этот шаблон отлично соответствует способам, с помощью которых вы можете построить BST из набора из n элементов. Выберите один элемент для использования в качестве корня дерева. Все меньшие элементы должны идти влево, а все более крупные элементы должны идти вправо. Оттуда вы можете построить меньшие BST из элементов слева и справа, а затем слить их вместе с корневым узлом, чтобы сформировать общий BST. Количество способов, которые вы можете сделать с помощью n элементов, задается C n, и поэтому число возможных BST определяется n-м каталонским номером.
Надеюсь, это поможет!
Например, для узлов 10, 10, 10 число двоичных деревьев поиска равно 1. Но каталонское число равно 5. Но если все элементы разные, это нормально. –
@ СухановНиколай Количество БПС по-прежнему 5 для 10,10,10. Форма дерева будет отличаться. – rents
Пусть T (n) - число bsts из 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
Возможно, было бы хорошо упомянуть, что эта рекурсия решает n-е каталонское число. – templatetypedef
@templatetypedef: Вы знаете, как получить каталонскую формулу чисел, начиная с суммы, которую я показал? –
@ user1131467 Эта сумма должна быть ровно числом триангуляций многоугольника над n + 2 узлами, что и было введено для каталонских чисел. Вы фиксируете ребро и позволяете стержню блуждать по другим n вершинам, что оставляет вас с двумя полигонами размером i-1 и n-i. –
Я уверен, что этот вопрос не просто рассчитывать, используя математическую формулу .. Я взял некоторое время и написал программы и объяснения или идеи расчета за то же самое.
Я попытался решить его с помощью рекурсии и динамического программирования. Надеюсь это поможет.
формула уже присутствует в предыдущем ответе:
Так что, если вы заинтересованы в изучении решения и понимания apporach вы всегда можете проверить мою статью Count Binary Search Trees created from N unique elements
Вероятно [связаны] (HTTP: // stackoverflow.com/questions/3042412/with-n-no-of-nodes-how-many-different-binary-and-binary-search-trees-possib). –