Bツリーを使用してソートを実行するC++プログラム

ここでは、Bツリーを使用してソートされたシーケンスを取得する方法を説明します。 Bツリーはn-aryツリーです。ソートされたシーケンスを取得するには、Bツリーを作成し、それに番号を追加します。ここで、Bツリーは最大5つのノードを保持できます。ノードの数が増えた場合は、ノードを分割して新しいレベルを形成します。ノードは（多くても）5のような少数の要素を保持しているため、バブルソート手法を使用してノードをソートしています。要素の数が非常に少ないため、パフォーマンスにあまり影響を与えません。

ツリーをトラバースした後、さまざまなノードのすべての値を取得します。これらの要素は、降順ではない順序で並べ替えられます。

アルゴリズム

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{ //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