Trie 자료구조는 문자열을 통째로 저장하지 않고 글자 단위 경로로 나눠 저장합니다. 그래서 단어 전체가 있는지뿐 아니라 어떤 접두사로 시작하는 단어가 있는지도 자연스럽게 확인할 수 있습니다.
핵심은 정확한 문자열 조회는 해시맵이 단순하고, 접두사 검색은 Trie가 더 자연스럽다는 기준입니다.
Trie 자료구조는 문자열을 경로로 저장한다
이 그림의 핵심은 ca가 한 번만 저장된다는 점입니다. 같은 접두사를 가진 단어가 많을수록 Trie는 이 공유 구조를 활용합니다.
예를 들어 cat, car, care를 저장하면 ca까지는 같은 경로를 공유하고, 그 뒤에서 t와 r로 갈라집니다.
이 구조 덕분에 공통 접두사를 가진 단어들을 한 덩어리처럼 다룰 수 있습니다.
해시맵으로 충분한 경우
자료구조 선택은 성능 숫자 하나로 끝나지 않습니다. 문제의 질문이 단어 전체를 묻는지, 접두사를 묻는지, 후보 목록을 펼쳐야 하는지를 먼저 봐야 합니다.
단어가 정확히 있는지만 묻는다면 해시맵이 더 간단합니다. word in set 같은 조회는 구현도 짧고 평균적으로 빠릅니다.
예를 들어 금지어 목록에 어떤 단어가 포함되는지만 확인한다면 Trie까지 만들 필요가 없을 수 있습니다. 해시 기반 조회 흐름은 자바 HashMap key 조회 글과도 연결됩니다.
Trie가 유리한 경우
- 자동완성처럼 prefix 아래 후보를 찾아야 한다.
- startsWith 쿼리가 많다.
- 전화번호 목록처럼 어떤 문자열이 다른 문자열의 접두사인지 확인해야 한다.
- 사전순 탐색이나 문자 단위 분기가 중요하다.
이런 문제에서는 해시맵으로 모든 접두사를 따로 저장할 수도 있지만, 데이터가 커질수록 관리가 지저분해질 수 있습니다.
Trie 구현 예시
class TrieNode:
def __init__(self):
self.children = {}
self.terminal = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.terminal = True
def search(self, word):
node = self._find(word)
return node is not None and node.terminal
def starts_with(self, prefix):
return self._find(prefix) is not None
def _find(self, text):
node = self.root
for ch in text:
if ch not in node.children:
return None
node = node.children[ch]
return node여기서 terminal은 이 노드에서 실제 단어가 끝나는지를 표시합니다. prefix 경로가 존재한다고 해서 반드시 그 prefix 자체가 단어라는 뜻은 아니기 때문입니다.
메모리 비용을 꼭 봐야 한다
Trie는 노드를 많이 만듭니다. 알파벳 소문자만 다루는지, 한글/이모지/대소문자까지 다루는지에 따라 children 구조의 비용이 달라집니다.
그래서 작은 데이터에서 단순 조회만 한다면 해시맵이 더 낫고, prefix 쿼리가 많거나 자동완성이 핵심이면 Trie가 더 자연스럽습니다. Trie 계열 개념은 cp-algorithms의 Aho-Corasick 설명에서도 출발점으로 등장합니다.
정리
Trie 자료구조는 해시맵의 상위 호환이 아닙니다. 문제의 질문이 ‘이 단어가 있는가’라면 해시맵, ‘이 접두사로 시작하는 단어가 있는가’라면 Trie를 먼저 떠올리면 됩니다.
