Префиксное дерево (Trie): автодополнение за O(L+K)

Почему автодополнение тормозит и как Trie спасает ситуацию

Вы когда-нибудь замечали, что поле поиска на сайте начинает лагать, когда пользователь быстро печатает? Я столкнулся с этим при создании виджета автодополнения для каталога из 200 000 товаров. Каждое нажатие клавиши запускало полный проход по списку, и интерфейс превращался в патоку. Я задался вопросом: почему мы проверяем одни и те же префиксы снова и снова? Ответ привёл меня к структуре данных, которая называется префиксное дерево (Trie).

Что такое префиксное дерево (Trie) и почему оно работает быстро

Префиксное дерево (Trie) хранит слова, группируя их по общим префиксам. Представьте слова «cat», «car», «cart» и «dog». В Trie корневой узел имеет ветку c, которая разветвляется на a→t (для «cat») и a→r→t (для «cart»). Слово «dog» идёт по отдельному пути d→o→g. Каждый общий префикс хранится один раз, а для поиска нужно просто спуститься по дереву, следуя символам запроса.

Временная сложность автодополнения составляет O(L + K), где L — длина префикса, а K — количество результатов. Почему? Потому что мы проходим по префиксу посимвольно (O(L)), а затем собираем все слова из поддерева (O(K)). Никакой лишней работы для слов, не имеющих общего префикса. Сравните с наивным подходом: O(N × L), где N — размер словаря. Для больших N Trie — это как переход от тупого меча к световому клинку: одним движением рассекает лес префиксов.

Реализация Trie на Python: от наивного фильтра к быстрому автодополнению

Начнём с наивного решения, которое просто фильтрует список:

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

Просто, но при 200 000 слов каждое нажатие клавиши вызывает задержку. Теперь реализуем Trie. Сначала определим узел:

class TrieNode:
    __slots__ = ('children', 'word')

    def __init__(self):
        self.children = {}  # символ → TrieNode
        self.word = None    # хранит полное слово, если узел завершает слово

Теперь само дерево:

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

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.word = word  # отмечаем конец слова

    def _collect(self, node, results):
        """Обход в глубину для сбора всех слов в поддереве"""
        if node.word:
            results.append(node.word)
        for child in node.children.values():
            self._collect(child, results)

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

Использование:

dictionary = ['cat', 'car', 'cart', 'dog', 'door', 'done', 'dongle']
trie = Trie()
for w in dictionary:
    trie.insert(w)

print(trie.starts_with('ca'))  # ['cat', 'car', 'cart']
print(trie.starts_with('do'))  # ['dog', 'door', 'done', 'dongle']

Типичные ошибки при работе с Trie (и как их избежать)

Вот несколько ловушек, которые могут превратить элегантное O(L+K) решение в медленный перебор:

• Забыть отметить конец слова — если не установить node.word, то слова, которые являются префиксами других (например, «cat» и «cater»), не будут найдены.
• Использовать список вместо словаря для детей — это замедляет поиск до O(размер алфавита) на каждом шаге. Используйте хеш-таблицу для мгновенного перехода.
• Не очищать результаты между вызовами — метод _collect добавляет в переданный список; всегда передавайте новый список, чтобы избежать накопления.

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

Где применять Trie: реальные сценарии

С Trie вы можете построить автодополнение, которое работает мгновенно даже с сотнями тысяч терминов. Это полезно для поисковых строк, автодополнения кода в IDE или даже для списка заклинаний в RPG. Каждый запрос теперь касается только нужной ветви дерева, а не всего леса.

Главный выигрыш — не только скорость, но и предсказуемость. Время ответа ограничено длиной ввода и количеством подсказок, независимо от размера словаря. Именно поэтому на собеседованиях так ценят фразу: «Я бы использовал Trie для поиска по префиксу».

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

Практическое задание: добавьте top_k

Попробуйте расширить класс Trie методом top_k(prefix, k), который возвращает k самых частотных слов с данным префиксом. Для этого вам понадобится хранить счётчик частоты в каждом узле. Протестируйте на наборе названий фильмов и посмотрите, как быстро вы получите топ-5 подсказок.

Если возникнут вопросы или захотите поделиться решением — пишите в комментариях! Удачи в ваших алгоритмических приключениях! 🚀