[Daily morning study] 트라이(Trie) 자료구조와 문자열 검색
#daily morning study
트라이(Trie)란?
트라이는 문자열을 저장하고 탐색하기 위한 트리 기반 자료구조다. 이름은 retrieval(검색)에서 유래했다.
각 노드가 문자 하나를 나타내고, 루트에서 특정 노드까지의 경로가 하나의 문자열(또는 그 접두사)이 된다. 공통 접두사를 공유하는 문자열들을 같은 경로에 모아서 저장하기 때문에 공간 효율이 높고 검색이 빠르다.
핵심 특성
- 루트 노드는 빈 문자열을 나타냄
- 각 노드는 자식 노드 배열(보통 알파벳 26개)과 단어 끝 여부를 나타내는 플래그를 가짐
- 깊이 k인 노드는 길이 k의 접두사를 나타냄
트라이 구조 예시
[“cat”, “car”, “card”, “care”, “dog”]을 트라이에 삽입하면:
(root)
├── c
│ └── a
│ ├── t* ← "cat" 끝
│ └── r* ← "car" 끝
│ ├── d* ← "card" 끝
│ └── e* ← "care" 끝
└── d
└── o
└── g* ← "dog" 끝
* 표시가 있는 노드는 is_end = True.
시간/공간 복잡도
| 연산 | 시간 복잡도 | 비고 |
|---|---|---|
| 삽입 | O(L) | L = 문자열 길이 |
| 검색 | O(L) | |
| 삭제 | O(L) | |
| 공간 | O(N × M × A) | N=단어 수, M=평균 길이, A=알파벳 크기 |
해시맵 기반 검색도 평균 O(1)이지만, 트라이는 접두사 탐색에 특화되어 있어 자동완성, 사전 구현 등에 적합하다.
Python 구현
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word: str) -> bool:
node = self.root
for ch in word:
if ch not in node.children:
return False
node = node.children[ch]
return node.is_end
def starts_with(self, prefix: str) -> bool:
node = self.root
for ch in prefix:
if ch not in node.children:
return False
node = node.children[ch]
return True
사용 예
trie = Trie()
for word in ["cat", "car", "card", "care", "dog"]:
trie.insert(word)
print(trie.search("car")) # True
print(trie.search("ca")) # False (단어 끝 아님)
print(trie.starts_with("ca")) # True
print(trie.starts_with("do")) # True
print(trie.starts_with("fox")) # False
자동완성 기능 구현
트라이의 대표적 활용 사례인 자동완성은 starts_with 이후 DFS로 구현한다.
def autocomplete(self, prefix: str) -> list[str]:
node = self.root
for ch in prefix:
if ch not in node.children:
return []
node = node.children[ch]
results = []
self._dfs(node, prefix, results)
return results
def _dfs(self, node: TrieNode, current: str, results: list[str]) -> None:
if node.is_end:
results.append(current)
for ch, child in node.children.items():
self._dfs(child, current + ch, results)
trie.autocomplete("car") # ["car", "card", "care"]
삭제 구현
삭제는 삽입보다 복잡하다. 단순히 is_end를 False로 바꾸는 것만으로는 메모리 누수가 생기기 때문에, 자식이 없는 노드는 실제로 제거해야 한다.
def delete(self, word: str) -> bool:
return self._delete(self.root, word, 0)
def _delete(self, node: TrieNode, word: str, depth: int) -> bool:
if depth == len(word):
if not node.is_end:
return False # 단어가 존재하지 않음
node.is_end = False
return len(node.children) == 0 # 자식 없으면 노드 제거 가능
ch = word[depth]
if ch not in node.children:
return False
should_delete_child = self._delete(node.children[ch], word, depth + 1)
if should_delete_child:
del node.children[ch]
return len(node.children) == 0 and not node.is_end
return False
공간 최적화: 압축 트라이 (Compressed Trie / Radix Tree)
일반 트라이는 단일 자식만 있는 노드가 길게 이어질 때 메모리 낭비가 심하다. 이런 경우 자식이 하나뿐인 노드들을 하나로 합치는 압축 트라이를 쓴다.
일반 트라이: 압축 트라이 (Radix Tree):
(root) (root)
└── d └── "dog"*
└── o
└── g*
Patricia Tree, Radix Tree라고도 불린다. Go의 표준 라이브러리 라우터, nginx 경로 탐색 등에서 실제로 활용된다.
트라이 vs 해시맵
| 트라이 | 해시맵 | |
|---|---|---|
| 단어 검색 | O(L) | O(L) 평균 |
| 접두사 검색 | O(P + 결과 수) | 불가 (전체 탐색 필요) |
| 정렬된 순회 | 가능 (사전순) | 별도 정렬 필요 |
| 메모리 | 공통 접두사 공유 | 각 키를 독립 저장 |
| 충돌 | 없음 | 발생 가능 |
접두사 기반 연산이 필요하면 트라이, 단순 키-값 저장이 필요하면 해시맵이 적합하다.
실전 활용 사례
1. 검색 자동완성
- 사용자가 입력한 접두사로 가능한 단어 목록 반환
- 구글, IDE 자동완성, 터미널 탭 완성
2. 철자 교정 (Spell Checker)
- 단어를 삽입할 때 편집 거리(Edit Distance)와 결합하면 유사 단어 제안 가능
3. IP 라우팅 (Longest Prefix Match)
- 네트워크 라우터에서 목적지 IP에 가장 길게 일치하는 라우팅 경로 탐색
4. 사전(Dictionary) 구현
- 단어 존재 여부 빠른 검색 + 사전순 순회
5. 문자열 패턴 매칭
- Aho-Corasick 알고리즘은 트라이를 기반으로 다중 패턴을 동시에 검색
Aho-Corasick 알고리즘 개요
여러 패턴 문자열을 텍스트에서 동시에 찾는 알고리즘이다. 트라이 + BFS로 실패 링크(failure link)를 구성하여 O(N + M + 매칭 수)로 동작한다 (N = 텍스트 길이, M = 모든 패턴 길이 합).
- 단순 반복 검색: O(N × M)
- Aho-Corasick: O(N + M + output)
바이러스 패턴 탐지, 스팸 필터링, grep 다중 패턴 등에 쓰인다.
요약
- 트라이는 문자열 집합을 트리 형태로 관리하며, 삽입/검색/삭제 모두 O(L)
- 접두사 탐색과 자동완성에 최적화된 자료구조
- 메모리 최적화가 필요하면 압축 트라이(Radix Tree)를 고려
- 다중 패턴 검색이 필요하면 Aho-Corasick(트라이 확장)을 사용
