Trie 자료구조는 트리 응용 자료구조로 문자열 검색에 사용되는 자료구조이다.

• 래딕스 트리(radix tree), 접두사 트리(prefix tree), 탐색 트리(retrieval tree)라고도 한다. 트라이는 retrieval tree에서 나온 단어이다.
• 장점: 문자열을 탐색할 때, 하나씩 전부 비교하면서 탐색하는 방식보다 문자열을 빠르게 검색할 수 있으며, 특히 검색 대상이 많을 때 유용하다.
• 단점: 각 노드에서 다음 문자를 가리키는 노드가 필요하기 때문에 문자열이 길어질수록 공간 복잡도 측면에서 불리하다.

구조

Trie 자료구조는 루트 노드에서 시작하여 각 문자의 글자에 맞는 자식 노드로 이어지는 트리이다.

예시

아래는 "apple", "app", "banana"를 trie 자료구조로 표현한 그림이다. 색깔이 있는 노드는 문자열이 종료되는 지점이다.

JavaScript 코드 예시

위의 개념을 JS 코드로 구현해보면 아래와 같다.

class TrieNode {
  constructor() {
    this.children = new Map(); // 자식 노드를 저장할 맵
    this.isEndOfWord = false; // 단어의 끝인지 여부
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode(); // 루트 노드 생성
  }

  insert(word) {
    let current = this.root; // 현재 노드를 루트 노드로 초기화
    for (const char of word) { // 단어의 각 문자에 대해 반복
      // 현재 노드의 자식 노드에 해당 문자가 없으면 새로운 노드를 생성하여 자식 노드로 추가
      if (!current.children.has(char)) { 
        current.children.set(char, new TrieNode());
      }
      current = current.children.get(char); // 현재 노드를 해당 문자의 자식 노드로 변경
    }
    current.isEndOfWord = true; // 마지막 노드를 단어의 끝으로 표시
  }

  search(word) {
    let current = this.root;
    for (const char of word) {
      // 현재 노드의 자식 노드에 해당 문자가 없으면 단어가 존재하지 않으므로 false 반환
      if (!current.children.has(char)) { 
        return false;
      }
      current = current.children.get(char); // 현재 노드를 해당 문자의 자식 노드로 변경
    }
    return current.isEndOfWord; // 마지막 노드의 isEndOfWord 값을 반환하여 단어의 존재 여부를 판단
  }
}

const trie = new Trie();
trie.insert('apple');
trie.insert('app');
trie.insert('banana');

console.log(trie.search('apple')); // true
console.log(trie.search('app')); // true
console.log(trie.search('appl')); // false
console.log(trie.search('banana')); // true