퓨전 트리(Fusion Tree)는 w비트(w-bit) 정수를 기반으로 연관 배열(associative array)을 구현하는 고급 트리 자료구조입니다. 이 글에서는 주어진 입력값을 바탕으로 6비트 정수 배열을 다루는 퓨전 트리를 C++로 구현하는 방법을 단계별로 살펴봅니다.
퓨전 트리란?
퓨전 트리는 B-트리의 변형된 형태로, 하나의 노드에 여러 개의 키를 저장하면서 비트 연산을 활용해 여러 키를 빠르게 비교할 수 있는 자료구조입니다. 이론적으로 n개의 요소를 저장할 때 일반적인 균형 트리보다 더 적은 비교 횟수로 검색이 가능하다는 장점이 있습니다.
이번에 구현할 프로그램은 각 노드가 최대 6개의 키를 저장할 수 있으며, 노드가 가득 차면 분할(split)하여 트리의 균형을 유지하는 방식으로 동작합니다.
알고리즘
프로그램 구현에 필요한 함수와 입력 절차는 다음과 같습니다.
Begin
트리에 삽입할 요소의 개수와 요소들을 입력받는다.
FusionTree 구조체를 선언하여 필요한 변수들을 정의한다.
init() 함수를 만들어 새 노드를 생성한다.
traverse() 함수를 만들어 트리를 순회한다.
sort() 함수를 만들어 노드 내 키 배열을 정렬한다.
split_child() 함수를 만들어 가득 찬 노드를 분할한다.
insert() 함수를 만들어 트리에 노드를 삽입한다.
main() 함수에서 insert()를 호출해 퓨전 트리를 구성한 뒤,
traverse()를 호출하여 결과를 출력한다.
End
예제 코드
#include<iostream>
using namespace std;
struct FusionTree//declaration of nodes {
int *d;
FusionTree **child_ptr;
bool l;
int n;
}*r = NULL, *np = NULL, *x = NULL;
FusionTree* init()//cretae new node {
int i;
np = new FusionTree;
np->d = new int[6];
np->child_ptr = new FusionTree *[7];
np->l = true;
np->n = 0;
for (i = 0; i < 7; i++) {
np->child_ptr[i] = NULL;
}
return np;
}
void traverse(FusionTree *p)//traverse the tree {
cout<<endl;
int i;
for (i = 0; i < p->n; i++) {
if (p->l == false) {
traverse(p->child_ptr[i]);
}
cout << " " << p->d[i];
}
if (p->l == false) {
traverse(p->child_ptr[i]);
}
cout<<endl;
}
void sort(int *p, int n)//sort the tree {
int i, j, t;
for (i = 0; i < n; i++) {
for (j = i; j <= n; j++) {
if (p[i] >p[j]) {
t = p[i];
p[i] = p[j];
p[j] = t;
}
}
}
}
int split_child(FusionTree *x, int i)//split the child {
int j, mid;
FusionTree *np1, *np3, *y;
np3 = init();// initialize new node
np3->l = true;
if (i == -1) {
mid = x->d[2];//calculate mid
x->d[2] = 0;
x->n--;
np1 = init();
np1->l = false;
x->l = true;
for (j = 3; j < 6; j++) {
np3->d[j - 3] = x->d[j];
np3->child_ptr[j - 3] = x->child_ptr[j];
np3->n++;
x->d[j] = 0;
x->n--;
}
for (j = 0; j < 6; j++) {
x->child_ptr[j] = NULL;
}
np1->d[0] = mid;
np1->child_ptr[np1->n] = x;
np1->child_ptr[np1->n + 1] = np3;
np1->n++;
r = np1;
} else {
y = x->child_ptr[i];
mid = y->d[2];
y->d[2] = 0;
y->n--;
for (j = 3; j <6 ; j++) {
np3->d[j - 3] = y->d[j];
np3->n++;
y->d[j] = 0;
y->n--;
}
x->child_ptr[i + 1] = y;
x->child_ptr[i + 1] = np3;
}
return mid;
}
void insert(int a) {
int i, t;
x = r;
if (x == NULL) {
r = init();
x = r;
} else {
if (x->l== true && x->n == 6) {
t = split_child(x, -1);
x = r;
for (i = 0; i < (x->n); i++) {
if ((a >x->d[i]) && (a < x->d[i + 1])) {
i++;
break;
} else if (a < x->d[0]) {
break;
} else {
continue;
}
}
x = x->child_ptr[i];
} else {
while (x->l == false) {
for (i = 0; i < (x->n); i++) {
if ((a >x->d[i]) && (a < x->d[i + 1])) {
i++;
break;
} else if (a < x->d[0]) {
break;
} else {
continue;
}
}
if ((x->child_ptr[i])->n == 6) {
t = split_child(x, i);
x->d[x->n] = t;
x->n++;
continue;
} else {
x = x->child_ptr[i];
}
}
}
}
x->d[x->n] = a;
sort(x->d, x->n);
x->n++;
}
int main() {
int i, n, t;
cout<<"enter the no of elements to be inserted\n";
cin>>n;
for(i = 0; i < n; i++) {
cout<<"enter the element\n";
cin>>t;
insert(t);
}
cout<<"traversal of constructed fusion tree\n";
traverse(r);
}
실행 결과
enter the no of elements to be inserted 7 enter the element 10 enter the element 20 enter the element 30 enter the element 40 enter the element 50 enter the element 60 enter the element 70 traversal of constructed fusion tree 10 20 30 40 50 60 70
코드 핵심 포인트
- 노드 구조: 각 노드는 최대 6개의 키(
d[6])와 7개의 자식 포인터(child_ptr[7])를 가질 수 있습니다. - 노드 분할: 노드가 가득 차면
split_child()가 중간 키를 계산해 부모 노드로 올리고, 나머지 키들은 두 개의 새 노드로 나눕니다. - 삽입 과정: 새로운 키는 항상 리프 노드에 추가되며, 추가 직후
sort()를 호출해 노드 내 키들이 항상 오름차순을 유지하도록 합니다. - 순회 결과: 위 실행 결과에서 7개의 정수(10~70)를 삽입한 뒤 트리를 순회하면 모든 키가 오름차순으로 출력됩니다. 이는 퓨전 트리가 올바르게 구성되었음을 보여줍니다.