트라이(Trie) - 효율적인 문자열 검색을 위한 자료구조

들어가며

각종 웹 서비스와 애플리케이션에서는 사용자의 검색어 입력에 대해 빠르게 응답해야 합니다. 이러한 요구를 충족시키는 데 효과적인 자료구조 중 하나가 바로 '트라이(Trie)'입니다.

 

이번 시간에는 트라이 자료구조에 대해서 알아보겠습니다.

 

트라이가 뭔데?

트라이는 문자열의 집합을 저장하고, 주어진 문자열을 빠르게 찾는 데 특화된 트리 기반의 자료구조입니다. 각 노드는 문자를 저장하며, 루트에서 어떤 노드까지의 경로를 따라 내려가며 만나는 문자들을 모으면 해당 경로에 대응되는 문자열을 얻을 수 있습니다.

 

예를 들어 문자열이 'be', 'bee', 'bar', 'car', 'cat'인 경우 트라이의 구조는 다음과 같습니다.

 

    root
   /    \
  b      c
 /|      |
e a      a
| |     / \
e r    r   t

 

그래서 뭐가 좋은 걸까?

트라이의 주요 장점은 다음과 같습니다.

• 빠른 검색 속도
  트라이는 문자열 데이터를 빠르게 검색할 수 있습니다. 문자열의 길이가 M이라면, O(M)의 시간 복잡도를 가집니다.
• 접두사 검색 용이
  트라이는 접두사로 시작하는 모든 문자열을 쉽게 찾을 수 있습니다. 접두사를 기반으로 트리가 형성되기 때문입니다.

 

그래도 완벽하지는 않다

물론 트라이도 다음과 같은 단점을 가지고 있습니다.

• 메모리 사용량
  트라이는 각 노드에서 가능한 모든 문자에 대한 참조를 유지해야 하므로, 사용하지 않는 참조에 대한 메모리가 낭비될 수 있습니다. 또한, 트라이는 공통 접미사를 공유하지 않기 때문에, 이러한 문자열의 집합을 저장하는 경우에는 메모리 사용량이 더욱 증가하게 됩니다. 특히, 대량의 데이터를 저장할 때 문제가 될 수 있습니다.

 

구현 코드

아래는 트라이를 자바스크립트로 구현한 코드입니다.

 

class TrieNode {
  constructor() {
    this.children = {};
    this.isTerminal = false;
  }
}

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

  insert(key) {
    let node = this.root;

    for (let i = 0; i < key.length; i++) {
      const ch = key[i];
      if (!(ch in node.children)) node.children[ch] = new TrieNode();

      node = node.children[ch];
    }
    node.isTerminal = true;
  }

  isPrefixExist(key) {
    let node = this.root;

    for (let i = 0; i < key.length; i++) {
      const ch = key[i];
      if (!(ch in node.children)) return false;

      node = node.children[ch];
    }

    return true;
  }

  isStringExist(key) {
    let node = this.root;

    for (let i = 0; i < key.length; i++) {
      const ch = key[i];
      if (!(ch in node.children)) return false;

      node = node.children[ch];
    }

    return node.isTerminal ? true : false;
  }
}

 

각 메서드는 트리의 루트부터 시작해 내려가며 진행합니다.

• isTerminal
  단어의 마지막을 나타냅니다.
• insert(key)
  새 문자열을 트라이에 저장합니다. 마지막 노드의 isTerminal의 값을 true로 설정합니다.
• isPrefixExist(key)
  해당 문자열을 접두사로 가지고 있는지 확인합니다. 문자열의 모든 문자를 따라 노드를 탐색했다면 true를 반환합니다.
• isStringExist(key)
  해당 문자열이 트라이에 존재하는지 확인합니다. 문자열의 모든 문자를 따라 노드를 탐색했을 때 마지막 노드의 isTerminal 값이 true라면 true를 반환합니다.
  

 

마치며

트라이는 문자열 검색과 관련된 문제를 마주하며 처음 접하게 된 자료구조인데요.

문자열을 검색하는 데 특화된만큼 이를 잘만 활용한다면 효율적으로 문제를 해결할 수 있습니다.

다만 상황에 따라 메모리 사용량이 클 수 있으니 유의하셔야겠습니다.

 

지적이나 다른 의견은 언제나 환영합니다 :D

감사합니다.

 

Reference

https://en.wikipedia.org/wiki/Trie