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

Trie из семи слов: зелёные узлы — конец слова
Trie из семи слов: зелёные узлы — конец слова

Проблема: запросы по префиксу

«Какие слова начинаются на ca?» set слов отвечает на вопрос «есть ли здесь car?» за O(L), но для вопроса о префиксе нужно просмотреть все n слов: O(n · L). Trie отвечает, спускаясь по префиксу и собирая то, что лежит ниже.

Структура и базовые операции

Узел хранит словарь children (буква → дочерний узел) и флаг end: здесь заканчивается слово. Флаг нужен, потому что префикс ещё не слово: ca есть в дереве как часть car и cat, но не вставлялось.

python
class TrieNode:
    def __init__(self):
        self.children = {}          # letter -> TrieNode
        self.end = False            # a word ends here

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

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.end = True

    def _walk(self, s):
        node = self.root
        for ch in s:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.end

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

trie = Trie()
for w in ["car", "care", "cart", "cat", "do", "dog", "dot"]:
    trie.insert(w)

print(trie.search("car"), trie.search("ca"))
print(trie.starts_with("ca"), trie.starts_with("cb"))
text
True False
True False