Skip to main content

Префиксное дерево

Определение​

Trie (дерево префиксов) — это структура данных, которая используется для хранения строк. В каждом узле trie хранится символ строки, а все пути от корня к узлу представляют собой строку символов, образующихся на этом пути.

Пример дерева trie:

    (root)
   /  |  \
  c   d   a
 /    |    \
a     o     r

Применение​

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

Построение Trie​

Для построения trie из массива строк используется следующий алгоритм:

class TrieNode {
  constructor() {
    this.data = null;
    this.children = new Map();
  }
}

let buildTrie = (words) => {
  let root = new TrieNode();
  for (const word of words) {
    let curr = root;
    for (const c of word) {
      if (!curr.children.has(c)) {
        curr.children.set(c, new TrieNode());
      }
      curr = curr.children.get(c);
    }
  }

  return root;
};
  1. Создаётся корневой узел.
  2. Для каждой строки последовательно добавляются символы в виде узлов, создавая ветвления в дереве.
  3. Если символ уже присутствует в текущем узле, переходим к следующему символу.
  4. В конце строки добавляется специальный маркер, обозначающий завершение слова.

Временная сложность​

Построение trie занимает O(n⋅k) времени, где:

  • n — количество слов в массиве,
  • k — средняя длина строк.

После построения trie можно использовать его для очень эффективного поиска строк и сопоставления шаблонов.

Задачи​

https://leetcode.com/problems/search-suggestions-system/description/
https://leetcode.com/problems/implement-trie-prefix-tree/description/