Рубрики

ВОРОТА | GATE MOCK 2017 | Вопрос 46

Учитывая два сбалансированных бинарных дерева поиска, B1 с n элементами и B2 с m элементами, какова временная сложность наиболее известного алгоритма объединения этих деревьев в другое сбалансированное бинарное дерево, содержащее m + n элементов?

(A) O (m + n)
(B) O (молог)

(C) O (нлогм)

(D) O (м 2 + n 2 )

Ответ: (А)
Объяснение:
O (m + n), так как мы можем сначала выполнить порядок на обоих деревьях и сохранить их в двух отдельных массивах. Теперь у нас есть две отсортированные последовательности, и мы можем объединить их в O (m + n) с помощью стандартного алгоритма слияния, а в конечном отсортированном массиве мы можем использовать двоичный поиск для создания дерева с использованием рекурсии. Рекурсивно добавление среднего элемента в корень и повторение одного и того же процесса для левой и правой подмассивов.

Тест на этот вопрос

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

ВОРОТА | GATE MOCK 2017 | Вопрос 46

0.00 (0%) 0 votes