Структуры данных
Trie: Дерево для строк
Цели урока
- Понять структуру Trie
- Реализовать insert, search, startsWith
- Написать автодополнение
- Узнать когда Trie лучше хеша
Предварительные знания
- Введение в деревья
Вы вводите 'prog' в Google - и мгновенно видите 'programming', 'progress', 'program'. Как это работает с миллиардами запросов? Trie - дерево, где пути = слова.
- Google - автодополнение поисковых запросов
- IDE - подсказки кода и автокомплит
- Spell checker - проверка орфографии
- Роутеры - longest prefix match для IP
От de la Briandais до названия 'trie'
Рене де ла Бриандэ описал структуру префиксного дерева в 1959 году как способ хранить файловые каталоги, не пересканируя ключи целиком. В 1960 году Эдвард Фредкин предложил название 'trie', взяв его из середины слова reTRIEval, поэтому одни произносят его как 'tree', а другие как 'try'. Позже структура стала основой таблиц IP-маршрутизации, где longest-prefix match решает, куда пойдёт каждый пакет, и систем автодополнения, которые превращают префикс в ранжированные подсказки за миллисекунды.
Зачем нужен Trie?
**Задача:** автодополнение в поисковике. Пользователь вводит "pro", нужно показать: "programming", "product", "project".
**Наивный подход:** перебрать все слова, проверить startsWith. При миллионе слов - медленно!
**Trie (от retrieval):** дерево, где каждое ребро - это символ, а путь от корня - префикс.
Trie оптимизирован для операций с:
Структура Trie
**Ключевые особенности:**
- Корень пустой (не содержит символ)
- Каждое ребро = один символ
- Путь от корня = префикс
- is_end помечает полные слова
**Альтернатива children:** массив из 26 элементов для английских букв. Быстрее, но тратит память.
Что хранится в children у TrieNode?
Вставка слова
**Сложность:** O(m), где m - длина слова. Не зависит от количества слов в Trie!
Сложность вставки слова длины m в Trie с n словами:
Поиск и startsWith
**Автодополнение:** находим узел префикса, затем DFS по всем путям:
Разница между search и starts_with:
Применения Trie
- **Автодополнение** - Google, IDE, терминал
- **Spell checker** - быстрая проверка существования слова
- **IP routing** - longest prefix match в роутерах
- **T9 ввод** - старые телефоны с кнопками
- **Биоинформатика** - поиск в ДНК последовательностях
| Операция | Trie | HashSet | BST |
|---|---|---|---|
| Поиск слова | O(m) | O(m) avg | O(m·log n) |
| Поиск по префиксу | O(m) | O(n·m) | O(n·m) |
| Автодополнение | O(m + k) | O(n·m) | O(n·m) |
**Trie побеждает** когда нужны операции с префиксами. Для точного поиска HashSet часто достаточен.
Trie всегда экономнее HashSet по памяти, потому что общие префиксы хранятся один раз.
В реальной памяти Trie часто проигрывает HashSet: каждый узел держит словарь/массив детей с указателями, а общий префикс экономит только символы. На словаре в 100k слов Trie занимает в разы больше байтов, чем HashSet с теми же строками.
Иллюзия общего хранения префиксов вытесняет из головы накладные расходы на структуру узлов. Экономия на символах есть, но overhead из 26 указателей (или dict) на каждый узел эту экономию обычно перебивает.
Для какой задачи Trie НЕ лучший выбор?
Ключевые идеи
- Trie = префиксное дерево для строк
- Узел: children (dict), is_end (bool)
- Все операции O(m), m = длина слова
- Идеален для автодополнения и поиска по префиксу
Вопросы для размышления
- Префиксное дерево используется в DNS, IP routing и BPE-токенизации - что общего у этих задач, что делает именно Trie оптимальным выбором?
- Если поиск 'starts_with' занимает O(m), а количество слов с этим префиксом равно k, какова сложность собрать их все - и почему DFS-обход поддерева важнее самой длины префикса?
- В каком случае радикс-дерево (Patricia trie) с компрессией одиночных цепочек начинает выигрывать у обычного Trie, и какие свойства входных данных это запускают?
Следующие темы
От строковых структур к приоритетным очередям.
- Heap — Быстрый доступ к min/max
Связанные уроки
- ds-12-balanced-trees — Trie - специализированное дерево, строится на основах BST
- ds-17-graph-algorithms — Trie - частный случай DAG для строковых ключей
- ds-06-hash-intro — Оба решают prefix lookup, но с разными trade-off
- aie-12-rag-fundamentals — Trie лежит в основе токенизаторов BPE и prefix search в RAG
- comp-06-lexer-basics