Рубрики

Структуры данных | Разное | Вопрос 5

Структура данных требуется для хранения набора целых чисел, так что каждая из следующих операций может быть выполнена за (log n) время, где n — количество элементов в наборе.

   o    Delection of the smallest element 
   o    Insertion of an element if it is not already present in the set

Какую из следующих структур данных можно использовать для этой цели?
(A) Куча может быть использована, но не сбалансированное дерево двоичного поиска
(B) Можно использовать сбалансированное двоичное дерево поиска, но не кучу
(C) Можно использовать как сбалансированное бинарное дерево поиска, так и кучу
(D) Ни сбалансированное двоичное дерево поиска, ни куча не могут быть использованы

Ответ: (Б)
Объяснение: Самобалансирующееся балансирующее дерево двоичного поиска, содержащее n элементов, позволяет искать, вставлять и удалять элемент за O (log n) наихудшего времени. Поскольку это BST, мы легко можем найти минимальный элемент в O (nlogn). Смотрите наш пост Найти минимальный элемент в бинарном дереве поиска для деталей.

Поскольку Heap является сбалансированным двоичным деревом (или почти полным двоичным деревом), сложность вставки для heap равна O (logn). Также сложность для получения минимума в минимальной куче — O (logn), потому что удаление корневого узла вызывает вызов heapify (после удаления первого элемента из массива), чтобы сохранить свойство дерева кучи. Но куча не может быть использована для вышеуказанной цели, как говорится в вопросе — вставьте элемент, если его еще нет. Для кучи, мы не можем узнать в O (logn), присутствует ли элемент или нет. Спасибо игре за правильное решение.
Тест на этот вопрос

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

Структуры данных | Разное | Вопрос 5

0.00 (0%) 0 votes