[DA] Trie

Trie

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조

검색어 자동완성, 사전 찾기 등에 응용

구조

1. 루트는 비어있다.
2. 각 간선(링크)은 추가될 문자를 키로 가짐
3. 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가짐
4. 해시 테이블, 연결 리스트를 이용하여 구현

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('bee');
trie.insert('tea');
console.log(trie.has('bee'));
console.log(trie.has('test'));