스레드 이진 트리(Threaded Binary Tree)는 트리를 특정 순서대로 순회할 수 있도록 설계된 이진 트리입니다. 일반적인 이진 트리와 달리, 스택이나 재귀 호출 없이도 중위 순회(inorder traversal)를 더 빠르게 수행할 수 있다는 것이 가장 큰 장점입니다.
스레드 이진 트리는 널(NULL) 포인터를 활용하는 방식에 따라 두 가지 유형으로 나뉩니다.
스레드 이진 트리의 종류
단일 스레드(Single Threaded)
각 노드가 왼쪽 또는 오른쪽 한 방향으로만 스레드를 가지는 형태입니다. 즉, 모든 오른쪽 널 포인터가 중위 후속자(inorder successor)를 가리키거나, 모든 왼쪽 널 포인터가 중위 선행자(inorder predecessor)를 가리킵니다.
이중 스레드(Double Threaded)
각 노드가 왼쪽과 오른쪽 양방향 모두 스레드를 가지는 형태입니다. 오른쪽 널 포인터는 중위 후속자를, 왼쪽 널 포인터는 중위 선행자를 동시에 가리킵니다.
아래는 C++로 스레드 이진 트리를 구현한 프로그램입니다.
주요 함수 및 의사 코드(Pseudocode)
insert() 함수 — 삽입
트리가 완전히 비어 있다면 새 노드를 루트로 삽입합니다.
그렇지 않고, 새 노드 < 현재 노드라면
왼쪽 스레드로 이동하여 새 노드를 왼쪽 자식으로 설정합니다.
그렇지 않다면
오른쪽 스레드로 이동하여 새 노드를 오른쪽 자식으로 설정합니다.search() 함수 — 검색
검색 키 < 루트라면
왼쪽 스레드로 이동합니다.
그렇지 않다면
오른쪽 스레드로 이동합니다.Delete() 함수 — 삭제
먼저 삭제할 노드와 그 부모 노드를 찾습니다. 노드 삭제는 다음 세 가지 경우로 나누어 처리합니다.
- 자식이 두 개 있는 노드
- 왼쪽 자식만 있는 노드
- 오른쪽 자식만 있는 노드
C++ 전체 예제 코드
#include <iostream>
#include <cstdlib>
#define MAX_VALUE 65536
using namespace std;
class N { //노드 선언
public:
int k;
N *l, *r;
bool leftTh, rightTh;
};
class ThreadedBinaryTree {
private:
N *root;
public:
ThreadedBinaryTree() { //변수 초기화 생성자
root= new N();
root->r= root->l= root;
root->leftTh = true;
root->k = MAX_VALUE;
}
void makeEmpty() { //트리 비우기
root= new N();
root->r = root->l = root;
root->leftTh = true;
root->k = MAX_VALUE;
}
void insert(int key) {
N *p = root;
for (;;) {
if (p->k< key) { //오른쪽 스레드로 이동
if (p->rightTh)
break;
p = p->r;
} else if (p->k > key) { //왼쪽 스레드로 이동
if (p->leftTh)
break;
p = p->l;
} else {
return;
}
}
N *temp = new N();
temp->k = key;
temp->rightTh= temp->leftTh= true;
if (p->k < key) {
temp->r = p->r;
temp->l= p;
p->r = temp;
p->rightTh= false;
} else {
temp->r = p;
temp->l = p->l;
p->l = temp;
p->leftTh = false;
}
}
bool search(int key) {
N *temp = root->l;
for (;;) {
if (temp->k < key) { //왼쪽 스레드에서 검색
if (temp->rightTh)
return false;
temp = temp->r;
} else if (temp->k > key) { //오른쪽 스레드에서 검색
if (temp->leftTh)
return false;
temp = temp->l;
} else {
return true;
}
}
}
void Delete(int key) {
N *dest = root->l, *p = root;
for (;;) { //노드와 부모 노드 탐색
if (dest->k < key) {
if (dest->rightTh)
return;
p = dest;
dest = dest->r;
} else if (dest->k > key) {
if (dest->leftTh)
return;
p = dest;
dest = dest->l;
} else {
break;
}
}
N *target = dest;
if (!dest->rightTh && !dest->leftTh) {
p = dest; //자식이 두 개인 경우
target = dest->l; //왼쪽 자식 중 가장 큰 노드
while (!target->rightTh) {
p = target;
target = target->r;
}
dest->k= target->k; //값 교체
}
if (p->k >= target->k) { //왼쪽 자식만 있는 경우
if (target->rightTh && target->leftTh) {
p->l = target->l;
p->leftTh = true;
} else if (target->rightTh) {
N*largest = target->l;
while (!largest->rightTh) {
largest = largest->r;
}
largest->r = p;
p->l= target->l;
} else {
N *smallest = target->r;
while (!smallest->leftTh) {
smallest = smallest->l;
}
smallest->l = target->l;
p->l = target->r;
}
} else {//오른쪽 자식만 있는 경우
if (target->rightTh && target->leftTh) {
p->r= target->r;
p->rightTh = true;
} else if (target->rightTh) {
N *largest = target->l;
while (!largest->rightTh) {
largest = largest->r;
}
largest->r= target->r;
p->r = target->l;
} else {
N *smallest = target->r;
while (!smallest->leftTh) {
smallest = smallest->l;
}
smallest->l= p;
p->r= target->r;
}
}
}
void displayTree() { //트리 출력
N *temp = root, *p;
for (;;) {
p = temp;
temp = temp->r;
if (!p->rightTh) {
while (!temp->leftTh) {
temp = temp->l;
}
}
if (temp == root)
break;
cout<<temp->k<<" ";
}
cout<<endl;
}
};
int main() {
ThreadedBinaryTree tbt;
cout<<"ThreadedBinaryTree\n";
char ch;
int c, v;
while(1) {
cout<<"1. Insert "<<endl;
cout<<"2. Delete"<<endl;
cout<<"3. Search"<<endl;
cout<<"4. Clear"<<endl;
cout<<"5. Display"<<endl;
cout<<"6. Exit"<<endl;
cout<<"Enter Your Choice: ";
cin>>c;
//switch 문 실행
switch (c) {
case 1 :
cout<<"Enter integer element to insert: ";
cin>>v;
tbt.insert(v);
break;
case 2 :
cout<<"Enter integer element to delete: ";
cin>>v;
tbt.Delete(v);
break;
case 3 :
cout<<"Enter integer element to search: ";
cin>>v;
if (tbt.search(v) == true)
cout<<"Element "<<v<<" found in the tree"<<endl;
else
cout<<"Element "<<v<<" not found in the tree"<<endl;
break;
case 4 :
cout<<"\nTree Cleared\n";
tbt.makeEmpty();
break;
case 5:
cout<<"Display tree: \n ";
tbt.displayTree();
break;
case 6:
exit(1);
default:
cout<<"\nInvalid type! \n";
}
}
cout<<"\n";
return 0;
}실행 결과
ThreadedBinaryTree 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 1 Enter integer element to insert: 10 Enter Your Choice: 1 Enter integer element to insert: 7 Enter Your Choice: 1 Enter integer element to insert: 6 Enter Your Choice: 1 Enter integer element to insert: 4 Enter Your Choice: 1 Enter integer element to insert: 5 Enter Your Choice: 1 Enter integer element to insert: 3 Enter Your Choice: 5 Display tree 3 4 5 6 7 10 Enter Your Choice: 3 Enter integer element to search: 7 Element 7 found in the tree Enter Your Choice: 3 Enter integer element to search: 1 Element 1 not found in the tree Enter Your Choice: 2 Enter integer element to delete: 3 Enter Your Choice: 5 Display tree 4 5 6 7 10 Enter Your Choice: 4 Tree Cleared Enter Your Choice: 5 Display tree Enter Your Choice: 6
정리
스레드 이진 트리는 널 포인터를 스레드로 활용해 중위 순회 시 스택과 재귀 없이 선형 시간에 순회할 수 있는 효율적인 자료구조입니다. 위 예제는 삽입, 삭제, 검색, 전체 출력 기능을 메뉴 형태로 제공하며, 실제 실행 결과를 통해 중위 순회 순서대로 정렬된 값이 출력되는 것을 확인할 수 있습니다.