Trie 자료구조 — 원리와 구현
문자열 검색에 최적화된 트리 구조
Trie란
검색 트리의 일종으로, 문자열을 저장하고 탐색하는데 효율적인 자료구조이다. Trie는 문자열의 접두사(Prefix)를 이용하여 트리를 구성하므로, 특히나 문자열 검색에 유용하다. 이름은 retrieval(검색)에서 유래되었다.
예를 들어 ["apple", "app", "april", "bat", "ball"]이라는 단어들을 저장한다고 하면, 공통 접두사를 공유하는 트리 구조가 만들어진다.
1
2
3
4
5
6
7
8
9
10
11
(root)
/ \
a b
| |
p a
/ \ | \
p r t l
| | |
l i l
| |
e l
Trie의 특징
- 각 노드는 하나의 문자를 저장한다
- 루트 노드는 빈 문자열을 나타낸다
- 각 노드는 해당 노드까지의 문자열(prefix)을 나타내며, 단어의 끝을 표시하는 플래그(
isEnd)를 가진다 - 자식 노드는 해당 문자 다음에 나타날 수 있는 문자를 저장하는 데 사용된다
시간 복잡도
| 연산 | 시간 복잡도 |
|---|---|
| 삽입 | O(L) |
| 검색 | O(L) |
| 접두사 검색 | O(L) |
| 삭제 | O(L) |
여기서 L은 문자열의 길이이다. HashMap으로 검색하면 O(L)이지만 접두사 기반 검색은 불가능하다. Trie는 접두사 검색까지 O(L)에 처리할 수 있다는 점이 핵심 장점이다.
공간 복잡도
최악의 경우 O(ALPHABET_SIZE × L × N)으로, N은 저장된 문자열의 수이다. 공통 접두사가 많을수록 공간 효율이 좋아진다.
Trie 구현 (Java)
노드 정의
1
2
3
4
5
6
7
8
9
class TrieNode {
TrieNode[] children;
boolean isEnd;
public TrieNode() {
children = new TrieNode[26]; // 소문자 알파벳만 고려
isEnd = false;
}
}
Trie 클래스
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// 삽입
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) {
node.children[idx] = new TrieNode();
}
node = node.children[idx];
}
node.isEnd = true;
}
// 검색: 해당 단어가 존재하는지 확인
public boolean search(String word) {
TrieNode node = findNode(word);
return node != null && node.isEnd;
}
// 접두사 검색: 해당 접두사로 시작하는 단어가 있는지 확인
public boolean startsWith(String prefix) {
return findNode(prefix) != null;
}
private TrieNode findNode(String str) {
TrieNode node = root;
for (char c : str.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) {
return null;
}
node = node.children[idx];
}
return node;
}
}
사용 예시
1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) {
Trie trie = new Trie();
trie.insert("apple");
trie.insert("app");
trie.insert("april");
System.out.println(trie.search("apple")); // true
System.out.println(trie.search("app")); // true
System.out.println(trie.search("ap")); // false (삽입하지 않음)
System.out.println(trie.startsWith("ap")); // true (접두사로는 존재)
System.out.println(trie.startsWith("bat")); // false
}
Trie에서의 삭제
삭제는 삽입/검색보다 조금 더 복잡하다. 다른 단어의 접두사인 경우 노드 자체를 삭제하면 안 되기 때문이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public boolean delete(String word) {
return delete(root, word, 0);
}
private boolean delete(TrieNode node, String word, int depth) {
if (node == null) return false;
if (depth == word.length()) {
if (!node.isEnd) return false;
node.isEnd = false;
return isEmpty(node);
}
int idx = word.charAt(depth) - 'a';
boolean shouldDeleteChild = delete(node.children[idx], word, depth + 1);
if (shouldDeleteChild) {
node.children[idx] = null;
return !node.isEnd && isEmpty(node);
}
return false;
}
private boolean isEmpty(TrieNode node) {
for (TrieNode child : node.children) {
if (child != null) return false;
}
return true;
}
삭제 로직의 핵심:
- 단어의 끝 노드에서
isEnd = false로 설정 - 해당 노드에 자식이 없으면 노드를 삭제
- 재귀적으로 올라가며 불필요한 노드들을 정리
HashMap을 사용한 Trie
알파벳만 다루는 경우 배열이 효율적이지만, 유니코드 등 다양한 문자를 다뤄야 할 경우 HashMap을 사용할 수 있다.
1
2
3
4
5
6
7
8
9
class TrieNode {
Map<Character, TrieNode> children;
boolean isEnd;
public TrieNode() {
children = new HashMap<>();
isEnd = false;
}
}
이 방식은 메모리를 절약할 수 있지만, 배열 방식보다 접근 속도가 느릴 수 있다.
활용 사례
Trie는 다음과 같은 상황에서 자주 사용된다:
- 자동 완성(Autocomplete): 입력한 접두사에 해당하는 모든 단어를 빠르게 검색
- 맞춤법 검사(Spell Checker): 사전에 있는 단어인지 빠르게 확인
- IP 라우팅(Longest Prefix Match): 네트워크에서 가장 긴 접두사 매칭
- 문자열 정렬: Trie에 삽입 후 DFS로 사전순 정렬 가능
코딩 테스트 Tip
Trie 관련 대표 문제:
- LeetCode 208 - Implement Trie (기본 구현)
- LeetCode 211 - Design Add and Search Words Data Structure (와일드카드 검색)
- LeetCode 212 - Word Search II (2D 보드에서 단어 검색, Trie + DFS)
- 백준 5052 - 전화번호 목록 (접두사 판별)
References
관련 포스트
-
Previous
시스템 디자인: 캐싱 전략 (Cache-Aside, Write-Through, Write-Be... -
Next
부동소수점(Floating Point) 표현 — IEEE 754 완전 정복
댓글을 불러오는 중...