Trie는 어떤 문제를 풀 때 적합한가요?

Trie는 문자열을 문자 단위 경로로 저장하는 트리 자료구조입니다. 접두사(prefix)를 공유하는 문자열들이 같은 경로를 사용하므로 자동완성, 사전 검색, 접두사 매칭 문제에 적합합니다.

핵심 개념

• 루트에서 문자 하나씩 따라 내려가며 단어를 표현합니다.
• 단어의 끝을 표시하는 flag가 있어야 app과 apple을 구분할 수 있습니다.
• 검색 시간은 저장된 단어 수가 아니라 문자열 길이 L에 비례합니다.

동작 방식 또는 판단 기준

이 주제를 이해할 때는 다음 순서로 보면 실무 적용이 쉬워집니다.

1. 무엇을 해결하려는가: 성능, 표현력, 안정성, 접근성 중 어떤 문제를 줄이려는지 확인합니다.
2. 전제 조건은 무엇인가: 정렬 여부, 브라우저 지원, 네트워크 특성, 동시성 조건처럼 성립해야 하는 조건을 점검합니다.
3. 비용은 어디서 발생하는가: 시간 복잡도, 메모리, 캐시, 재시도, 렌더링 비용처럼 병목 지점을 나눠 봅니다.
4. 실패 시 어떤 문제가 생기는가: 잘못 적용했을 때의 버그나 운영 리스크를 함께 고려합니다.

실제 예시

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}

class Trie {
  root = new TrieNode();
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch);
    }
    node.isEnd = true;
  }
  startsWith(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) return false;
      node = node.children.get(ch);
    }
    return true;
  }
}

실무에서 주의할 점

• 문자 종류가 많고 단어 수가 적으면 Map/노드 오버헤드가 커질 수 있습니다.
• 유니코드, 대소문자, 정규화 정책을 정하지 않으면 같은 단어가 다르게 저장될 수 있습니다.
• 단순 전체 문자열 조회만 필요하다면 Hash Set이 더 간단하고 빠를 수 있습니다.

실무 적용 가이드

• 자동완성은 Trie + 인기순 score + 상위 후보 캐시를 함께 설계합니다.
• 민감한 필터링은 Aho-Corasick 같은 Trie 기반 알고리즘으로 확장할 수 있습니다.
• 메모리가 중요하면 compressed trie/radix tree를 검토합니다.

함께 연결해서 보면 좋은 키워드

Trie, Prefix, Autocomplete, String Search

정리

Trie는 문자열을 문자 단위 경로로 저장하는 트리 자료구조입니다. 다만 개념 자체보다 중요한 것은 적용 조건과 한계를 함께 이해하는 것입니다. 작은 예제에서는 단순해 보여도 실제 서비스에서는 성능, 보안, 유지보수성, 접근성 요구사항이 함께 얽히므로, 문제의 성격을 먼저 파악한 뒤 적절한 도구로 선택하는 것이 좋습니다.