С "N" нет узлов, сколько различных двоичных и двоичных поисковых деревьев возможно?

Ответ 1

Я рекомендую эту статью моего коллеги Ника Парланте (со спины, когда он еще был в Стэнфорде). Число структурно разных бинарных деревьев (задача 12) имеет простое рекурсивное решение (которое в замкнутой форме заканчивается каталонской формулой, которую уже упомянул @codeka).

Я не уверен, как количество структурно разных деревьев двоичного поиска (коротких BSTs) будет отличаться от числа "простых" двоичных деревьев - за исключением того, что если "считать tree node values" означает каждый node может быть, например, любое число, совместимое с условием BST, то число различных (но не всех структурно различных!) BST бесконечно. Я сомневаюсь, что вы это имеете в виду, пожалуйста, проясните, что вы имеете в виду на примере!

Ответ 2

• Всего нет двоичных деревьев =

• Суммирование по я дает общее число двоичных деревьев поиска с n узлами.

Базовый случай равен t (0) = 1 и t (1) = 1, то есть есть один пустой BST и существует один BST с одним node.

Итак, в общем случае вы можете вычислить общее количество двоичных поисковых деревьев, используя приведенную выше формулу. Мне был задан вопрос в интервью Google, связанный с этой формулой. Вопрос в том, сколько всего нет двоичных поисковых деревьев возможно с 6 вершинами. Итак, ответ t (6) = 132

Я думаю, что я дал вам некоторую идею...

Ответ 3

Число бинарных деревьев можно вычислить, используя каталонский номер.

Число двоичных деревьев поиска можно рассматривать как рекурсивное решение. т.е. Число двоичных деревьев поиска = (Число левых двоичных поисковых поддеревьев) * (Число двоичных поисковых подстрок Вправо) * (Пути выбора корня )

В BST применяется только относительное упорядочение между элементами. Таким образом, без каких-либо потерь по общности можно предположить, что отдельные элементы в дереве - это 1, 2, 3, 4,...., n. Кроме того, пусть число BST будет представлено f (n) для n элементов.

Теперь мы имеем несколько случаев для выбора корня.

• выберите 1 как root, ни один элемент не может быть вставлен в левое поддерево. Элементы n-1 будут вставлены в правое поддерево.
• Выберите 2 как root, 1 элемент можно вставить в левое поддерево. Элементы n-2 могут быть вставлены в правое поддерево.
• Выберите 3 как root, 2-й элемент можно вставить в левое поддерево. Элементы n-3 можно вставить в правое поддерево.

...... Аналогично, для i-го элемента как корня элементы i-1 могут быть слева и n-i справа.

Эти под деревья сами являются BST, поэтому мы можем суммировать формулу как:

f (n) = f (0) f (n-1) + f (1) f (n-2) +.......... + f (n-1) F (0)

Базовые случаи, f (0) = 1, так как существует ровно один способ сделать BST с 0 узлами. f (1) = 1, так как существует ровно один способ сделать BST с 1 node.

Ответ 4

У Эрика Липперта недавно была очень подробная серия сообщений в блогах об этом: " Каждое двоичное дерево есть" и " Каждое дерево есть" (плюс еще несколько после этого).

В ответ на ваш конкретный вопрос он говорит:

Число двоичных деревьев с n узлами задается каталонскими числами, которые имеют много интересных свойств. N-е каталонское число определяется по формуле (2n)!/(n + 1)! n!, которая растет экспоненциально.

Ответ 5

Если дано нет. узлов N.

Различное число BST = каталанский (N)
Различное число структурно различных двоичных деревьев = Catalan (N)

Различное число двоичных деревьев = N! * Каталанский (N)

Ответ 6

Различные бинарные деревья с n узлами:

(1/(n+1))*(2nCn)

где C = комбинация, например.

n=6,
possible binary trees=(1/7)*(12C6)=132

Ответ 7

(2n)!/n!*(n+1)!

Ответ 8

The number of possible binary search tree with n nodes (elements,items) is

=(2n C n) / (n+1) = ( factorial (2n) / factorial (n) * factorial (2n - n) ) / ( n + 1 ) 

where 'n' is number of nodes  (elements,items ) 

Example :

for 
n=1 BST=1,
n=2 BST 2,
n=3 BST=5,
n=4 BST=14 etc

Ответ 9

двоичное дерево:

Нет необходимости рассматривать значения, нам нужно посмотреть на structrue.

Учитывая (2 power n) - n

Например: для трех узлов это (2 мощность 3) -3 = 8-3 = 5 разных структур

двоичное дерево поиска:

Нам нужно рассмотреть даже значения node. Мы называем это каталонским номером

Учитывая 2n C n/n + 1