построить уникальное дерево двоичного поиска

Question

Я работаю над проблемой алгоритма. Учитывая n, сгенерируйте все структурно уникальные двоичные деревья поиска, которые сохраняют значения 1 ... n. Решение состояло в том, чтобы перечислить каждое число i в последовательности и использовать число в качестве корня, подпоследовательность 1 ... (i-1) с левой стороны будет лежать на левой ветви корня и аналогично правая подпоследовательность (i +1) ... n лежит на правой ветви корня. Затем постройте поддерево из подпоследовательности рекурсивно. Такой подход гарантирует, что построенные BST все уникальны, поскольку они имеют уникальные корни.

Теперь мой вопрос: что, если деревья не ограничены двоичными деревьями поиска, если это может быть любое двоичное дерево. Как было бы решение? Я бы все же хотел рассмотреть все случаи с корнем i, где i = 1, ... n. Левое поддерево не должно находиться в диапазоне 1 ... (i-1), правое поддерево не должно находиться в диапазоне (i + 1) ... n. Но тогда как их устроить? Создать произвольное подмножество элементов (i-1) и применить?

Answer 1

Предположим, вам была дана следующая проблема: при условии, что n дисков, упорядочите их в уникальных двоичных формах. Затем, следуя вашим правильным рассуждениям в вопросе, вы можете сказать следующее: я буду указывать диски 1, 2, 3, .., n; то я (рекурсивно) построю деревья, корень которых находится на диске # 1, затем на диске # 2 и т. д.

Таким образом, найденные (правильно) найденные вами деревья не имеют ничего общего с содержанием в узлов, не говоря уже о том, удовлетворяет ли содержание инварианту BST. Учитывая ваш вопрос здесь,

1. Если вопрос в том, сколько корневых орграфов существует, то это то же самое, что и раньше.

2. Если вопрос в том, сколько комбинаций корневых орграфов + содержимое узла есть, вы просто перечисляете корневые орграфы, как вы это делали, и для каждого перечисляете перестановки 1, 2, ... п.

   Если это так, и вам не нужно перечислять, а скорее приближать число таких деревьев, то обратите внимание, что это n!, умноженное на Catalan Numbers.

Answer 2

Используйте свой алгоритм для BST. Это генерирует уникальные формы деревьев. Формы уникальны, потому что для каждого корня n в левом поддереве есть n-1 элементов, остальные - справа.

Тогда для каждой формы есть n! упорядочения элементов. Это дает результаты для произвольных деревьев.