트라이(Trie): 문자열 탐색과 저장을 효율적으로 만들어주는 자료구조

트라이는 트리 기반의 자료 구조로 문자열의 탐색을 효율적으로 수행할 수 있도록 도와줍니다. 특히 공통 접두사를 공유하는 데이터를 다룰 때 유용하여 자동완성, 사전 검색 등 주로 문자열의 탐색에서 많이 응용하는 자료 구조입니다.

트라이(Trie)

자동완성 혹은 사전의 단어 검색에서 검색창에 어떤 문자를 입력하면 해당 문자로 시작하는 단어를 찾아주어야 합니다. 예를 들어 영어 사전에서 "prefix"라는 단어를 찾을 때 p, r, e, f, i, x의 문자들을 순서대로 입력할 것입니다. 그러면 각 입력마다 "p"로 시작하는 단어들, "pr"로 시작하는 단어들, "pre"로 시작하는 단어들 ... 을 사용자가 완성할 단어로 판단하며 단어를 미리 완성하여 아래에 표시해 줍니다. 이를 컴퓨터에서 효율적으로 검색할 수 있도록 트리를 기반으로 트리에서의 각 노드의 위치를 통해 키를 정의하고 필요한 값을 찾을 수 있도록 만든 것이 트라이 구조입니다.

트라이의 구조와 작동방식

트라이는 기본적으로 트리 기반의 자료 구조로, 각 노드가 개별적인 키를 가지지 않고 트리에서의 위치를 통해 키가 정의됩니다. 각 데이터는 각 노드에 직접 저장되지 않고 트리를 따라 타고 내려가는 경로에 분산되어 저장됩니다. 따라서 루트부터 데이터의 마지막까지의 경로가 해당 데이터의 키가 됩니다. 해당 키 자체가 저장하고 싶은 문자열이 될 수 있고 그렇지 않은 경우 마지막 노드에 데이터를 저장하게 됩니다.

https://excalidraw.com/에서 그린 Trie 구조

 

저장된 문자를 찾기 위해서는 루트노드부터 시작하여 루트의 자식들을 순회하며 마지막 문자까지 경로를 따라 탐색을 계속합니다. 마지막 문자를 만났을 때, 해당 경로까지 지나온 노드에 저장된 문자의 값을 합치면 저장된 문자를 알 수 있습니다. 만약 poem과 poet이라는 단어가 저장되어 있다면 (각 노드 당 하나의 문자만을 저장할 시에는) p → o → e → m까지 찾아가고 여기서 m 노드를 찾아가면 "poem", t노드를 찾아가면 "poet"이라는 단어를 찾을 수 있을 것입니다. 여기서 볼 수 있듯이 저장된 데이터들은 접두사가 같다면 같은 부분을 중복하여 저장하지 않고 공유하기 때문에 메모리를 효율적으로 사용할 수 있습니다.

구현하기

트라이는 기본적으로 트리 구조입니다. 여기서는 한 노드에 하나의 글자만을 저장하는 간단한 방식으로 구현해보겠습니다.

 

먼저, 트라이 자료 구조를 만들면 트라이는 root부터 시작합니다. 그리고 새로운 문자열을 저장할 때마다 문자열을 한 글자씩 나누어 노드로 저장하는데 문자열은 루트의 자식으로 저장되고 나누어진 노드는 문자열의 순서대로 부모-자식 관계로써 저장됩니다. 예를 들어 "cat"을 저장하면 첫 글자인 c는 루트의 자식이되고 c의 자식은 a, a의 자식은 t가 되는 식입니다.

 

탐색도 비슷한 방식으로 이루어집니다. 두 가지의 탐색 방법을 구현할 것인데, 하나는 해당 단어가 트라이에 저장되었는지 확인하는 메서드이고 다른 하나는 해당 문자열로 시작하는 단어가 저장되었는지 확인하는 메서드입니다. 두 메서드 모두 구현 방식은 거의 똑같습니다. 찾으려는 문자열을 한 글자씩 나눕니다. 그 뒤 루트노드부터 시작하여, 글자의 순서대로 한 글자씩 자식 노드에 존재한다면 자식 노드로 이동한 뒤 다음 글자가 이동한 노드의 자식에 있는지를 마지막 글자까지 확인합니다. 중간에 한 번이라도 자식 노드에 원하는 글자가 존재하지 않으면 해당 문자는 트라이 구조에 존재하지 않는 것이므로 false를 반환합니다. 모두 존재한다면 메서드의 종류에 따라 마지막 비교된 문자가 마지막 단어인지 확인하여 트라이에 해당 단어가 있는지를 반환하고 접두사인지 확인하는 메서드라면 true를 반환합니다.

 

아래는 위의 설계에 따라 간단하게 구현해 본 트라이 클래스입니다. 개선할 여지는 있지만 간단한 구현입니다.

class Trie {
  constructor() {
    this.root = this.#newNode();
  }

  #newNode() {
    return { children: {}, isEndNode: false };
  }

  insert(word) {
    let currentNode = this.root;

    for (let char of word) {
      if (!currentNode.children[char]) {
        currentNode.children[char] = this.#newNode();
      }

      currentNode = currentNode.children[char];
    }

    currentNode.isEndNode = true;
  }

  search(word) {
    let currentNode = this.root;

    for (let char of word) {
      if (!currentNode.children[char]) {
        return false;
      }

      currentNode = currentNode.children[char];
    }

    return currentNode.isEndNode;
  }

  startsWith(word) {
    let currentNode = this.root;

    for (let char of word) {
      if (!currentNode.children[char]) {
        return false;
      }

      currentNode = currentNode.children[char];
    }

    return true;
  }
}

const myTrie = new Trie();
myTrie.insert("cat");
myTrie.insert("car");
myTrie.insert("cargo");
myTrie.insert("canada");
console.log(myTrie.search("cargo")); // true
console.log(myTrie.search("ca")); // false
console.log(myTrie.startsWith("ca")); // true

시간복잡도

실제 단어가 얼마나 저장되었는지와는 상관없이 찾고자하는 혹은 저장하고자하는 문자열의 길이만이 시간복잡도에 영향을줍니다. 따라서 문자열의 길이가 n이라면 탐색과 삽입의 시간복잡도는 모두 O(n)이 됩니다.

 

여기서 한 노드에 여러 글자를 저장하면 트리의 깊이를 줄여 메모리 사용량을 줄일 수 있는데, 이를 "Compressed Trie" 또는 "Radix Trie"라고 부릅니다. 이를 구현하기 위해서는 새로운 문자열을 저장할 때 자식 노드에서 부분적으로 일치하는 접두사를 가져와 두 개의 노드로 분리하는 과정이 필요합니다. 예를 들어 현재 자식 노드의 키가 preix일 때 여기서 저장해야될 단어의 남은 부분이 pretty라면 현재 prefix라고 저장된 키를 pre로 나누어 pre의 자식으로 fix와 tty를 저장하는 방식으로 작동합니다.

https://excalidraw.com/로 그린 Radix Trie(기수 트리)

참고 자료

Wiki, 트라이 (컴퓨팅)

stackoverflow, What is the difference between trie and radix trie data structures?