re:re:actable
Урок 073 минуты чтения

Что такое trie / prefix tree?

На этой странице
Кратко

Trie, или prefix tree, - дерево для хранения строк по символам. Оно удобно для задач на префиксы, словари, autocomplete, word search и проверку наличия слова.

Вопрос

Что такое Trie, зачем он нужен и как его реализовать в JavaScript/TypeScript?

Основная идея

Обычное дерево хранит значения в узлах. Trie хранит строку как путь от корня к символам.

Например, слова:

cat
car
dog

Можно представить так:

root
 ├─ c
 │  └─ a
 │     ├─ t *
 │     └─ r *
 └─ d
    └─ o
       └─ g *

* означает конец слова.

Зачем нужен isEnd

Если в trie есть путь:

c -> a -> r

это может означать слово car.

Но если есть слово card, путь c -> a -> r тоже существует. Поэтому нужен флаг:

isEnd = true

Он говорит: здесь заканчивается полное слово.

Реализация

class TrieNode {
  children = new Map<string, TrieNode>()
  isEnd = false
}
 
class Trie {
  private root = new TrieNode()
 
  insert(word: string): void {
    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.isEnd = true
  }
 
  search(word: string): boolean {
    const node = this.findNode(word)
    return Boolean(node?.isEnd)
  }
 
  startsWith(prefix: string): boolean {
    return Boolean(this.findNode(prefix))
  }
 
  private findNode(value: string): TrieNode | null {
    let node = this.root
 
    for (const char of value) {
      const next = node.children.get(char)
 
      if (!next) {
        return null
      }
 
      node = next
    }
 
    return node
  }
}

Методы

МетодЧто делаетСложность
insert(word)добавляет словоO(L)
search(word)проверяет полное словоO(L)
startsWith(prefix)проверяет префиксO(P)

L - длина слова, P - длина префикса.

Пример использования

const trie = new Trie()
 
trie.insert("cat")
trie.insert("car")
 
console.log(trie.search("cat")) // true
console.log(trie.search("ca")) // false
console.log(trie.startsWith("ca")) // true

Где нужен Trie

  • autocomplete;
  • проверка префиксов;
  • поиск слов в grid;
  • словарь;
  • replace words;
  • word break;
  • longest common prefix;
  • wildcard search, если добавить DFS.

Когда Trie лучше Set

Set хорош для полного слова:

words.has("cat")

Но для префикса:

есть ли слово, начинающееся на "ca"?

Set придется обходить целиком, а Trie пройдет только символы префикса.

Сложность и память

Время операций зависит от длины строки, а не от количества слов:

insert/search/startsWith: O(length)

Память:

O(total number of characters)

Trie может потреблять много памяти, потому что каждый узел хранит Map.

Что важно помнить: частые ошибки

  • Забыть isEnd и считать любой префикс словом.
  • Использовать search там, где нужен startsWith.
  • Не учитывать память.
  • Путать Trie и binary tree.
  • Считать сложность O(1), хотя она зависит от длины слова.
  • Не обрабатывать пустую строку, если задача ее допускает.

Что отвечать на собеседовании?

Trie - это prefix tree для строк. Каждый путь от корня соответствует последовательности символов, а флаг isEnd отмечает конец полного слова. Основные операции insert, search и startsWith работают за O(L), где L - длина слова или префикса. Trie полезен для autocomplete, словарей и задач на префиксы, но требует дополнительной памяти.

Мини-шпаргалка

  • Trie = дерево символов.
  • Путь = строка.
  • isEnd = здесь заканчивается слово.
  • insert - добавить слово.
  • search - полное слово.
  • startsWith - префикс.
  • Time O(length).
  • Space может быть большим.

Документация

Wikipedia: Trie.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам