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

Trie (prefix tree) — древовидная структура данных для хранения строк, где каждый узел соответствует одному символу, а путь от корня до узла образует префикс хранимых слов.

Зачем нужно

Trie позволяет искать слово в словаре за O(m), где m — длина слова, независимо от числа слов в словаре. Это делает его идеальным для автодополнения, проверки орфографии и поиска по префиксу. Хеш-таблица даёт O(m) на поиск, но не поддерживает префиксные запросы.

Где используется

  • Автодополнение в поисковых движках и IDE
  • Проверка орфографии в текстовых редакторах
  • Маршрутизация IP-адресов (longest prefix match)
  • Словарный сжатый поиск в задачах CP
  • Реализация словарей с быстрым поиском по префиксу

Основной контент

Структура

Слова: ["cat", "car", "card", "care", "bat"]

         root
        /    \
       c      b
       |      |
       a      a
      / \     |
     t   r    t
         |\ 
         d  e

Каждый узел хранит:

  • children — Map/объект дочерних узлов (по символу)
  • isEnd — флаг конца слова

Реализация

class TrieNode {
  constructor {
    this.children = {};
    this.isEnd = false;
  }
}

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

  // Вставка слова — O(m)
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) {
        node.children[ch] = new TrieNode();
      }
      node = node.children[ch];
    }
    node.isEnd = true;
  }

  // Поиск слова — O(m)
  search(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) return false;
      node = node.children[ch];
    }
    return node.isEnd;
  }

  // Поиск по префиксу — O(m)
  startsWith(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children[ch]) return false;
      node = node.children[ch];
    }
    return true;
  }

  // Все слова по префиксу — O(m + k), k — число совпадений
  autocomplete(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children[ch]) return ;
      node = node.children[ch];
    }
    const results = ;
    this._dfs(node, prefix, results);
    return results;
  }

  _dfs(node, current, results) {
    if (node.isEnd) results.push(current);
    for (const [ch, child] of Object.entries(node.children)) {
      this._dfs(child, current + ch, results);
    }
  }
}

const trie = new Trie();
["cat", "car", "card", "care", "bat"].forEach(w => trie.insert(w));
console.log(trie.search("car"));        // true
console.log(trie.startsWith("ca"));     // true
console.log(trie.autocomplete("car"));  // ["car", "card", "care"]

Сложность

Операция Время Память
Вставка O(m) O(m) на слово
Поиск O(m) —
Поиск по префиксу O(m) —
Хранение n слов средней длины m — O(n·m)

Частые ошибки

  • Хранить children в массиве фиксированного размера 26 (для ASCII) — расточительно для Unicode; лучше Map или объект.
  • Не устанавливать isEnd = true при вставке — поиск будет возвращать false для реальных слов.
  • Путать search (точное совпадение) и startsWith (наличие префикса) — распространённая ошибка в задачах LeetCode.
  • Не удалять узлы при удалении слова — память не освобождается.

Связанные темы

Ресурсы