삼항 트리(Ternary Tree)란?
삼항 트리는 각 노드가 최대 세 개의 자식 노드를 가질 수 있는 트리 자료구조입니다. 세 개의 자식 노드는 일반적으로 '왼쪽(left)', '중앙(mid)', '오른쪽(right)'으로 표현됩니다.
이 트리에서 자식 노드를 가진 노드는 부모 노드가 되며, 자식 노드는 필요에 따라 부모 노드에 대한 참조를 가질 수 있습니다. 삼항 트리는 특히 문자열 집합을 저장하고 빠르게 검색하는 데 유용하며, 이런 용도로 사용될 때는 '삼항 검색 트리(Ternary Search Tree)'라고도 불립니다.
이번 글에서는 C++를 활용해 삼항 트리를 구현하고, 트리를 순회(traversal)하여 저장된 모든 문자열을 출력하는 프로그램을 만들어 보겠습니다.
삽입(Insert) 알고리즘
새로운 단어를 삼항 트리에 삽입하는 절차는 다음과 같습니다.
Begin
Declare function insert(struct nod** root, char *w)
if (!(*root)) then
*root = newnod(*w);
if ((*w) < (*root)->d) then
insert(&((*root)->l), w);
else if ((*w) > (*root)->d) then
insert(&((*root)->r), w);
else if (*(w+1)) then
insert(&((*root)->eq), w+1);
else
(*root)->EndOfString = 1;
End.
삽입 로직의 핵심을 정리하면 다음과 같습니다.
- 현재 문자가 노드의 문자보다 작으면 왼쪽(l) 서브트리로 이동합니다.
- 크면 오른쪽(r) 서브트리로 이동합니다.
- 같으면 다음 문자를 중앙(eq) 자식으로 재귀적으로 삽입합니다.
- 문자열의 끝에 도달하면 해당 노드의
EndOfString플래그를 1로 설정해 단어의 완성을 표시합니다.
순회(Traversal) 알고리즘
Begin
Declare function traverseTTtil(struct nod* root, char* buffer, int depth)
if (root) then
traverseTTtil(root->l, buffer, depth);
buffer[depth] = root->d;
if (root->EndOfString) then
buffer[depth+1] = '\0';
print the value of buffer.
traverseTTtil(root->eq, buffer, depth + 1);
traverseTTtil(root->r, buffer, depth);
End.
순회 함수는 중위 순회(in-order traversal) 방식으로 동작합니다. 왼쪽 서브트리를 먼저 방문한 뒤 현재 문자를 버퍼에 기록하고, 단어가 완성된 지점에서 버퍼를 출력합니다. 이후 중앙 서브트리(다음 문자)와 오른쪽 서브트리를 차례로 순회합니다. 덕분에 결과물이 항상 사전순(alphabetical order)으로 정렬되어 출력됩니다.
C++ 전체 예제 코드
#include<stdlib.h>
#include<iostream>
using namespace std;
struct nod {
char d;
unsigned EndOfString : 1;
struct nod *l, *eq, *r;
} *t = NULL;
struct nod* newnod(char d) {
t = new nod;
t->d = d;
t->EndOfString = 0;
t->l = t->eq = t->r = NULL;
return t;
}
void insert(struct nod** root, char *w) {
if (!(*root))
*root = newnod(*w);
if ((*w) < (*root)->d)
insert(&((*root)->l), w);
else if ((*w) > (*root)->d)
insert(&((*root)->r), w);
else {
if (*(w+1))
insert(&((*root)->eq), w+1);
else
(*root)->EndOfString = 1;
}
}
void traverseTTtil(struct nod* root, char* buffer, int depth) {
if (root) {
traverseTTtil(root->l, buffer, depth);
buffer[depth] = root->d;
if (root->EndOfString) {
buffer[depth+1] = '\0';
cout << buffer << endl;
}
traverseTTtil(root->eq, buffer, depth + 1);
traverseTTtil(root->r, buffer, depth);
}
}
void traverseTT(struct nod* root) {
char buffer[50];
traverseTTtil(root, buffer, 0);
}
int main() {
struct nod *root = NULL;
insert(&root, "mat");
insert(&root, "bat");
insert(&root, "hat");
insert(&root, "rat");
cout << "Following is traversal of ternary tree\n";
traverseTT(root);
}
실행 결과
Following is traversal of ternary tree bat hat mat rat
출력 결과를 보면 입력 순서(mat, bat, hat, rat)와 관계없이 모든 단어가 사전순(bat → hat → mat → rat)으로 정렬되어 출력되는 것을 확인할 수 있습니다. 이는 삼항 트리의 순회가 본질적으로 정렬된 순서를 보장하기 때문입니다.
마무리
삼항 트리는 이진 탐색 트리의 메모리 효율성과 트라이(Trie)의 빠른 문자열 검색 능력을 절충한 자료구조입니다. 자동완성, 맞춤법 검사기, 사전 구현 등 문자열 처리가 많은 애플리케이션에서 널리 활용되므로, 위 예제 코드를 직접 실행해 보며 동작 원리를 익혀보시기 바랍니다.