Trie 자료구조는 문자열을 통째로 비교하기보다, 글자 하나씩 길을 따라 저장하고 찾는 구조입니다. 그래서 공통 prefix를 공유해야 하는 문제에서 특히 힘을 발휘합니다.
이 글에서는 정의를 암기하기보다, 왜 자동완성이나 prefix 검색 문제에서 Trie가 자꾸 등장하는지 직관 중심으로 정리하겠습니다.
Trie를 한 줄로 이해하면 무엇일까
Trie는 문자열 키를 문자 단위 경로로 저장하는 검색 트리 계열 구조입니다. 단어가 끝나는 위치에는 단어 끝 표시를 두고, 중간 노드는 여러 단어가 함께 지나갈 수 있습니다.
즉 각 노드는 문자 하나를 위한 분기점처럼 동작하고, 루트에서 어떤 노드까지 내려가는 경로가 prefix를 표현합니다.
왜 prefix 검색에 특히 강할까
예를 들어 cat, car, care를 저장하면 c -> a 경로를 함께 씁니다. 그래서 사용자가 ca까지 입력한 순간, 그 아래 서브트리만 보면 후보 단어가 모여 있습니다.
이 점 때문에 Trie는 단순 exact match뿐 아니라 startsWith, 자동완성, longest prefix 같은 문제에서 자연스럽습니다. Princeton Algorithms의 tries 소개도 prefix matching과 longest prefix를 대표 예시로 듭니다.
검색은 어떻게 진행될까
- 루트에서 첫 글자 간선을 찾는다.
- 다음 노드에서 두 번째 글자 간선을 찾는다.
- 문자열 끝까지 내려간다.
- 마지막 노드에 단어 끝 표시가 있으면 검색 성공이다.
중요한 것은 사전 전체를 다시 비교하지 않는다는 점입니다. Trie 검색은 보통 지금 찾는 문자열 길이만큼 한 칸씩 내려가는 흐름으로 이해하면 됩니다.
삽입과 삭제는 어떤 감각으로 보면 좋을까
삽입은 이미 있는 경로를 재사용하고, 없는 경로만 새로 만들면 됩니다. 예를 들어 car가 이미 있으면 care를 넣을 때는 마지막 e만 추가하면 됩니다.
삭제는 조금 더 조심해야 합니다. 단어 끝 표시만 지우면 되는지, 아니면 그 뒤로 아무도 사용하지 않는 노드를 위로 거슬러 올라가며 정리해야 하는지를 함께 봐야 하기 때문입니다.
해시 테이블과 비교하면 왜 선택 기준이 갈릴까
해시 테이블은 exact match 조회에는 매우 강합니다. 하지만 ca로 시작하는 모든 단어를 모으는 작업은 구조적으로 직접적이지 않습니다.
Trie는 애초에 prefix 경로를 따라 내려가는 구조라서 이런 질의가 더 자연스럽습니다. 반대로 메모리 비용은 보통 Trie 쪽이 더 큽니다.
- 정확히 같은 키를 빨리 찾고 싶다 → 해시 테이블이 강하다
- prefix 검색과 자동완성이 중요하다 → Trie가 강하다
Trie는 언제나 더 빠른 구조가 아니라, prefix 연산이 중요한 문제에서 더 잘 맞는 구조입니다.
시간 복잡도는 어떻게 기억하면 좋을까
Trie의 검색과 삽입은 보통 문자열 길이 m 기준으로 설명합니다. 즉 단어 수보다, 현재 다루는 문자열 길이가 더 직접적인 감각이 됩니다.
다만 구현에 따라 상수 비용은 크게 달라질 수 있습니다. 자식 포인터를 고정 배열로 둘지, map으로 둘지, ternary search trie처럼 가지를 줄일지에 따라 속도와 메모리 특성이 달라집니다.
Trie의 가장 큰 단점은 무엇일까
가장 큰 단점은 메모리입니다. 문자마다 자식 링크를 넉넉하게 들고 있으면 실제로 쓰지 않는 칸이 많아질 수 있기 때문입니다.
이 때문에 실전에서는 단순 R-way Trie 대신 map 기반 Trie, compressed trie, ternary search trie(TST) 같은 변형을 함께 검토합니다. Princeton 자료도 R-way trie와 TST를 함께 소개합니다.
간단한 Python 예시로 보면 더 쉽다
class Node:
def __init__(self):
self.children = {}
self.is_end = False
root = Node()
word = "cat"
cur = root
for ch in word:
if ch not in cur.children:
cur.children[ch] = Node()
cur = cur.children[ch]
cur.is_end = True각 노드는 다음 문자로 가는 길들을 들고 있고, 마지막 노드에서 단어 끝 여부를 표시합니다. 실제 최적화는 훨씬 다양하지만, Trie의 본질은 이 예시만으로도 충분히 보입니다.
언제 Trie를 떠올리면 좋을까
- 자동완성
- 사전 검색
- 금칙어 prefix 판별
- startsWith 질의가 많은 문자열 집합
- longest prefix matching 개념이 필요한 문제
자료구조 비교 감각을 넓히고 싶다면 힙 자료구조란 무엇인가 글과 이진 탐색 트리 총정리도 함께 보면 선택 기준이 더 또렷해집니다.
외부 참고는 Princeton Algorithms Trie 소개와 Wikipedia Trie 개요를 바탕으로 정리했습니다.
