Двоичные деревья поиска (BST) — это фундаментальная структура данных, используемая в информатике и часто используемая для эффективных операций поиска, вставки и удаления. Уникальным BST является дерево, в котором структура дерева уникальна, что приводит к различным комбинациям значений. В этой статье блога мы рассмотрим различные методы создания уникальных BST, сопровождаемые примерами кода на популярном языке программирования.

Методы создания уникальных BST:

1. Рекурсивный подход.
   Рекурсивный подход — это интуитивно понятный способ создания уникальных BST. Мы можем выбрать корневой узел и рекурсивно генерировать уникальные BST для левого и правого поддеревьев. Общее количество уникальных BST можно рассчитать путем умножения количества уникальных левых поддеревьев на количество уникальных правых поддеревьев. Вот пример реализации на Python:

def generate_unique_bsts(n):
    if n == 0:
        return [None]
    result = []
    for i in range(1, n + 1):
        left_subtrees = generate_unique_bsts(i - 1)
        right_subtrees = generate_unique_bsts(n - i)
        for left in left_subtrees:
            for right in right_subtrees:
                root = TreeNode(i)
                root.left = left
                root.right = right
                result.append(root)
    return result

2. Динамическое программирование.
   Динамическое программирование можно использовать для оптимизации рекурсивного подхода путем сохранения ранее вычисленных результатов. Мы можем использовать таблицу динамического программирования для хранения количества уникальных BST для разных чисел. Это позволяет избежать избыточных вычислений и повышает эффективность. Вот пример реализации на Java:

public int numUniqueBSTs(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }
    return dp[n];
}

3. Формула каталонского числа.
   Другой подход к созданию уникальных BST — использование формулы каталонского числа. Каталонские числа представляют собой количество уникальных BST, которые могут быть сформированы с заданным количеством узлов. Формула расчета n-го каталонского числа: (2n)! / ((n + 1)! * n!). Мы можем использовать эту формулу для непосредственного создания уникальных BST. Вот пример реализации на C++:

int numUniqueBSTs(int n) {
    long long int catalan = 1;
    for (int i = 0; i < n; i++) {
        catalan *= (2 * n - i);
        catalan /= (i + 1);
    }
    return int(catalan);
}