Алгоритми та структури даних · Senior · Запитання 45 з 75
Чому в продакшні trie часто замінюють хеш-таблицями чи radix-деревами?
- 1Trie не можуть зберігати слова з не-ASCII символами
- 2Trie мають O(n²) на кожен пошук
- ✓Правильна відповідь: Звичайні trie марнують пам'ять на вузли з одним нащадком
Пояснення
Вузол на кожен символ із map дітей - це важко. Radix-дерева (Patricia) стискають ланцюжки одиночних нащадків в одне ребро. Роутери вебфреймворків (find-my-way у Fastify) використовують radix-дерева для зіставлення URL.