Префиксное дерево Trie: как ускорить автодополнение в 100 раз

Зачем вам префиксное дерево?

Представьте: вы пишете поисковую строку, а интерфейс зависает на секунду после каждого символа. Знакомо? Я тоже через это прошёл, когда пытался сделать автодополнение для 200 тысяч слов с помощью обычного цикла. Друг кричал: «Ты снова заморозил всё приложение?» — и я чувствовал себя Нео до того, как он увидел Матрицу: всё было размытым и медленным.

Тогда я понял две вещи:

• Перебор не масштабируется, когда данных много.
• Нужна структура, которая позволяет прыгать сразу к кандидатам с общим префиксом, не просматривая весь набор.

Встречайте префиксное дерево (Trie) — дерево, где каждый узел — символ, а пути от корня образуют слова. Это как световой меч для строковых задач: элегантно, точно и смертельно эффективно, когда умеешь им владеть.

Почему Trie даёт O(L) на поиск?

Допустим, мы ищем все слова с префиксом «cat». В Trie мы просто идём по дверям: c → a → t — и оказываемся в комнате, где лежат только слова с этим префиксом. Не нужно заглядывать в другие комнаты — коридор уже отфильтровал их.

Магия в двух инвариантах:

• Каждый узел хранит флаг is_word — конец слова или нет.
• Каждый узел содержит словарь (или массив) детей по следующему символу.

Вставка слова — проход/создание узлов за O(L). Поиск префикса — тот же путь за O(L). Когда дошли до узла префикса, сбор всех завершений — это обход поддерева в глубину. Общее время пропорционально длине префикса + размеру вывода. Это оптимально: вы не можете вернуть k слов, не прочитав хотя бы k символов.

В терминах собеседований: разница между линейным сканированием (O(N·L) на запрос) и префиксным деревом (O(L + размер вывода)). Тот же скачок, что от поиска базы повстанцев по всей галактике к использованию голокрона, который прыгает прямо в нужный сектор.

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

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) -> None:
        """Вставка слова — O(L)"""
        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 _find_node(self, prefix: str) -> TrieNode | None:
        """Возвращает узел, соответствующий префиксу, или None"""
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None  # ловушка #1: считать, что префикс существует
            node = node.children[ch]
        return node

    def autocomplete(self, prefix: str) -> list[str]:
        """Возвращает все слова с заданным префиксом"""
        node = self._find_node(prefix)
        if not node:
            return []
        results = []
        # DFS по поддереву
        def dfs(current, path):
            if current.is_word:
                results.append(path)  # ловушка #2: забыть добавить само слово
            for ch, child in current.children.items():
                dfs(child, path + ch)
        dfs(node, prefix)
        return results

# Пример использования
trie = Trie()
trie.insert("car")
trie.insert("card")
trie.insert("care")
trie.insert("cartoon")
trie.insert("dog")

print(trie.autocomplete("ca"))  # ['car', 'card', 'care', 'cartoon']
print(trie.autocomplete("do"))  # ['dog']
print(trie.autocomplete("zz"))  # []

Разбор ключевых моментов

Метод _find_node выполняет проход по префиксу. Если символ отсутствует — сразу возвращаем пустой список, без лишних действий. DFS обходит только поддерево узла префикса — каждый посещённый узел соответствует символу из хотя бы одного подходящего слова, поэтому работа ограничена размером вывода.

Флаг is_word позволяет включить сам префикс в результаты (например, «cat» при запросе «cat»). Забыть это — частая ошибка, из-за которой возвращаются только более длинные слова.

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

LeetCode 208 — Implement Trie (Prefix Tree)

Условие: спроектировать структуру с методами insert, search, startsWith. Решение — тот же класс Trie, где search — обёртка над _findNode с проверкой node.is_word.

LeetCode 642 — Design Search Autocomplete System

Условие: даны предложения с частотами, нужно возвращать топ-3 горячих предложений для вводимого префикса, обновляя частоты по мере ввода. Основа — Trie, где каждый узел хранит карту предложение → частота, а автодополнение собирает топ-k через мин-кучу при обходе поддерева.

Обе задачи сводятся к одному: Trie позволяет прыгнуть к нужному узлу за O(L), а затем остаётся только обработать содержимое этого поддерева.

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

Теперь, когда у вас есть Trie в арсенале, вы можете:

• Сократить задержку в поиске по мере ввода с секунд до миллисекунд, даже для миллионов записей.
• Решать целый класс строковых задач (поиск по словарю, наибольший общий префикс, разбиение слова и т.д.) одним паттерном.
• Впечатлить интервьюера, показав понимание не только API, но и причины гарантии O(L).

Я до сих пор улыбаюсь, когда вижу, как у кандидата загораются глаза после объяснения, что Trie — это «коридор, фильтрующий префиксы». Это момент, когда абстракция становится осязаемой — как осознание, что Сила — не мистика, а практический способ двигать предметы силой мысли.

Итак: возьмите словарь, постройте свой Trie и почувствуйте, как автодополнение становится похожим на разблокировку секретного уровня в игре.

Ваша очередь: попробуйте расширить Trie для поддержки поиска с подстановочными знаками (например, c*t находит «cat», «cot», «civet»). Напишите своё решение в комментариях или поделитесь в соцсетях — мне будет интересно посмотреть, как вы владеете Силой! Удачи в кодинге!