1. 트라이 자료구조란?
: 효율적인 문자열 검색을 위한 트리 자료구조
정수형, 실수형 변수는 크기가 항상 정해져 있기 때문에 비교 연산에 상수 시간이 걸린다고 가정할 수 있습니다.
그러나, 문자열 변수를 비교하는데는 최악의 경우 문자열의 길이에 비례하는 시간이 걸립니다.
n개의 원소를 갖는 이진 검색 트리에서 원하는 원소를 찾기 위해서는 O(log n) 번의 비교가 필요합니다.
따라서 원소 간의 비교를 상수 시간에 할 수 있을 때는 탐색의 시간 복잡도가 O(log n)이지만
비교 대상이 문자열인 경우, 비교에 문자열의 길이에 비례하는 시간이 걸리므로
문자열 검색의 시간복잡도는 문자열의 최대 길이 m을 곱한 O(m log n)이 됩니다.
이런 문제를 해결하고자 나온 자료구조가 트라이(Trie)입니다.
트라이 자료구조는 문자열의 집합을 트리 형태로 저장함으로써, 원하는 원소(문자열)을 찾는 작업을 O(m) 시간만에 할 수 있습니다.
2. 구조
트라이 자료구조는 문자열의 접두사에 대응되는 노드들이 서로 연결된 트리입니다. (루트: 빈 문자열)
문자열 집합 {"tree", "tea", "ten"} 을 저장하는 트라이는 다음과 같이 나타낼 수 있습니다.
(tree: 루트에서부터 차례대로 t -> tr -> tre -> tree)
3. 장/단점
시간 복잡도 측면에서, 트라이 자료구조를 사용하면 문자열 등의 자료를 빠르게 탐색할 수 있다는 장점이 있지만,
공간 복잡도 측면에서는 자식 노드를 가리키는 포인터 목록을 고정 길이 배열로 가지고 있기 때문에
메모리 낭비가 심하다는 단점이 있습니다.
4. 구현
boilerplate 코드: https://github.com/YuriKwon/Algorithm/blob/main/template/Trie.cpp
Node - 데이터
트라이의 노드를 표현하는 객체(구조체)는
- 현재 노드가 leef 노드인지 나타내는 boolean값: isEnd
- 자식 노드들을 가리키는 포인터의 배열: children
이 두가지 데이터를 갖습니다.
이 때 children 배열의 길이는 자식 노드의 최대 개수가 됩니다. (고정 길이 배열)
즉, 알파벳 대문자로만 구성된 문자열을 저장하는 트라이라면 각 노드가 저장하고 있는 children 배열의 길이가 26이 되는 것입니다.
현재 노드가 단어의 마지막 노드인지 알려주는 isEnd는 자동 완성 기능 등을 구현하는데 필요합니다.
Node - Insert, Find
트라이의 핵심 동작으로는 Insert, Find가 있습니다.
삽입의 경우 구조체 생성자를 이용해 루트 노드를 만든 뒤,
해당 루트 노드에 문자열을 Insert 하는 방식으로 이루어집니다.
Find의 경우 검색하고자 하는 문자열이 (트라이에) 저장된 문자열과 완전히 일치할 때만 true를 반환하도록 구현하는 방법,
접두사인 경우에도 true를 반환하도록 하는 방법 두가지 형태로 구현할 수 있습니다.
구현 코드는 다음과 같습니다.
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
const int ALPHABETS_CNT = 26;
int charToIdx(char ch) {
return ch - 'a';
}
// 트라이의 한 노드를 나타내는 객체
struct TrieNode {
bool isEnd;
TrieNode* children[ALPHABETS_CNT]; // 자손 노드들을 가리키는 포인터 목록
// 고정 길이 배열 (알파벳 대문자라면, 길이 26으로 고정) -> 메모리 낭비 큼
// 생성자
TrieNode() : isEnd(false) {
memset(children, 0, sizeof(children));
}
// 소멸자
~TrieNode() {
for (int i=0; i<ALPHABETS_CNT; i++) {
if (children[i]) delete children[i];
}
}
void insert(const char* key) {
cout << *key << endl;
if (*key == '\0') isEnd = true;
else {
int next = charToIdx(*key);
if (children[next] == NULL) children[next] = new TrieNode();
children[next] -> insert(key + 1);
}
}
// 접두사 검색 (자동완성 기능 구현 시 필요)
bool find(const char* key) {
if (*key == '\0') return true;
int next = charToIdx(*key);
if (children[next] == NULL) return false;
return children[next] -> find(key + 1);
}
// 완전히 일치하는 경우만 검색
bool find2(const char* key) {
if (*key == '\0' && isEnd) return true;
if (*key == '\0' && !isEnd) return false;
int next = charToIdx(*key);
if (children[next] == NULL) return false;
return children[next] -> find2(key + 1);
}
};
int main() {
vector <string> words = {"yuri", "apple", "banana"};
TrieNode root;
for (string word : words) {
const char* ptr = &word[0];
root.insert(ptr);
}
cout << root.find("yu") << " " << root.find("yut") << " " << root.find("yur") << endl; // t f t
cout << root.find2("yu") << " " << root.find2("yur") << " " << root.find2("yuri"); // f f t
return 0;
}
5. Reference
- 책 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 2> 구종만, 인사이트
- 위키백과 - 트라이(컴퓨팅)
- C++ 문자열 집합: 트라이 자료구조
- [자료구조] 트라이(Trie) C++ 구현
'CS > 자료구조' 카테고리의 다른 글
| [자료구조/JAVA] 배열(Array) (0) | 2022.03.17 |
|---|