Trie (Префиксное дерево)

Что такое Trie

Trie (от retrieval) — дерево поиска, в котором ключ не хранится в узле явно, а определяется путём от корня до узла. Каждый узел представляет один символ, а путь от корня до листа образует слово.

Придумано Эдвардом Фредкином в 1960 году.

Основные свойства

Структура узла

┌──────────────────────────────────┐
│  children[0..A-1]                │  ← A указателей (A = размер алфавита)
│  is_end: bool                    │  ← маркер конца слова
│  value: any  (опционально)       │  ← полезная нагрузка
└──────────────────────────────────┘

Визуализация

Вставлены слова: cat, car, card, care, bat, bad

✓ = is_end = true — здесь заканчивается слово

Основные операции

➕ Вставка — O(m)

Вставка "care":
  root → c → a → r → e (is_end = true)

Если узел уже существует — просто идём дальше.
Если нет — создаём новый.

def insert(root, word):
    node = root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
    node.is_end = True

🔍 Поиск — O(m)

Поиск "car":
  root → c ✓ → a ✓ → r ✓ → is_end? → True ✓

Поиск "ca":
  root → c ✓ → a ✓ → is_end? → False ✗ (есть как префикс, но не слово)

Поиск "cat":
  root → c ✓ → a ✓ → t ✓ → is_end? → True ✓

def search(root, word):
    node = root
    for char in word:
        if char not in node.children:
            return False       # символ не найден
        node = node.children[char]
    return node.is_end         # True только если полное слово

🔍 Поиск префикса — O(m)

def starts_with(root, prefix):
    node = root
    for char in prefix:
        if char not in node.children:
            return False
        node = node.children[char]
    return True   # префикс существует (слова необязательно)

➖ Удаление — O(m)

Рекурсивный обход: удаляем узел только если он не является предком другого слова.

Удаление "car" (но "card", "care" остаются):
  → узел r НЕ удаляем — у него есть дети (d, e)
  → просто сбрасываем is_end = false

Сложность операций

Плюсы и минусы