이 글에서는 B-트리(B-Tree)를 이용해 정렬된 순서(sorted sequence)를 얻는 방법을 살펴봅니다. B-트리는 하나의 노드가 여러 개의 자식을 가질 수 있는 n진 트리(n-ary tree)입니다. 정렬된 순서를 얻으려면 먼저 B-트리를 생성한 뒤 숫자들을 차례대로 삽입하면 됩니다. 여기서 사용하는 B-트리는 한 노드가 최대 5개의 데이터를 저장할 수 있으며, 요소 수가 이 값을 초과하면 노드를 분할(split)하여 새로운 레벨을 형성합니다.
각 노드가 최대 5개 정도의 적은 수의 요소만 가지기 때문에, 노드 내부의 정렬에는 버블 정렬(bubble sort) 기법을 사용합니다. 정렬 대상 요소 수가 매우 적으므로 전체 성능에는 큰 영향을 주지 않습니다.
트리 순회(traversal)를 마치면 서로 다른 노드에 담긴 모든 값을 얻을 수 있으며, 이 요소들은 비내림차순(non-decreasing order), 즉 오름차순으로 정렬되어 출력됩니다.
알고리즘
traverse(p)
입력: 트리 노드 p
출력: 트리의 순회 순서
Begin
for i in range 0 to n-1, do
if p is not a leaf node, then
traverse(child of p at position i)
end if
print the data at position i
done
if p is not a leaf node, then
traverse(child of p at position i)
end if
End
sort(a, n)
입력: 정렬할 배열 a와 배열의 요소 개수 n
출력: 정렬된 배열
Begin
for i in range 0 to n-1, do
for j in range 0 to n-1, do
if a[i] > a[j], then
swap a[i] and a[j]
end if
done
done
End
split_node(x, i)
입력: 분할할 노드 x, 리프 노드인 경우 i는 -1, 그렇지 않으면 양수
출력: 분할 후 노드의 중간 요소
Begin
Create a node np3, and mark it as leaf node
if i is -1, then
mid := Data from position 2 of x
Set the data at position 2 of x to 0
Reduce the number of data in x by 1
create a new node called np1, and mark it as non-leaf node
mark x as leaf node
Insert all of the nodes of x from position 3 to 5 into np3
Also insert all of the child reference of x from position 3 to 5 into np3
Remove the inserted elements from the node x
insert mid into the first position of np1
make x as left child and np3 as right child of np1
increase the element count of np1, and make this as root.
else
y := the subtree at location i
mid := data from position 2 of y
Set the data at position 2 of y to 0
Reduce the number of data in y by 1
Insert all of the nodes of y from position 3 to 5 into np3
increase the element count of np3, and remove inserted elements from y
add y child at position i, and add np3 at position i+1
end if
End
insert(a)
입력: 삽입할 요소 a
출력: 갱신된 B-트리
Begin
x := root
if x is null, then
create a root node and take root into x
else
if x is leaf node, and has 5 elements, then
temp_node := split_child(x, -1)
x := root
i := find correct position to insert a
x := child of x at position i
else
while x is not a leaf node, do
i := find correct position to insert a
if child of x at position i, has 5 elements, then
temp_node := split_child(x, i)
add temp_node data at position x->n of x
else
x := child of x at position i
end if
done
end if
end if
add a into x at position x->n
sort elements of x
End
예제 코드
#include<iostream>
using namespace std;
struct BTreeNode{ // B-트리의 노드 구조체 생성
int *data;
BTreeNode **child_ptr;
bool leaf;
int n;
}*root = NULL, *np = NULL, *x = NULL;
BTreeNode * getNode(){
int i;
np = new BTreeNode;
np->data = new int[5]; // 5개의 데이터 필드와 6개의 링크 필드 설정
np->child_ptr = new BTreeNode *[6];
np->leaf = true; // 처음에는 노드를 리프 노드로 설정
np->n = 0;
for (i = 0; i < 6; i++) {
np->child_ptr[i] = NULL; // 모든 포인터를 NULL로 초기화
}
return np;
}
void traverse(BTreeNode *p) {
cout<<endl;
int i;
for (i = 0; i < p->n; i++) { // B-트리 전체를 재귀적으로 순회
if (p->leaf == false){
traverse(p->child_ptr[i]);
}
cout << " " << p->data[i];
}
if (p->leaf == false) {
traverse(p->child_ptr[i]);
}
cout<<endl;
}
void sort(int *p, int n) {
for (int i = 0; i < n; i++) {
for (int j = i; j <= n; j++) {
if (p[i] > p[j]){
swap(p[i], p[j]);
}
}
}
}
int split_child(BTreeNode *x, int i){ // 노드를 루트 하나와 자식 둘로 분할
int mid;
BTreeNode *np1, *np3, *y;
np3 = getNode(); // 새로운 리프 노드 np3 생성
np3->leaf = true;
if (i == -1) {
mid = x->data[2]; // 중간 요소 추출
x->data[2] = 0;
x->n--;
np1 = getNode();
np1->leaf = false;
x->leaf = true;
for (int j = 3; j < 5; j++) {
np3->data[j - 3] = x->data[j];
np3->child_ptr[j - 3] = x->child_ptr[j];
np3->n++;
x->data[j] = 0;
x->n--;
}
for (int j = 0; j < 6; j++) {
x->child_ptr[j] = NULL;
}
np1->data[0] = mid;
np1->child_ptr[np1->n] = x;
np1->child_ptr[np1->n + 1] = np3;
np1->n++;
root = np1;
} else {
y = x->child_ptr[i];
mid = y->data[2];
y->data[2] = 0;
y->n--;
for (int j = 3; j < 5; j++) {
np3->data[j - 3] = y->data[j];
np3->n++;
y->data[j] = 0;
y->n--;
}
x->child_ptr[i] = y;
x->child_ptr[i + 1] = np3;
}
return mid;
}
void insert(int a){ // B-트리에 요소 삽입
int i, tmp_node;
x = root;
if (x == NULL) {
root = getNode();
x = root;
} else {
if (x->leaf == true && x->n == 5){ // 노드가 리프이면서 5개의 데이터를 가질 때
tmp_node = split_child(x, -1); // 노드를 분할하여 새로운 레벨 생성
x = root;
for (i = 0; i < (x->n); i++) {
if ((a > x->data[i]) && (a < x->data[i + 1])) {
i++;
break;
} else if (a < x->data[0]) {
break;
} else {
continue;
}
}
x = x->child_ptr[i];
} else {
while (x->leaf == false) {
for (i = 0; i < (x->n); i++) {
if ((a > x->data[i]) && (a < x->data[i + 1])) {
i++;
break;
} else if (a < x->data[0]) {
break;
} else {
continue;
}
}
if ((x->child_ptr[i])->n == 5) {
tmp_node = split_child(x, i);
x->data[x->n] = tmp_node;
x->n++;
continue;
} else {
x = x->child_ptr[i];
}
}
}
}
x->data[x->n] = a;
sort(x->data, x->n);
x->n++;
}
int main() {
int i, n, t;
cout<<"삽입할 요소의 개수를 입력하세요\n";
cin>>n;
for(i = 0; i < n; i++) {
cout<<"요소를 입력하세요\n";
cin>>t;
insert(t);
}
cout<<"생성된 트리의 순회 결과\n";
traverse(root);
}
실행 결과
삽입할 요소의 개수를 입력하세요 8 요소를 입력하세요 54 요소를 입력하세요 23 요소를 입력하세요 98 요소를 입력하세요 52 요소를 입력하세요 10 요소를 입력하세요 23 요소를 입력하세요 47 요소를 입력하세요 84 생성된 트리의 순회 결과 10 23 23 47 52 54 84 98
위 실행 결과에서 볼 수 있듯이, 8개의 숫자를 무작위 순서로 삽입한 뒤 트리를 순회하면 10 23 23 47 / 52 / 54 84 98과 같이 값들이 오름차순으로 정렬되어 출력됩니다. 삽입 과정에서 노드가 가득 차면 자동으로 분할되어 새로운 레벨이 형성되며, 각 노드 내부에서는 버블 정렬을 통해 항상 정렬된 상태가 유지됩니다.