트라이 Trie

• 기본적으로 K진 트리의 구조를 가진다.
• 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.
• 자동완성 기능, 사전 검색 등 문자열 탐색에 특화된 자료구조이다.

장점

• 문자열 검색을 빠르게 수행할 수 있다.
• 문자열 탐색시, 전부 비교하면서 탐색하는 것보다 효율적으로 찾을 수 있다.

단점

• 각 노드에서 자식들의 포인터를 배열로 모두 포함하고 있으므로, 저장 공간을 많이 사용한다. 따라서, 메모리 측면에서 비효율적일 수 있다.

기본 구조

하나의 노드는 다음과 같이 구성된다.

현재 문자를 담을, 혹은 현재까지의 문자열을 저장할 value ,
현재 문자에서 끝나는 문자열이 있는지를 저장할 end ,
더 이어지는 문자열이 있다면, 해당 노드를 저장하는 children 으로 구성된다.

자바스크립트 코드로 나타내면 다음과 같다.

class Node {
  constructor(value = "") {
    this.value = value; // 현재까지의 문자열을 저장.
    this.end = false;	// 해당 노드에서 끝나는 문자열이 있는지.
    this.children = {}; // 더 연결되는 문자열들의 노드를 저장.
  }
}

go, gone, guild 를 차례로 담아보자.

우선 root 노드부터 시작해서 g , o 순으로 연결하게 된다.
기존에 go와 o가 없기 때문에 노드를 생성해서 연결한다.

다음으로, gone 과 guild 를 넣으면

value는 위와 같이 현재까지의 문자열을 저장하기도 하고, 각 원소를 저장하기도 하는 것 같다.
현재 상황에서 더 참조하기 쉬운 형태로 저장하면 될 것 같다.

자바스크립트로 구현

위와 같은 구조를 자바스크립트로 구현해보자.

class Trie {
  constructor() {
    this.root = new Node() // root는 빈 노드를 하나 만든다.
  }
  
  // 새 단어 추가
  insert(string) {
    let curNode = this.root; // root노드를 시작으로 현재까지의 문자열과 일치하는 노드가 존재하는 지 확인하며 삽입한다.
    
    for (let i=0; i<string.length; i++) {
      const currentChar = string[i];
      
      if (curNode.children[currentChar] === undefined) {
        curNode.children[currentChar] = new Node(curNode.value + currentChar);
        // curNode.child[currentChar] = new Node(currentChar); -> 각 자리 요소만 저장하는 경우.
      }
      
      curNode = curNode.children[currentChar];
    }
    currentNode.end = true; // 마지막 원소까지 저장한 후에는 끝나는 단어가 생긴 것이므로 true로 변경
  }
  
  // 단어 존재 여부 확인
  search(string) {
    let curNode = this.root;
    
    for (let i=0; i<string.length; i++) {
      let currentChar = string[i];
      if (curNode.children[currentChar]) {
        curNode = curNode.children[currentChar];
      } else {
        return false;
      }
    }
    // 문자열을 순차적으로 모두 도는데 성공한 경우
    return true;
  }
}

문자열 검색이나, 자동완성 등을 구현할 때에 이를 적용하면,
문자열 집합의 개수와 상관없이 찾고자 하는 문자열의 길이가 n이라면 시간복잡도도 O(n)이라고 한다.

따라서, 다른 구조보다 빠르게 문자열을 찾을 수 있다.

참고자료

위키백과 트라이 (컴퓨팅)
Implementing a Trie in JavaScript Part 1
teihong93님의 자바스크립트를 이용한 Trie 구현