Как работает Trie-дерево: автодополнение за O(L)

Зачем вам Trie-дерево?

Вы когда-нибудь печатали в поисковой строке и видели мгновенные подсказки? Я впервые попытался реализовать автодополнение для пет-проекта и на каждом символе перебирал список из 100 тысяч слов. Ноутбук гудел как турбина, а интерфейс зависал на секунду. Проблема была не в коде, а в структуре данных: просмотр плоского списка даёт O(N × L) на запрос (N слов, L средняя длина). Нужно было разделить работу между словами с общим префиксом. Тогда я открыл для себя Trie-дерево (читается «трай»).

Как устроено Trie-дерево?

Trie — это дерево, где каждый узел — символ, а путь от корня до узла образует префикс. Слова «кот», «код» и «кофе» делят ветвь «к-о». Вместо хранения каждого слова отдельно мы храним каждый символ один раз на пути. Поиск всех слов по префиксу — это спуск по символам префикса до узла, а затем сбор всех листьев-потомков. Никакого перебора, только O(L) шагов, где L — длина префикса.

Реализация Trie на Python

Напишем минимальное Trie для автодополнения. Будем хранить флаг is_word для пометки конца слова и словарь children для переходов.

class TrieNode:
    def __init__(self):
        self.children = {}  # символ -> TrieNode
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True

    def _dfs(self, node: TrieNode, prefix: str, results: list):
        if node.is_word:
            results.append(prefix)
        for ch, child in node.children.items():
            self._dfs(child, prefix + ch, results)

    def suggestions(self, prefix: str) -> list:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []  # префикс не найден
            node = node.children[ch]
        results = []
        self._dfs(node, prefix, results)
        return results

Сравнение: до и после

Наивный перебор списка

def naive_suggestions(words, prefix):
    return [w for w in words if w.startswith(prefix)]

Для 200 тысяч слов длиной 8 каждый вызов делает ~1.6 млн сравнений символов.

Trie-дерево

Вставка всех слов стоит O(общая длина) — 1.6 млн операций. Каждый запрос — O(L) (L длина префикса, обычно < 10). Для префикса из 5 символов — 5 переходов по узлам. Ускорение на практике >300×.

Частые ошибки

• Забыть отметить конец слова — без флага is_word вы никогда не узнаете, что путь образует целое слово.
• Список вместо словаря для детей — линейный поиск среди детей превращает каждый шаг в O(σ), где σ — размер алфавита. Используйте хеш-таблицу для константного доступа.

Задачи с собеседований

«Разработайте систему автодополнения»

Дан список предложений с частотами. Нужно вернуть топ-3 популярных предложений для префикса. Trie хранит предложения, каждый узел содержит max-heap (или сортированный список) из топ-3 частот в своём поддереве. Ответ за O(L).

«Самое длинное слово, где все префиксы — слова»

Вставьте все слова в Trie, затем DFS только по узлам с is_word = True. Самый глубокий достижимый узел — ответ. Сложность O(N × L).

Практический вывод

Trie-дерево превращает медленный перебор в молниеносный поиск. Возьмите словарь любимых цитат, вставьте их в Trie и сделайте мини-автодополнение. Попробуйте ранжировать подсказки по популярности или добавить нечёткий поиск (автоматы Левенштейна). Какую фичу добавите вы?