Trie 자료구조는 어떤 문제에 적합하며 해시 테이블과 어떻게 다른가요?

Trie는 문자열을 문자 단위의 트리로 저장하는 자료구조입니다. 같은 접두사를 공유하는 단어들이 같은 경로를 공유하기 때문에 자동완성, 사전 검색, prefix matching에 강합니다.

해시 테이블은 정확히 같은 key를 찾는 데 매우 빠릅니다. 예를 들어 users['kim']처럼 전체 문자열이 주어졌을 때 평균 O(1)에 가깝게 조회합니다. 하지만 “kim으로 시작하는 모든 단어”를 찾으려면 모든 key를 순회해야 할 수 있습니다.

Trie에서는 접두사 길이를 m이라고 할 때, 먼저 m개의 문자를 따라 내려간 뒤 그 아래 subtree만 탐색하면 됩니다.

c
└─ a
   ├─ r (car)
   └─ t (cat)

장점은 접두사 검색이 빠르고 정렬된 탐색이 자연스럽다는 점입니다. 단점은 노드가 많아져 메모리 사용량이 커질 수 있다는 것입니다. 특히 알파벳 범위가 크거나 저장 문자열이 많을 때는 압축 Trie, Radix Tree 같은 변형을 고려합니다.

면접에서는 “정확 조회는 해시, 접두사 기반 탐색은 Trie”라고 비교하면 이해가 쉽습니다.