Рубрики

Структуры данных | Сбалансированные деревья бинарного поиска | Вопрос 13

Какие из следующих утверждений верно
(A) Деревья AVL более сбалансированы по сравнению с красно-черными деревьями, но они могут вызвать большее вращение при вставке и удалении.
(B) Высота деревьев AVL и красно-черных деревьев, как правило, одинакова, но деревья AVL могут вызывать больше поворотов при вставке и удалении.
(C) Красно-черные деревья более сбалансированы по сравнению с деревьями AVL, но могут вызывать больше поворотов при вставке и удалении.
(D) Высота деревьев AVL и красно-черных деревьев, как правило, одинакова, но красно-черные тростники могут вызывать больше поворотов во время вставки и удаления.

Ответ: (А)
Пояснение: Красное Черное Дерево с n узлами имеет высоту <= 2Log2 (n + 1)

Дерево AVL с n узлами имеет высоту меньше чем Log φ (√5 (n + 2)) — 2.

Следовательно, деревья AVL более сбалансированы по сравнению с красно-черными деревьями, но они могут вызвать большее вращение при вставке и удалении. Так что, если ваше приложение включает в себя много частых вставок и удалений, тогда предпочтительны красно-чёрные деревья. И если вставки и удаления происходят реже, а поиск — более частой операцией, то дерево AVL следует отдавать предпочтение красному черному дереву.
Тест на этот вопрос

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

Структуры данных | Сбалансированные деревья бинарного поиска | Вопрос 13

0.00 (0%) 0 votes