Алгоритми та структури даних · Middle · Запитання 39 з 75
Яку проблему розв'язують самобалансовані дерева (AVL, червоно-чорні)?
- ✓Правильна відповідь: Тримають висоту O(log n), тож операції лишаються швидкими
- 2Зберігають дубльовані ключі компактніше
- 3Дозволяють кожному вузлу мати понад двох нащадків
Пояснення
Після вставок і видалень вони обертають вузли, щоб дерево лишалося приблизно збалансованим. Упорядковані словники в багатьох мовах (Java TreeMap, C++ std::map) - це червоно-чорні дерева.