개요
트라이(Trie / Prefix tree)는 문자열을 저장하고 검색하는 데 일반적으로 사용되는 알고리즘 방법 중 하나이다. 트리 구조를 기반으로 사용하며 효율적인 검색을 할 수 있게 해준다는 데서 검색(retrieval)에서 이름을 가져왔다.
원리
문자열 삽입
처음에는 빈 루트 노드만이 위치한다. 여기에 chick이라는 문자열을 넣는다고 하자.
문자열 중 첫번째 문자인 c에 대응하는 노드가 없기 때문에 루트 노드로부터 새로운 노드를 생성하고 노드의 값은 문자 c가 된다. 다음으로 삽입을 진행할 h도 그에 대응하는 노드가 없으므로 c 노드의 아래에 노드를 생성하고 값을 h로 한다.
그 다음 문자들에 대해서도 각각에 대응하는 노드가 없으므로 새로운 노드를 생성하고 값은 각각의 문자를 넣는다. 따라서 'chick'이라는 문자열을 모두 삽입하고 나면 이러한 구조가 된다. 문자열의 끝인 'k'는 자신이 문자열의 끝임을 알려주어야 한다.(보통, boolean 값으로 문자열의 끝=true로 표시하거나 데이터 구조에 대한 포인터를 가리킴) 그리고 다음으로 'choco'와 'chi'를 삽입하도록 하자.
'choco'를 삽입할 때, 'c'와 'h'는 이미 트리에 삽입되어 있으므로 새로운 노드를 생성하지 않는다. 다음에 오는 'o'는 'h' 다음의 노드 중 존재하지 않으므로 노드를 생성, 값을 삽입한다.
'c', 'o'에 대해서도 그에 대응하는 값을 가진 노드가 없으므로 같은 과정이 진행된다. 또한 'o' 노드는 문자열의 끝을 가리키도록 한다. 다음으로 'chi' 문자열을 삽입하자.
'chi'는 각각의 문자에 대응되는 노드가 이미 삽입되어 있다. 'c', 'h', 'i' 모두 이미 트리에 있으므로 새로운 노드를 생성하지 않는다. 대신 문자열의 끝인 'i' 노드에 자신이 문자열의 끝임을 가리키도록 한다.
문자열 검색
위의 과정을 통해 생성된 트라이 구조에서 문자열 'chick'과 'choc','char'를 검색해보자. 'chick'부터 루트 노드에서부터 검색을 시작한다. 'chick'을 검색할 때, 첫번째 문자인 'c'가 루트 노드의 자식 노드에 있는지 탐색한다. 'c'가 존재하므로 다음 문자인 'h'가 존재하는지 탐색한다. 이러한 방식으로 탐색을 진행하면 결국 마지막 문자인 'k'를 검색한다. 'k'가 존재하고, 자신이 문자열의 끝임을 나타내고 있으므로 'chick'은 트리에 존재함을 확인하고 검색을 종료한다. 'choc'를 검색하면 어떻게 되는가. 마찬가지로 'c', 'h', 'o', 'c'에 대해서는 각각에 대응하는 노드가 존재함을 탐색을 통해 알 수 있으므로 진행한다. 하지만 문자열의 끝이어야 하는 'c'는 문자열의 끝이 아니므로 'choc'은 트리에 존재하지 않는 단어이다. 'char'를 검색하는 과정은 어떻게 되는가. 'c', 'h'까지는 트리에 존재하는 단어이므로 검색을 진행한다. 하지만 'a'는 'h'의 하위 노드 중에 존재하지 않으므로 탐색을 진행하여 없음을 확인하고 검색이 종료된다.
이러한 방식으로 트리를 사용한 트라이 알고리즘을 구현한다.
정리하면
- 빈 루트 노드로부터 시작한다.
- 삽입할 문자열에 대해 한 문자씩 이동하며, 각각에 대응하는 문자가 없으면 새로운 노드를 생성, 현재의 노드와의 엣지를 연결하고 문자의 값을 저장한다.
- 문자열 전체를 삽입하면 마지막 노드를 문자열의 끝으로 표시한다.
- 문자열을 검색하려면 루트 노드로부터 한 문자씩 검색한다. 이 과정에서 없는 문자를 검색하면 문자열이 없음을 반환하고 검색을 종료한다.
- 문자열의 끝에 도달하고 경로의 마지막 노드가 문자열의 끝으로 표시되면 문자열이 존재함을 반환하고 검색을 종료한다.
트라이의 장단점은 다음과 같다.
장점
- 문자열을 빠르게 검색할 수 있다.
문자열을 삽입하거나 검색하는 경우 모두 문자열의 길이만큼 탐색을 진행하므로 대상 문자열의 길이가 m이라고 할 때, 시간 복잡도는 O(m)만큼이 된다. 삽입의 경우 없는 문자열에 대해 새로운 노드를 생성, 이 과정이 m회 진행되며, 검색의 경우 역시 최악의 경우가 검색하려는 문자열이 존재하는 것이므로 문자열의 길이 m만큼 탐색하기 때문이다. - 접두사 검색에 굉장히 효율적이다.
트라이는 접두사를 검색할 때, 유용하게 쓰인다. 해당 접두사를 검색하고 그에 해당하는 노드들을 통과한 뒤 하위 노드들을 반환하면 되기 때문이다. 자동 완성 시스템, 가장 긴 공통 접두사 단어 찾기 등에서 트라이를 사용한다.
단점
- 메모리 사용량이 크다.
많은 수의 문자열을 삽입하거나 긴 문자열을 삽입할 경우, 각 문자열의 문자에 대해 노드를 만들게 되는데 많은 수의 문자열을 삽입하면 공통 접두사 아래 상당히 큰 수의 하위 노드가 생길 수 있고 긴 문자열을 삽입하면 하위 노드의 층수가 깊어질 수 있다.
응용
다음은 트라이를 사용한 알고리즘 문제 풀이 예시이다.
#include <iostream>
using namespace std;
typedef struct trie {
bool finish;
trie* node[15];
//생성자
trie() {
finish = false;
for (int i = 0; i < 10; i++) {
node[i] = NULL;
}
}
//소멸자
~trie() {
for (int i = 0; i < 10; i++) {
if (node[i]) {
delete node[i];
}
}
}
void insert(char* str) {
if (*str == NULL) {
finish = true;
return;
}
int k = *str - '0';
if (node[k] == NULL) {
node[k] = new trie();
}
node[k]->insert(str + 1);
}
bool find(char* str) {
if (*str == NULL) {
if (finish == true) {
return true;
}
return false;
}
if (finish == true) {
return false;
}
int k = *str - '0';
if (node[k] == NULL) {
return false;
}
return node[k]->find(str + 1);
}
};
int main() {
int t, n;
char s[10005][15];
bool ans;
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> t;
while (t--) {
trie* tri = new trie();
cin >> n;
for (int i = 0; i < n; i++) {
cin >> s[i];
tri->insert(s[i]);
}
ans = true;
for (int i = 0; i < n; i++) {
if (tri->find(s[i]) == false) {
ans = false;
break;
}
}
delete tri;
cout << ((ans) ? "YES\n" : "NO\n");
}
return 0;
}숫자(0~9)를 영문자 대신으로 트라이를 구현한 것이다. 원리는 위의 트라이 원리 설명과 같다. 번호를 삽입할 때, 각 번호의 자릿수만큼 탐색을 진행하여 번호에 해당하는 노드가 있으면 다음 자리의 번호로 이동하여 과정을 수행하고 없으면 새로운 노드를 생성, 해당 번호의 값을 부여한다. 번호를 검색할 때, 각 번호의 자릿수만큼 탐색을 진행하여 검색하려는 전화번호가 아직 끝나지 않았지만 현재 탐색 중인 노드가 문자열의 끝을 나타낼 경우, 검색을 중단하고 결과를 반환한다.
#include <iostream>
#include <vector>
#include <map>
using namespace std;
typedef struct trie {
map<string, trie*> prey;
trie() {
}
~trie() {
for (auto it = prey.begin(); it != prey.end(); it++) {
delete it->second;
}
}
void insert(vector<string> v, int idx) {
if (idx == v.size()) {
return;
}
else {
string s = v[idx];
auto it = prey.find(s);
if (it != prey.end()) {
it->second->insert(v, idx + 1);
}
else {
trie* t = new trie();
prey.insert({ s,t });
t->insert(v, idx + 1);
}
}
}
void print(int idx) {
if (prey.empty()) {
return;
}
else {
for (auto it = prey.begin(); it != prey.end(); it++) {
for (int i = 0; i < idx; i++) {
cout << "--";
}
cout << it->first << "\n";
it->second->print(idx + 1);
}
}
}
};
int main() {
int n, k;
string s;
trie* nest = new trie();
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> k;
vector<string> v;
for (int j = 0; j < k; j++) {
cin >> s;
v.push_back(s);
}
nest->insert(v, 0);
}
nest->print(0);
delete nest;
return 0;
}문자가 아닌 문자열이 하나의 노드로 들어올 수 있는가? 나는 map 구조를 사용해 각 문자열에 해당하는 트라이 포인터를 반환함으로써 이 문제를 해결했다. 이보다 더욱 효율적인 해결 방법이 반드시 있으리라 생각한다.
#include <bits/stdc++.h>
using namespace std;
struct trie {
int finish;
trie* node[30];
trie() {
finish = 0;
for (int i = 0; i < 26; i++) {
node[i] = NULL;
}
}
~trie() {
for (int i = 0; i < 26; i++) {
if (node[i]) {
delete node[i];
}
}
}
void id_insert(char* str) {
if (*str == NULL) {
finish++;
return;
}
int k = *str - 'a';
if (node[k] == NULL) {
node[k] = new trie();
}
node[k]->id_insert(str + 1);
}
bool id_find(char* str) {
if (*str == NULL) {
if (finish > 0) {
cout << finish + 1;
return true;
}
return false;
}
else {
cout << *str;
}
int k = *str - 'a';
if (node[k] == NULL) {
return false;
}
return node[k]->id_find(str + 1);
}
};
int main() {
int n;
char pname[15];
trie* tri = new trie();
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
while (n--) {
cin >> pname;
tri->id_find(pname);
tri->id_insert(pname);
if (n > 0) {
cout << "\n";
}
}
return 0;
}문자열의 끝이 없음(null)에도 반환하는 실수를 깨닫지 못해 꼬박 10시간 동안 분투했던 문제이다. 트라이 외에도 더 효율적인 풀이 방법이 있다고 하니 고민해보자.
