Рубрики

ВОРОТА | Gate IT 2008 | Вопрос 12

Что из перечисленного правда?

(A) Стоимость поиска дерева AVL θ (log n), но стоимость бинарного дерева поиска O (n)
(B) Стоимость поиска дерева AVL составляет θ (log n), но стоимость полного двоичного дерева θ (n log n)
(C) Стоимость поиска бинарного дерева поиска составляет O (log n), но стоимость дерева AVL θ (n).
(D) Стоимость поиска дерева AVL θ (n log n), но стоимость бинарного дерева поиска O (n)

Ответ: (А)
Пояснение: AVL дерево — это сбалансированное дерево.
Временная сложность AVL дерева поиска = θ (logn)

Но двоичное дерево поиска может быть перекошено, поэтому в худшем случае время поиска BST = θ (n)
Тест на этот вопрос

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

ВОРОТА | Gate IT 2008 | Вопрос 12

0.00 (0%) 0 votes