트라이(Trie)

트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다.

각 간선은 새롭게 추가되는 정보를 가지고 있고 정점은 이전 정점으로부터 더해진 문자열 정보를 갖습니다.

특징

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

• L이 문자열의 길이일 때 탐색, 삽입은 O(L)만큼 걸린다.
  보통 문자열을 탐색할 때 문자열의 개수 * 각 문자열의 길이만큼 시간복잡도를 갖는다.
  반면 트라이를 이용하면 찾는 문자열의 길이만큼만 시간복잡도를 갖는다.

• 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적이다.

• 각 정점이 자식에 대한 링크를 전부 가지고 있기때문에 저장 공간을 더 많이 사용한다.

  

트라이 구조

• 루트는 비어있다.
• 각 간선(링크)은 추가될 문자를 키로 가진다.
• 각 정점은 이전 정점의 값 + 간선의 키값
• 해시 테이블과 연결리스트를 사용하여 구현할 수 있다.

빈 루트 정점만 존재

tea를 추가

맨 앞 문자열 't'를 잘라 루트 정점의 자식으로 추가

맨 앞 문자열 'e'를 잘라 t 정점의 자식으로 추가한다.

맨 앞 문자열 'a'를 잘라 te정점의 자식으로 추가한다

만약 역기서 'ten'을 추가하면 어떻게 될까요?

맨 앞 문자열을 자르면 't', 'e', 'n'이며 이중 't'와 'e'는 이미 간선이 존재하고
'n'의 간선이 없기때문에 분기가 생깁니다.

JavaScript 구현

class Node {
  constructor(value = "") {
    this.value = value;
    this.children = new Map();
  }
}

class Trie {
  constructor() {
    this.root = new Node();
  }

  insert(string) {
    let currNode = this.root;

    for (const char of string) {
      if (!currNode.children.has(char)) {
        currNode.children.set(char, new Node(currNode.value + char));
      }

      currNode = currNode.children.get(char);
    }
  }

  has(string) {
    let currNode = this.root;

    for (const char of string) {
      if (!currNode.children.has(char)) {
        return false;
      }
      currNode = currNode.children.get(char);
    }

    return true;
  }
}

const trie = new Trie();
trie.insert("ten");
trie.insert("tea");
console.log(trie.has("ten")); // true
console.log(trie.has("tea")); // true
console.log(trie.has("tap")); // false