Trie (префиксное дерево): структура, на которой работает автодополнение

Проблема, которую не решает хеш-таблица

Представьте поисковую строку. Пользователь набирает «алго», и нужно мгновенно показать все слова словаря, начинающиеся с этих букв: «алгоритм», «алгоритмический», «алгебра» отсеять.

Хеш-таблица здесь бессильна. Она отвечает на вопрос «есть ли такое слово целиком» за O(1), но вопрос «какие слова начинаются с этого префикса» требует перебрать все ключи. Хеш от «алго» и хеш от «алгоритм» никак не связаны — в этом сама суть хеширования.

Trie (произносится «трай», от retrieval) решает ровно эту задачу. Слова хранятся так, что общий префикс лежит в общем месте.

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

Каждый узел — это символ. Путь от корня до узла складывается в префикс. Отдельный флаг отмечает узлы, где заканчивается настоящее слово.

Положим в дерево слова cat, car, card, dog:

        (root)
        /    \
       c      d
       |      |
       a      o
      / \     |
     t   r    g*
     *   *
         |
         d*

* — здесь заканчивается слово

Обратите внимание на несколько вещей.

Слова car и card делят весь путь c → a → r, и card просто продолжает его. Узел r помечен как конец слова, и одновременно у него есть потомок.

Узел a концом слова не помечен — «ca» не слово, это просто промежуточный префикс. Именно поэтому флаг обязателен: без него нельзя отличить реальное слово от куска чужого.

Реализация

class TrieNode {
  constructor() {
    this.children = new Map(); // символ → TrieNode
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;

    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char);
    }

    node.isEndOfWord = true;
  }

  // проходим по пути и возвращаем узел или null
  _traverse(prefix) {
    let node = this.root;

    for (const char of prefix) {
      if (!node.children.has(char)) return null;
      node = node.children.get(char);
    }

    return node;
  }

  // есть ли такое слово целиком
  search(word) {
    const node = this._traverse(word);
    return node !== null && node.isEndOfWord;
  }

  // есть ли хоть одно слово с таким префиксом
  startsWith(prefix) {
    return this._traverse(prefix) !== null;
  }
}

const trie = new Trie();
['cat', 'car', 'card', 'dog'].forEach((w) => trie.insert(w));

trie.search('car');       // true
trie.search('ca');        // false — это префикс, а не слово
trie.startsWith('ca');    // true
trie.startsWith('cab');   // false

Вынесенный метод _traverse избавляет от дублирования: search и startsWith отличаются ровно одной проверкой флага. Это мелочь, но на собеседовании такие вещи замечают.

Аналог на Python:

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

    def __init__(self) -> None:
        self.children: dict[str, 'TrieNode'] = {}
        self.is_end = False


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

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            node = node.children.setdefault(char, TrieNode())
        node.is_end = True

    def _traverse(self, prefix: str) -> TrieNode | None:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

    def search(self, word: str) -> bool:
        node = self._traverse(word)
        return node is not None and node.is_end

    def starts_with(self, prefix: str) -> bool:
        return self._traverse(prefix) is not None

__slots__ здесь не украшательство: узлов в дереве бывают сотни тысяч, и отказ от __dict__ у каждого экземпляра заметно экономит память.

Сложность

Пусть L — длина слова, n — количество слов в словаре.

Самое ценное здесь — время не зависит от количества слов. Поиск в словаре из миллиона слов занимает столько же, сколько в словаре из десяти, если длина слова одинакова.

Собираем все слова по префиксу

Это то, ради чего Trie обычно и берут. Дошли до узла-префикса, дальше обходим поддерево в глубину и собираем все отмеченные узлы.

autocomplete(prefix, limit = 10) {
  const node = this._traverse(prefix);
  if (node === null) return [];

  const results = [];

  const dfs = (current, path) => {
    if (results.length >= limit) return;

    if (current.isEndOfWord) {
      results.push(prefix + path);
    }

    for (const [char, child] of current.children) {
      dfs(child, path + char);
      if (results.length >= limit) return;
    }
  };

  dfs(node, '');
  return results;
}

trie.autocomplete('ca'); // ['cat', 'car', 'card']

Ограничение limit тут не для красоты. В реальном автодополнении по префиксу «а» могут найтись сотни тысяч слов, и собирать их все — верный способ положить сервис.

Удаление: место, где обычно ошибаются

Удалить слово — не значит просто снять флаг. Если после этого узлы стали никому не нужны, их надо убрать, иначе дерево будет разрастаться мусором. Но убирать можно только те узлы, у которых нет детей и которые не являются концом другого слова.

delete(word) {
  const removeFrom = (node, index) => {
    if (index === word.length) {
      if (!node.isEndOfWord) return false; // слова и не было
      node.isEndOfWord = false;
      // узел можно удалять, только если он бездетный
      return node.children.size === 0;
    }

    const char = word[index];
    const child = node.children.get(char);
    if (!child) return false;

    const shouldRemoveChild = removeFrom(child, index + 1);

    if (shouldRemoveChild) {
      node.children.delete(char);
      // сам узел удаляем, если он опустел и не конец другого слова
      return node.children.size === 0 && !node.isEndOfWord;
    }

    return false;
  };

  removeFrom(this.root, 0);
}

Проверьте на примере: удаляем card из дерева с car и card. Узел d уходит, а узел r остаётся — он помечен как конец слова car. Именно это и проверяет условие !node.isEndOfWord.

Массив вместо словаря

Если алфавит фиксирован и мал (например, только строчные латинские буквы), вместо Map часто берут массив на 26 элементов:

class TrieNode {
  constructor() {
    this.children = new Array(26).fill(null);
    this.isEndOfWord = false;
  }
}

// индекс символа
const idx = char.charCodeAt(0) - 'a'.charCodeAt(0);

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

На собеседовании стоит проговорить этот компромисс: он показывает, что вы думаете о характере данных, а не заучили одну реализацию.

Где применяется на практике

Автодополнение и поисковые подсказки — прямое назначение.

Проверка орфографии — быстро понять, есть ли слово в словаре, и предложить близкие варианты.

IP-маршрутизация — таблицы маршрутов ищут самый длинный совпадающий префикс адреса, и это буквально работа Trie.

Фильтрация запрещённых слов — алгоритм Ахо-Корасик, который ищет сразу много образцов в тексте, построен поверх префиксного дерева.

T9 и клавиатурный ввод — исторически один из первых массовых примеров.

Когда Trie не нужен

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

Ещё один минус — накладные расходы на объекты. Каждый узел это отдельный объект со своей ссылочной структурой, и на больших словарях память расходуется заметно. Если словарь статичен и огромен, стоит посмотреть в сторону сжатых вариантов вроде radix tree или DAWG.

Что запомнить

• Trie хранит слова по символам, общий префикс лежит в общем пути.
• Флаг конца слова обязателен: без него «ca» не отличить от «cat».
• Все операции — O(длины слова), независимо от размера словаря.
• При удалении убирайте только бездетные узлы, не являющиеся концом другого слова.
• Массив вместо словаря — быстрее, но прожорливее по памяти.
• Для точного поиска без префиксов хеш-таблица лучше.

Закрепите на практике

Хорошее упражнение на ту же мышцу — поиск слова в матрице символов. Задача решается перебором с возвратом, а если слов много, то именно префиксное дерево превращает её из безнадёжной в решаемую.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→