📖트라이
트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.
위와 같이 트리의 루트 노드에서부터 자식 노드들을 따라가면서 생성된 문자열들이 트라이 자료구조에 저장되어있다. 저장된 문자열은 끝을 표시하는 변수를 추가하여 문자열의 끝을 구분할 수 있다.
📁트라이의 작동 원리
트라이는 주어진 문자열을 이루고 있는 문자를 앞에서부터 하나씩 노드로 생성하여 저장하는 과정을 반복한다.
- 주어진 문자열에서 현재 문자를 가져온다.
- 현재 문자로 이루어진 노드가 존재한다면 그 노드로 이동한 후 다음 문자를 탐색하고, 노드가 없다면 노드를 새로 할당 받은 후 해당 노드를 통해 다음 문자를 탐색한다.
- 문자열의 마지막이 될 때까지 위의 과정을 반복한다.
문자열 AB, ACD, CDF를 삽입하는 과정을 살펴보자. 초기는 다음과 같이 루트 노드만 존재한다.
문자열 AB의 첫번째 문자인 A에 대한 노드가 없기 때문에 노드를 새로 추가한 후, A 노드에서 다음 문자를 탐색한다.
다음 문자인 B에 대한 노드 또한 없기 때문에 노드를 새로 추가한다. 이때, 문자열의 끝이라는 의미로 노드를 빨간색으로 표시한다.
문자열 AB에 대한 노드 삽입을 완료하였다. 이후 문자열 ACD를 삽입할 경우, 문자 A에 대한 노드는 이미 존재하므로 A 노드에서 다음 순서 문자인 C에 대한 노드를 추가한다.
D에 대한 노드도 존재하지 않으므로 새로 추가해주면서 문자열의 끝이라는 의미로 빨갛게 표시한다.
문자열 CDF는 첫 문자인 C에 대한 노드가 없으므로 문자열 AB를 추가하는 과정과 마찬가지로 각 문자에 대해 노드를 새로 추가해주면 된다.
📁트라이의 장단점
- 문자열 검색을 빠르게 할 수 있다.
트라이의 최대 장점이다. 원하는 원소를 찾기 위해 자주 사용되는 이진 탐색 트리는 원소를 찾는데 O(logN)의 시간이 걸리게 된다. 하지만, 문자열의 경우 두 문자열을 비교하기 위해서는 문자열의 길이만큼의 시간이 추가로 필요하기 때문에 원하는 문자열을 찾기 위해서는 O(MlogN)의 시간이 걸리게 된다.
반면에 트라이를 사용하는 경우, 문자열의 길이만큼 노드를 따라가며 원하는 문자열을 찾으면 되기 때문에 O(M)의 시간에 검색이 가능하다.
- 메모리 측면에서 비효율적일 수 있다.
문자열이 모두 영소문자로 이루어져 있다고 해도, 각 노드는 자식 노드를 가리키는 최대 26개의 포인터를 저장해야 한다.
최악의 경우에는 문자열들의 길이의 총합만큼 노드가 필요하므로, 필요한 메모리는 O(포인터 크기 x 포인터 배열 수 x 총 노드의 수)가 된다.
📁구현
다음은 트라이에서 노드로 사용될 구조체에 대한 코드이다.
struct TRIE {
bool finish;
TRIE *child[26];
TRIE() {
finish = false;
for (int i = 0; i < 26; i++) child[i] = NULL;
}
}finish는 문자열의 끝을 의미한다. 문자열의 마지막 문자 노드는 finish의 값을 true로 한다. child 배열에는 노드의 자식 노드에 대한 포인터를 저장한다.
다음은 트라이에 문자열을 삽입하는 코드이다.
void insert(char *str) {
if (*str == NULL) {
finish = true;
return;
}
int cur = *str - 'A';
if (child[cur] == NULL) child[cur] = new TRIE();
child[cur]->insert(str + 1);
}
str에 저장된 문자를 삽입한다. cur에 문자에 대한 아스키코드 값에서 A의 아스키코드 값을 뺀 값을 저장한다. 이 값은 child 배열에 노드를 저장할 때 인덱스로 사용된다.
노드가 존재하지 않는 경우, 새로 노드를 생성하여 저장하고, 다음 문자를 삽입하기 위해 insert 함수를 재귀 호출한다.
마지막 문자까지 저장한 후에는 마지막 노드의 finish 값을 true로 바꿔준다.
다음은 트라이에서 문자열을 검색하는 코드이다.
bool find(char *str) {
if (*str == NULL) {
if (finish == true) return true;
return false;
}
int cur = *str - 'A';
if (child[cur] == NULL) return false;
return child[cur]->find(str + 1);
}str에 저장된 문자열을 트라이에서 검색한다. 만약 마지막 문자까지 도달하지 못했는데 더이상 노드가 존재하지 않거나 마지막 문자까지 도달했지만 finish의 값이 true가 아니라면 문자열을 찾지 못한 것이므로 false를 반환한다.
