여기서는 B-Tree를 사용하여 정렬된 시퀀스를 얻는 방법을 살펴보겠습니다. B-트리는 n-항 트리입니다. 정렬된 시퀀스를 얻으려면 B-트리를 만든 다음 숫자를 추가할 수 있습니다. 여기서 B-트리는 최대 5개의 노드를 보유할 수 있습니다. 노드의 수가 증가하면 노드를 분할하여 새로운 레벨을 형성합니다. 노드가 5개(최대)와 같이 적은 수의 요소를 보유하므로 버블 정렬 기술을 사용하여 정렬합니다. 요소 수가 매우 적기 때문에 성능에 큰 영향을 미치지 않습니다.
트리를 순회한 후에는 다른 노드의 모든 값을 얻을 수 있습니다. 이러한 요소는 내림차순으로 정렬됩니다.
알고리즘
횡단(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
정렬(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), 그렇지 않으면 일부 양수 값
출력 :분할 후 Node의 중간 요소
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
삽입(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{ //create a node structure of a B-tree
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]; //set five data fiels and 6 link field
np->child_ptr = new BTreeNode *[6];
np->leaf = true; //initially the node is a leaf
np->n = 0;
for (i = 0; i < 6; i++) {
np->child_ptr[i] = NULL; //initialize all pointer to null
}
return np;
}
void traverse(BTreeNode *p) {
cout<<endl;
int i;
for (i = 0; i < p->n; i++) { //recursively traverse the entire b-tree
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){ //split the node into three nodes, one root and two children
int mid;
BTreeNode *np1, *np3, *y;
np3 = getNode(); //create a new leaf node called np3
np3->leaf = true;
if (i == -1) {
mid = x->data[2]; //get the middle element
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){ //insert into BTree
int i, tmp_node;
x = root;
if (x == NULL) {
root = getNode();
x = root;
} else {
if (x->leaf == true && x->n == 5){ //when the node is a leaf node and has 5 data
tmp_node = split_child(x, -1); //make a new level by spliting the node
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<<"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 tree\n";
traverse(root);
} 출력
enter the no of elements to be inserted 8 enter the element 54 enter the element 23 enter the element 98 enter the element 52 enter the element 10 enter the element 23 enter the element 47 enter the element 84 traversal of constructed tree 10 23 23 47 52 54 84 98