Рубрики

ВОРОТА | GATE CS 2008 | Вопрос 46

GATE

Вам дается прохождение P по порядку бинарного дерева поиска по n элементам 1, 2,…, n. Вы должны определить уникальное двоичное дерево поиска, которое имеет P в качестве обхода после заказа. Какова временная сложность наиболее эффективного алгоритма для этого?
(A) O (Logn)
(B) O (n)
(C) O (nLogn)
(D) ничего из вышеперечисленного, так как дерево не может быть однозначно определено.

Ответ: (Б)
Объяснение: Важно отметить, что это Binary Search Tree, а не Binary Tree. В BST обход по порядку всегда можно получить, отсортировав все ключи.

См. Метод 2 http://espressocode.top/construct-bst-from-given-preorder-traversa/ для получения подробной информации.

Эта же техника может быть использована для прохождения заказа.
Тест на этот вопрос

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

ВОРОТА | GATE CS 2008 | Вопрос 46

0.00 (0%) 0 votes