Алгоритми та структури даних · Middle · Запитання 35 з 75
Для чого добрий trie (префіксне дерево)?
- 1Сортування масивів чисел за O(n)
- 2Пошук найкоротшого шляху між двома містами
- ✓Правильна відповідь: Пошук за префіксом, наприклад автодоповнення
Пояснення
Кожен вузол представляє префікс, а його діти - наступні символи. Перевірка префікса коштує O(довжина префікса) незалежно від того, скільки слів збережено.