트라이

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다. 따라서 검색어 자동완성이나 사전 찾기 등에 응용된다. 문자열의 길이가 $n$일 때 탐색, 삽입은 $O(n)$만큼 걸린다. 각 정점이 자식에 대한 링크를 전부 갖고 있어 저장공간을 더 많이 사용한다.

트라이의 루트 노드는 비어있다. 각 간선은 추가될 문자를 키로 가지며, 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가진다. 해시 테이블과 연결 리스트를 이용하여 구현할 수 있다.

구현

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

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

const trie = new Trie();

자식으로 추가할 노드와 트라이의 뼈대부터 코드를 짜봤다. 우선 트라이의 루트 노드는 비어있으므로 아무런 값이 없는 노드로 할당한다.

삽입

class Trie {
  // ... code
  
  insert(string) {
    if (typeof string !== "string") {
      console.log("Please enter a string");
      return;
    }
    
    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('abce');
trie.insert('abcf');
trie.insert('abdg');
trie.insert('apple');
trie.insert('banana');

단어의 추가(삽입)할 때의 코드이다. 받은 단어 string의 반복문을 돌려 현재 노드의 자식(currentNode.children) 중에 각 철자들이 있는지 차례대로 확인한다. 만약 있다면 현재 노드(currentNode)를 그 자식 노드의 값으로 재할당하고, 없다면 해당 철자를 키로 하고 이전 값들의 문자열과 현재 철자를 더하여 값으로 저장한다.

위의 경우에 트라이 그래프의 모양은 다음과 같다. 키 값으로 노드를 표현했다. 각 노드의 값은 루트 노드부터 내려오는 경로의 키 값을 다 더한 것이다.

                ''(root)
          a                  b
     b        p              a
  c     d       p            n
e  f      g       l          a
                    e        n
                             a

자동완성

문자를 입력받았을 때, 그 문자로 만들 수 있는 단어들을 나열한다. 검색창에 입력을 했을 때 자동완성 되는 원리를 구현해보았다.

문자열을 받아 그 문자열의 자동완성을 기대했을 때, 문자열의 값을 가진 노드부터 자식이 없을 때까지 순회(dfs)하여 트라이에 저장된 단어들을 전부 반환해야 한다.

                ''(root)
          a                  b
     b        p              a
  c     d       p            n
e  f      g       l          a
                    e        n
                             a

예를 들어, 위와 같이 트라이에 단어들을 삽입했을 때, abc까지 입력을 받았다면, abce, abcf가 자동완성의 결과로 반환되어야 한다.

class Trie {
  // ... code
  
  traverse(node, dic) {
    if (node.children.size) {
      for (const [key, _] of node.children) {
        this.traverse(node.children.get(key), dic);
      }
    } else dic.push(node.value);
  }
  
  autoComplete(string) {
    if (!string) {
      console.log("Please enter a word");
      return;
    }
    
    let dic = [];
    let currentNode = this.root;
    
    // 받은 단어 노드까지 이동
    for (const char of string) {
      if (!currentNode.children.has(char)) {
        console.log("No word found");
        return;
      }
      currentNode = currentNode.children.get(char);
    }
    
    // 순회
    for (const [key, _] of currentNode.children) {
      this.traverse(currentNode.children.get(key), dic);
    }
    dic.sort();
    console.log(dic);
  }
}

const trie = new Trie();

입력받은 문자열과 노드의 값이 일치하는 노드에서부터 모든 자식을 순회하여 값을 가져와야 하기 때문에 재귀함수를 이용하여 구현해보았다.

우선 입력받은 문자열을 for 반복문을 통해 입력받은 문자열과 노드의 값이 일치하는 노드까지 내려간다. 만약 입력받은 문자열이 트라이에서 더 이상 찾을 수 없다면(자동 완성할 수 있는 경우가 존재하지 않는다면) return 문을 통해 for문을 포함한 함수를 종료한다.

반복문이 종료된 이후에 순회는 currentNode의 자식들부터 시작해야 한다. 현재 노드의 자식들을 순회하며 자식이 없을 때까지 순회가 되도록 헬퍼 메소드 traverse를 선언해 재귀함수를 만든다. 종료 조건은 자식이 없을 때로 size 프로퍼티를 통해 구분했다. 받은 노드의 자식이 있다면 다시 자식들을 순회하며 재귀를 돌려 자식이 없을 때까지 간다. 자식이 없다면 트라이에 저장된 단어가 완성되었다는 뜻으로 배열에 삽입한다.

위 예시와 같이 다음과 같은 구조로 트라이를 만들었다고 가정한다.

                ''(root)
          a                  b
     b        p              a
  c     d       p            n
e  f      g       l          a
                    e        n
                             a

그리고 다음 문자열을 자동 완성 메서드의 인수로 넣었을 때 출력되는 값은 다음과 같다.

trie.autoComplete(''); // Please enter a word

trie.autoComplete('a'); // [ 'abce', 'abcf', 'abdg', 'apple' ]

trie.autoComplete('ab'); // [ 'abce', 'abcf', 'abdg' ]

trie.autoComplete('abc'); // [ 'abce', 'abcf' ]

trie.autoComplete('abzaaaaa'); // []

---

만약 제가 고려하지 못한 부분이 있다면 알려주세요, 감사합니다 :)