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

Question

Для двоичных деревьев: Нет необходимости учитывать значения узлов дерева, меня интересуют только разные топологии деревьев с узлами 'N'.

Для дерева двоичного поиска: Мы должны учитывать значения узлов дерева.

Answer 1

1. Общее количество бинарных деревьев = = 1003 *

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

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

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

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

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

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

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

Answer 4

Если дано нет. Узлов N Тогда.

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

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

Answer 5

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

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

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

Answer 6

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

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

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

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

Answer 7

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

Answer 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

Answer 9

Правильный ответ должен быть 2nCn / (n + 1) для немаркированных узлов, а если узлы помечены, то (2nCn) * n! / (N + 1) .

Answer 10

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

Не нужно учитывать значения, нам нужно взглянуть на структуру.

Задано (2 степени n) - n

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

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

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

, данным 2n C n / n + 1