Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

B 트리를 구현하는 C++ 프로그램

<시간/>

B-트리는 노드가 두 개 이상의 자식을 가질 수 있다는 점에서 이진 탐색 트리의 일반화입니다. 기본적으로 정렬된 데이터를 유지하고 로그 시간에 순차적인 액세스, 검색, 삽입 및 삭제를 허용하는 자체 균형 트리 데이터 구조입니다.

다음은 6차 B 트리를 구현하는 C++ 프로그램입니다.

알고리즘

Begin
   function insert() to insert the nodes into the tree:
      Initialize x as root.
   if x is leaf and having space for one more info then insert a to x.
   else if x is not leaf, do
      Find the child of x that is going to be traversed next.
      If the child is not full, change x to point to the child.
      If the child is full, split it and change x to point to one of the two parts of the child. If a is smaller
      than mid key in the child, then set x as first part of the child. Else second part of the child. When split    the child, move a key from the child to its parent x.
End

예시 코드

#include<iostream>
using namespace std;
struct BTree//node declaration {
   int *d;
   BTree **child_ptr;
   bool l;
   int n;
}*r = NULL, *np = NULL, *x = NULL;

BTree* init()//creation of node {
   int i;
   np = new BTree;
   np->d = new int[6];//order 6
   np->child_ptr = new BTree *[7];
   np->l = true;
   np->n = 0;
   for (i = 0; i < 7; i++) {
      np->child_ptr[i] = NULL;
   }
   return np;
}

void traverse(BTree *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(BTree *x, int i) {
   int j, mid;
   BTree *np1, *np3, *y;
   np3 = init();//create new node
   np3->l = true;
   if (i == -1) {
      mid = x->d[2];//find 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 B 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 B tree
10 20
30
40 50 60 70