Що таке trie (префіксне дерево)?

Trie (префіксне дерево) - це структура даних, яка зберігає рядки посимвольно, дозволяючи ефективно шукати за префіксами.

Кожен вузол дерева представляє один символ, а шлях від кореня до вузла - префікс якогось рядка. Повне слово закінчується у вузлі, позначеному як кінець слова.

Приклад:

Для слів cat, car, dog дерево матиме такий вигляд:

• Корінь → c → a → t (кінець слова) ↳ r (кінець слова)
• Корінь → d → o → g (кінець слова)

Основні операції:

• Вставка: O(L), де L - довжина слова.
• Пошук: O(L).
• Пошук за префіксом: O(P), де P - довжина префікса.

Переваги:

• Швидкий пошук слів і автодоповнення за префіксами.
• Можна зберігати великі словники без дублювання спільних префіксів.

Недоліки:

• Займає більше пам'яті, ніж хеш-таблиця (багато вказівників на дітей).