자료구조 - 트라이(Trie)
정리
트라이란?
문자열의 집합을 표현하는 트리 자료구조이다
여러 개의 문자열을 가지고 있을 때, 어떤 문자열이 그 문자열들에 포함되는지 비교하려면 어떻게 해야할까?
가장 간단한 방법은 일일이 비교하는 것이지만 성능 상 안 좋을것이다
문자열들의 집합인 사전에서 단어 검색, 자동 완성, 접두사 검색 등에 유용하면서 문자열 저장을 위한 메모리를 사용하지만 시간 복잡도가 매우 효율적이라 문자열을 저장하고 검색하는 데 유용한 자료구조가 트라이이다
트라이는 트리 구조로 루트 노드는 항상 비어있고 다른 노드들은 한 개의 문자를 나타낸다. 루트 노드의 자식 노드는 각 문자열의 첫 글자이다
예시
문자열의 집합 {bridge, brother, duck, date, day}가 있을 때
트라이 자료구조로 나타내면 다음과 같다
파란색으로 칠한 것은 문자열의 마지막 글자를 나타낸다
트라이 자료구조의 중요한 특징 중 하나는 루트 노드에서부터 문자열을 탐색해나가면 문자열의 접두사를 쉽게 얻을 수 있다
b -> br -> bri -> brid -> bridg -> bridge
구현
일단 트라이 자료구조의 각 노드가 어떻게 구성될까??
각 노드는 자식 노드를 저장해야한다
각 노드마다 자식 노드를 빠르게 찾기 위해 unordered_map<char, TrieNode*> 타입으로 자식 노드를 저장할 맵을 가진다
그리고 현재 노드가 이 문자열의 끝인지를 나타내는 부울 변수를 둔다
class TrieNode
{
unordered_map<char, TrieNode*> children;
bool isEnd;
};트라이 자료구조의 주요 연산 3가지는
- 삽입 : 문자열을 트라이에 삽입한다
- 검색 : 특정 문자열이 트라이에 존재하는지 확인한다
- 삭제 : 특정 문자열을 트라이에서 삭제함
삽입
루트 노드부터 자식노드를 담은 Map에서 삽입할 문자열의 한 문자씩 찾아 본 뒤, 없으면 추가하고 있으면 트리를 계속 탐색한다
문자열의 마지막 노드가 되면 노드에 마지막 노드라는 표시를 한다
탐색
위의 그림을 참고해 "date"가 있는지 찾아보자
탐색 도중 원하지 않는 값이 존재한다면 트라이에는 "date"가 들어있지 않는 것이다
- 루트 노드의 자식 노드 중 'd'가 있는 지 검색하고 찾으면 이동한다
- 'd'의 자식 노드 중 'a'를 확인한다
- 'a'의 자식 중 't'를 확인한다
- 't'의 자식 중 'e'를 확인한다
- 't'는 "date"의 마지막 글자이고 노드에 부울 변수로 기록되어 있으니 탐색을 성공했다(부울 변수가 false라면 탐색 실패)
삭제
이번엔 "bridge"를 삭제해본다
- 탐색에서 했던 방법으로 "bridge"의 마지막 노드로 이동한다
- 마지막 노드('e')에 bool 변수가 true로 설정되어 있으면 삭제 성공 후 false로 바꾼다
- 'e'의 자식노드가 있는지 확인 후 없으면 거꾸로 탐색하며 노드를 삭제한다
- 'i'까지 삭제 후 'r'로 이동했는데 'r'에는 다른 자식 노드가 있으므로 'r'은 삭제하지 않는다
이제 진짜 구현해보자. 트라이 클래스의 생성자에서 루트 노드를 초기화해준다
전체 코드
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
class TrieNode
{
public:
unordered_map<char, TrieNode*> children;
bool isEnd;
};
class Trie
{
private:
TrieNode* root;
bool DeleteHelp(TrieNode* current, const string& word, int index)
{
// 문자열의 끝에 도달한 경우
if (index == word.size())
{
// 해당 노드가 문자열의 끝이 아니라면, 삭제할 단어가 없음
if (!current->isEnd)
return false;
// 단어의 끝을 표시하는 플래그를 제거
current->isEnd = false;
// 자식 노드가 없으면 true 반환
return current->children.empty();
}
char ch = word[index];
TrieNode* node = current->children[ch];
// 삭제할 단어가 존재하지 않음
if (node == nullptr)
{
return false;
}
// 재귀적으로 다음 노드로 이동
bool deleteCurrentNode = DeleteHelp(node, word, index + 1);
// 하위 노드를 삭제할 수 있는 경우, 현재 노드의 자식에서 제거
if (deleteCurrentNode)
{
current->children.erase(ch);
// 현재 노드가 단어의 끝이 아니고, 다른 자식이 없으면 true 반환
return current->children.empty() && !current->isEnd;
}
return false;
}
public:
Trie()
{
root = new TrieNode();
}
void Insert(const string& word)
{
TrieNode* current = root;
for (char c : word)
{
// 해당 문자가 자식 노드에 존재하지 않는다 == 자식 노드를 추가해준다
if (current->children.find(c) == current->children.end())
{
current->children[c] = new TrieNode();
}
// 추가했거나 이미 있는 문자면 현재 노드를 옮겨준다
current = current->children[c];
}
// 모든 문자까지 탐색 후 마지막이니 부울 변수 세팅
current->isEnd = true;
}
bool Search(const string& word)
{
TrieNode* current = root;
for (char c : word)
{
// 해당 문자가 자식 노드에 존재하지 않는다 == 탐색에 실패했으니 바로 false 리턴
if (current->children.find(c) == current->children.end())
{
return false;
}
// 탐색 성공 시 현재 노드를 옮겨줌
current = current->children[c];
}
// 진짜 마지막 문자열인지 확인
return current->isEnd;
}
bool CheckPrefix(const string& prefix)
{
TrieNode* current = root;
for (char c : prefix)
{
if (current->children.find(c) == current->children.end())
{
return false;
}
current = current->children[c];
}
return true;
}
void Remove(const string& word)
{
DeleteHelp(root, word, 0);
}
};
int main()
{
Trie trie;
// 삽입
trie.Insert("bridge");
trie.Insert("brother");
trie.Insert("duck");
trie.Insert("date");
trie.Insert("day");
cout << "'date' 탐색 : " << (trie.Search("date") ? "찾음" : "못 찾음") << '\n';
trie.Remove("date");
cout << "'date' 탐색 : " << (trie.Search("date") ? "찾음" : "못 찾음") << '\n';
return 0;
}회고
트라이 자료구조의 존재 자체는 알고 있었는데 공부해보려고는 못하다가 오늘 마침내 해봤다
트라이나 세그먼트 트리 같은거나 보면 트리가 약간 고수들의 알고리즘을 위한 자료구조인것같다
아직 트리에 빠삭하다고는 말을 못하겠어서 트리와 관련된 문제를 많이 풀어봐야겠다
트라이를 이용한 문제가 백준에 있으니 이 문제를 한번 풀어보자
참고
