Trie (Префиксное дерево)
Когда применять:
- Автокомплит (Autocomplete).
- Поиск слов по префиксу.
- Проверка наличия слова в словаре.
- Spell checker.
Шаблон реализации
class TrieNode {
constructor() {
this.children = {}; // { 'a': TrieNode, 'b': TrieNode ... }
this.isEnd = false; // Конец слова?
}
}
class Trie {
constructor() { this.root = new TrieNode(); }
// Вставка слова: O(L), L - длина слова
insert(word) {
let node = this.root;
for (const char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
node.isEnd = true;
}
// Поиск слова целиком
search(word) {
let node = this.root;
for (const char of word) {
if (!node.children[char]) return false;
node = node.children[char];
}
return node.isEnd;
}
// Поиск префикса (starts with)
startsWith(prefix) {
let node = this.root;
for (const char of prefix) {
if (!node.children[char]) return false;
node = node.children[char];
}
return true;
}
}