Что такое 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 может быть большим.