자동완성, 문자 찾기 등 문자열 검색에 유용하다
문자열 길이만큼 시간 복잡도가 걸린다
정점이 자식에 대한 링크를 전부가지고 있어야한다.
⇒ 저장 공간이 그만큼 소비된다.
class Node {
constructor(value = '') {
this.value = value;
this.children = new Map();
}
}
class Trie {
constructor() {
this.root = new Node();
}
insert(string) {
let currentNode = this.root;
for (const char of string) {
if (!currentNode.children.has(char)) {
currentNode.children.set(char, new Node(currentNode.value + char));
}
currentNode = currentNode.children.get(char);
}
}
has(string) {
let currentNode = this.root;
for (const char of string) {
if (!currentNode.children.has(char)) return false;
currentNode = currentNode.children.get(char);
}
return true;
}
}
const trie = new Trie();
trie.insert('cat');
trie.insert('dog');
console.log(trie.has('c'));//true
console.log(trie.has('ca'));//true
console.log(trie.has('cat'));//true
console.log(trie.has('cag'));//false
console.log(trie.has('d'));//true
console.log(trie.has('do'));//true
console.log(trie.has('dog'));//true
console.log(trie.has('dot'));//false