트라이(Trie)의 원리와 구현 - soo:bak
작성일 :
트라이란?
트라이(Trie)는 문자열 집합을 저장하고 검색하는 트리 기반 자료구조입니다.
Prefix Tree 또는 Retrieval Tree라고도 부르며, 공통 접두사를 공유하는 방식으로 문자열들을 저장합니다.
문자열 검색에 \(O(m)\) (\(m\): 문자열 길이)의 시간 복잡도를 가지며, 자동 완성이나 사전 구현에 자주 활용됩니다.
트라이의 구조
문자열 ["cat", "car", "card", "dog"]를 저장한 트라이의 모습입니다:
1
2
3
4
5
6
7
8
9
root
/ \
c d
| |
a o
/ \ |
t r g*
* |
d*
*는 단어의 끝(종료 표시)을 나타냅니다.
각 노드는 하나의 문자를 나타내며, 루트에서 노드까지의 경로가 접두사가 됩니다.
종료 표시가 있는 노드까지의 경로가 완전한 단어입니다.
구현
기본 구현
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
class Trie {
private:
struct Node {
unordered_map<char, Node*> children;
bool isEnd = false;
};
Node* root;
public:
Trie() {
root = new Node();
}
// 단어 삽입 - O(m)
void insert(const string& word) {
Node* cur = root;
for (char c : word) {
if (!cur->children.count(c)) {
cur->children[c] = new Node();
}
cur = cur->children[c];
}
cur->isEnd = true;
}
// 단어 검색 - O(m)
bool search(const string& word) {
Node* cur = root;
for (char c : word) {
if (!cur->children.count(c)) {
return false;
}
cur = cur->children[c];
}
return cur->isEnd;
}
// 접두사 검색 - O(m)
bool startsWith(const string& prefix) {
Node* cur = root;
for (char c : prefix) {
if (!cur->children.count(c)) {
return false;
}
cur = cur->children[c];
}
return true;
}
};
int main() {
Trie trie;
trie.insert("apple");
trie.insert("app");
trie.insert("application");
cout << trie.search("app") << "\n"; // 1 (true)
cout << trie.search("apple") << "\n"; // 1 (true)
cout << trie.search("appl") << "\n"; // 0 (false)
cout << trie.startsWith("app") << "\n"; // 1 (true)
cout << trie.startsWith("apy") << "\n"; // 0 (false)
return 0;
}
배열 기반 구현 (고정 알파벳)
소문자만 사용하는 경우 배열을 활용하면 더 빠르게 구현할 수 있습니다.
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
class TrieArray {
private:
struct Node {
Node* children[26] = {nullptr};
bool isEnd = false;
};
Node* root;
int charToIdx(char c) { return c - 'a'; }
public:
TrieArray() { root = new Node(); }
void insert(const string& word) {
Node* cur = root;
for (char c : word) {
int idx = charToIdx(c);
if (!cur->children[idx]) {
cur->children[idx] = new Node();
}
cur = cur->children[idx];
}
cur->isEnd = true;
}
bool search(const string& word) {
Node* cur = root;
for (char c : word) {
int idx = charToIdx(c);
if (!cur->children[idx]) return false;
cur = cur->children[idx];
}
return cur->isEnd;
}
};
시간 복잡도
트라이의 모든 연산은 문자열 길이 \(m\)에 비례합니다.
- 삽입: \(O(m)\)
- 검색: \(O(m)\)
- 접두사 검색: \(O(m)\)
- 삭제: \(O(m)\)
공간 복잡도는 최악의 경우 \(O(n \cdot m \cdot k)\)입니다. (\(n\): 단어 수, \(m\): 평균 단어 길이, \(k\): 알파벳 크기)
실제로는 공통 접두사를 공유하므로 이보다 훨씬 적은 메모리를 사용합니다.
트라이 vs 해시 테이블
해시 테이블도 문자열 검색에 \(O(m)\)의 평균 시간 복잡도를 가지지만, 접두사 검색에서 차이가 납니다.
해시 테이블에서 특정 접두사로 시작하는 모든 단어를 찾으려면 모든 키를 순회해야 하므로 \(O(n \cdot m)\)이 필요합니다.
반면 트라이는 접두사 위치까지 이동한 후 하위 트리만 탐색하면 되므로 훨씬 효율적입니다.
또한 트라이는 사전순 순회가 가능하고 해시 충돌이 없다는 장점이 있습니다.
접두사 기반 검색이나 자동 완성 기능이 필요하다면 트라이가 적합합니다.
활용 예시
1. 자동 완성
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<string> autocomplete(const string& prefix) {
vector<string> result;
Node* cur = root;
// 접두사까지 이동
for (char c : prefix) {
if (!cur->children.count(c)) return result;
cur = cur->children[c];
}
// DFS로 모든 단어 수집
function<void(Node*, string)> dfs = [&](Node* node, string word) {
if (node->isEnd) result.push_back(word);
for (auto& [c, child] : node->children) {
dfs(child, word + c);
}
};
dfs(cur, prefix);
return result;
}
2. 단어 개수 세기
각 노드에 해당 접두사를 가진 단어 수를 저장하면, 특정 접두사로 시작하는 단어가 몇 개인지 빠르게 알 수 있습니다.
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
class TrieWithCount {
struct Node {
unordered_map<char, Node*> children;
int count = 0; // 이 접두사를 가진 단어 수
bool isEnd = false;
};
void insert(const string& word) {
Node* cur = root;
for (char c : word) {
if (!cur->children.count(c)) {
cur->children[c] = new Node();
}
cur = cur->children[c];
cur->count++;
}
cur->isEnd = true;
}
int countWordsWithPrefix(const string& prefix) {
Node* cur = root;
for (char c : prefix) {
if (!cur->children.count(c)) return 0;
cur = cur->children[c];
}
return cur->count;
}
};
3. 최장 공통 접두사
여러 문자열의 최장 공통 접두사를 찾을 때도 트라이를 활용할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
string longestCommonPrefix(vector<string>& words) {
if (words.empty()) return "";
Trie trie;
for (const string& w : words) {
trie.insert(w);
}
string lcp;
Node* cur = root;
while (cur->children.size() == 1 && !cur->isEnd) {
auto it = cur->children.begin();
lcp += it->first;
cur = it->second;
}
return lcp;
}
자식이 하나뿐이고 단어의 끝이 아닌 동안 계속 내려가면, 모든 문자열이 공유하는 접두사를 찾을 수 있습니다.
마무리
트라이는 문자열 집합을 효율적으로 저장하고 검색하는 자료구조입니다.
각 노드가 문자를 나타내는 트리 구조로, 문자열 길이에 비례하는 \(O(m)\) 시간에 검색이 가능합니다.
공통 접두사를 공유하여 메모리를 절약하고, 접두사 검색이나 자동 완성에 특히 유용합니다.
다만 해시 테이블에 비해 메모리 사용량이 클 수 있으므로, 접두사 기반 연산이 필요한지에 따라 적절히 선택하면 됩니다.
관련 글:
관련 문제: