Рубрики

ВОРОТА | GATE-CS-2003 | Вопрос 6

GATE

Пусть T (n) будет числом различных деревьев двоичного поиска на n различных элементах.
потом где х
(А) н-к + 1
(Б) нк
(С) нк-1
(D) нк-2

Ответ: (Б)
Объяснение: Идея состоит в том, чтобы создать корневой ключ, поместить (k-1) ключей в одно поддерево, а оставшиеся nk ключей — в другое поддерево.

Двоичное дерево поиска (BST) — это дерево, в котором все узлы следуют указанным ниже свойствам:

  • Левое поддерево узла имеет ключ, меньший или равный ключу его родительского узла.
  • Правое поддерево узла имеет ключ больше, чем ключ его родительского узла.

Теперь строим деревья бинарного поиска из n различных чисел
Для простоты рассмотрим n различных чисел как первые n натуральных чисел (начиная с 1)
Если n = 1, у нас есть только одна возможность, поэтому только 1 BST.
Если n = 2, у нас есть 2 возможности, когда меньшее число является корневым, а большее число — правым дочерним или вторым, когда большее число является корневым, а меньшее число — левым дочерним.

Если n = 3, у нас есть 5 возможностей. Сохраняя каждое число сначала как корень, а затем расположив оставшиеся 2 числа, как в случае n = 2.

Если n = 4, у нас есть 14 возможностей. Принятие каждого числа в качестве корня и размещение чисел smaal в качестве левого поддерева и больших чисел в качестве правого поддерева.

Таким образом, мы можем заключить, что при n различных числах, если мы возьмем корень 'k', то все числа, меньшие, чем k, станут левым поддеревом, а числа, большие чем k, будут правым поддеревом, где правое поддерево и левое поддерево снова будут построены рекурсивно. как корень.
Следовательно,

Это решение предоставлено Parul Sharma.
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2003 | Вопрос 6

0.00 (0%) 0 votes