Количество двоичных деревьев и BST с узлом n

Если число узлов = n, мы имеем

  1. Количество BST = C (n)
  2. Число структурно различных бинарных деревьев = C (n)
  3. Количество бинарных деревьев = n! * C(n)

где C (n) = каталонское число = (2n)! / [ (n+1)! * п! ]

Я понимаю #1. Я могу сделать это, используя свойство BST [Код ниже]. Может кто-нибудь сказать, пожалуйста, как прийти к № 2 и № 3? Благодарю.

public static long countBST_dp(int n) {
    if(n == 0 || n == 1) return 1;
    long[] arr = new long[n+1];
    arr[0] = 1; arr[1] = 1;

    for (int i = 2; i < arr.length; i++) {
        int isum = 0;
        for (int k = 1; k <= i; k++) {
            isum += arr[k-1] * arr[i-k];
        }
        arr[i] = isum;
    }
    return arr[n];
}
Источник

3 ответа

Решение

Количество структурно различных бинарных деревьев - здесь порядок не имеет значения, все вершины одинаковы - все, что имеет значение, это структура. Таким образом, мы можем сделать биекцию - учитывая BST, создать дерево, где все узлы идентичны. Теперь, учитывая два разных BST - вы получите два разных дерева с одинаковыми узлами (в противном случае между ними был порядок в порядке узлов, и, следовательно, дерево не BST), поэтому наша функция инъективна. Также есть некоторый BST, который может "генерировать" любое "структурное дерево", поэтому наша функция является субъективной.
Так как мы нашли биекцию из {T | T is a BST of nodes [1,2,...,n]} в {T | T is a binary tree where all nodes are identical} - размер двух комплектов одинаков. Так как мы знаем первый набор, если по размеру C(n) - второй тоже есть.

Количество бинарных деревьев = n! * C (n)

Для каждого дерева T от {T | T is a binary tree where all nodes are identical} мы можем генерировать n! различные деревья, так что узлы отличаются друг от друга, применяя все перестановки на узлах. Таким образом, есть |{T | T is a binary tree where all nodes are identical}| * n! разные деревья, так что узлы отличаются друг от друга. Поскольку мы уже доказали, что размер набора является каталонским числом, мы получаем C(n)*n!

Источник

Для #1 вы можете посмотреть это: Подсчитать количество бинарных поисков, заданных N отличных элементов

Для #2 вы можете посмотреть это: Количество двоичных деревьев с n узлами
Основная идея состоит в том, что мы берем узел в качестве корня и распределяем остальное по левому и правому поддеревьям, которые являются меньшими подзадачами исходного.

Для #3 это число различных двоичных деревьев (#2), умноженное на различные схемы чисел для каждого дерева (n!). Думайте об этом как о заполнении BST любой перестановкой n чисел.

Источник

2. Число структурно различных бинарных деревьев = C(n)

Из Википедии каталонское число удовлетворяет рекуррентному соотношению:

C(0) = 1, C(1) = 1
C(n) = C(0)*C(n-1) + C(1)*C(n-2) + ... + C(n-1)*C(0)

обозначать h(n) = No. of structurally different binary trees with node n,затем:

h(0) = 1
h(1) = 1
...
With n node, left subtree of root may have 0,1,...,n-1 nodes
accordingly right subtree have n-1,n-2,...,0 nodes, so:
h(n) = h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)*h(0) = C(n)

3. Количество бинарных деревьев = n! * C (n)

Если структура бинарного дерева фиксирована, мы можем "заполнить" дерево n различные значения в n! пути.

Есть C(n) структуры, так No. of binary trees = n! * C(n),

Источник
Другие вопросы по тегам