이 글에서는 트라이(Trie) 자료구조를 구현하는 C++ 프로그램을 살펴봅니다. 트라이는 트리 기반의 자료구조로, 대량의 문자열 데이터 집합에서 특정 키(key)를 매우 효율적으로 검색하기 위해 사용됩니다.
트라이는 문자열을 한 글자씩 노드로 연결해 저장하며, 각 노드는 알파벳(A~Z) 개수만큼의 자식 포인터를 가질 수 있습니다. 이러한 구조 덕분에 검색 시간은 키의 길이에 비례하여 O(L)(L은 키의 길이)로 매우 빠릅니다. 사전(단어장), 자동완성, 접두사 검색 등에 널리 활용됩니다.
주요 함수와 의사 코드
트라이 구현에는 크게 두 가지 핵심 연산이 필요합니다. 바로 삽입(insert)과 삭제(deleteNode)입니다.
1. insert() — 키 삽입
Begin
function insert() :
If key not present, inserts key into trie.
If the key is prefix of trie node, just mark leaf node.
End
삽입 함수는 해당 키가 아직 트라이에 없다면 새로 추가하고, 이미 다른 단어의 접두사로 존재한다면 마지막 노드를 리프(leaf) 노드로 표시만 하면 됩니다.
2. deleteNode() — 키 삭제
Begin
function deleteNode()
If tree is empty then return null.
If last character of the key is being processed,
then that node will be no more end of string after deleting it.
If given key is not prefix of any other string, then delete it and set root = NULL.
If key is not the last character,
Then recur for the child which will be obtained by using ASCII value.
If root does not have any child left and it is not end of another word,
Then delete it and set root = NULL.
End
삭제는 재귀적으로 처리됩니다. 트리가 비어 있으면 NULL을 반환하고, 키의 마지막 문자에 도달하면 해당 노드의 '단어 끝' 표시를 해제합니다. 만약 그 노드가 다른 단어의 접두사가 아니라면 메모리에서 삭제하고, 부모 노드 역시 더 이상 자식이 없고 다른 단어의 끝이 아니라면 함께 제거합니다.
C++ 전체 예제 코드
#include <bits/stdc++.h>
using namespace std;
const int ALPHA_SIZE = 26;
struct Trie {
struct Trie *child[ALPHA_SIZE];
bool endofstring; //It is true if node represents end of word.
};
struct Trie *createNode(void) //creation of new node {
struct Trie *tNode = new Trie;
tNode->endofstring = false;
for (int i = 0; i < ALPHA_SIZE; i++)
tNode->child[i] = NULL;
return tNode;
}
void insert(struct Trie *root, string key) {
struct Trie *curr = root;
for (int i = 0; i < key.length(); i++) {
int index = key[i] - 'A';
if (!curr->child[index])
curr->child[index] = createNode();
curr = curr->child[index];
}
curr->endofstring= true; //last node as leaf
}
bool search(struct Trie *root, string key) { //check if key is present in trie. If present returns true
struct Trie *curr = root;
for (int i = 0; i < key.length(); i++) {
int index = key[i] - 'A';
if (!curr->child[index])
return false;
curr = curr->child[index];
}
return (curr != NULL && curr->endofstring);
}
bool isEmpty(Trie* root) //check if root has children or not {
for (int i = 0; i < ALPHA_SIZE; i++)
if (root->child[i])
return false;
return true;
}
Trie* deletion(Trie* root, string key, int depth = 0) {
//If tree is empty return null.
if (!root)
return NULL;
if (depth == key.size()) { //If last character of key is being processed,
if (root->endofstring)
root->endofstring = false; //then that node will be no more end of string after deleting it.
if (isEmpty(root)) { //If given key is not prefix of any other string,
delete (root);
root = NULL;
}
return root;
}
//If key not last character,
int index = key[depth] - 'A';
root->child[index] =
deletion(root->child[index], key, depth + 1); //Then recur for the child which will be obtained by using ASCII value.
if (isEmpty(root) && root->endofstring == false) { //If root does not have any child leftand it is not end of another word
delete (root);
root = NULL;
}
return root;
}
int main() {
string inputs[] = {"HELLOWORLD","HI","BYE", "THE","THENA"}; // Input keys ( only A to Z in upper case)
int n = sizeof(inputs)/sizeof(inputs[0]);
struct Trie *root = createNode();
for (int i = 0; i < n; i++)
insert(root, inputs[i]);
search(root, "HELLOWORLD")? cout << "Key is Found\n" :
cout << "Key is not Found\n";
search(root, "HE")? cout << "Key is Found\n" :
cout << "Key is not Found\n";
deletion(root, "THEN")? cout << "Key is deleted\n" :
cout << "Key is not Deleted\n";
return 0;
}
코드 동작 원리 요약
- createNode(): 새 노드를 생성하고 모든 자식 포인터를 NULL로 초기화합니다.
- insert(): 키의 각 문자를 ASCII 값으로 인덱스화하여 자식 노드를 따라가며, 없으면 새 노드를 생성합니다. 마지막 노드는 단어의 끝(endofstring = true)으로 표시합니다.
- search(): 키의 문자를 순서대로 따라가며 경로가 끊기면 false를 반환하고, 마지막 노드가 단어의 끝일 때만 true를 반환합니다.
- deletion(): 재귀 호출로 키의 끝까지 내려간 뒤, 단어 끝 표시를 해제하고 불필요한 노드를 아래에서부터 정리합니다.
실행 결과
Key is Found Key is not Found Key is deleted
위 실행 결과를 보면, HELLOWORLD는 트라이에 존재하므로 "Key is Found"가 출력되고, HE는 다른 단어의 접두사일 뿐 완전한 단어가 아니므로 "Key is not Found"가 출력됩니다. 또한 THEN 삭제 연산이 성공적으로 수행되어 "Key is deleted"가 출력됩니다.