• 트리구조이다
• 문자열을 저장하고 효율적으로 탐색할 수 있다.
• 최하위 노드는 전체 문자열을 가지고 있다.

특징

• 자동완성, 문자 찾기 등 문자열 검색에 유용하다

• 문자열 길이만큼 시간 복잡도가 걸린다

• 정점이 자식에 대한 링크를 전부가지고 있어야한다.

  ⇒ 저장 공간이 그만큼 소비된다.

구조

• 루트는 비어있다
• 간석은 추가 될 문자를 키로 가진다
• 각 정점은 이전 정점의 값 + 간선을 키 값으로 가진다.

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