<code C++>
// btree.cpp 


#include "stdafx.h"
#include <iostream>
#include <string>

using namespace std;

const int k = 2;
const int n = 2 * k;

struct block {
    int p; /* 1, ..., n, (n+1) */
    int key [n+1]; /* key[0], ..., key [p-1] */
    block * ref [n+2]; /* ref [0], ..., ref [p] */
};

block * root = NULL;

void insert (block * & b, int x)
{
    if (b == NULL)
    {
        b = new block;
        b->p = 1;
        b->key[0] = x;
        b->ref[0] = NULL;
        b->ref[1] = NULL;
    }
    else 
    {
       int i = 0;
       while (i < b->p && x < b->key[i]) i ++;
       if (i < b->p && x == b->key[i]) return;
       
       block * t = b->ref[i];
       if (t == NULL)
       {
           for (int j = b->p-1; j >= i; j --) b->key[j+1] = b->key [j];
           for (int j = b->p; j >= i+1; j --) b->ref[j+1] = b->ref [j];
           b->key [i] = x;
           b->ref [i+1] = NULL;
       }
       else
       {
           insert (t, x);
           if (t->p > n)
           {
               // t->key[0] ... t->key[k-1] ponechat
               // t->ref[0] ... t->ref[k] ponechat
               int y = t->key[k]; // delici bod

               block * r = new block ();
               // t->key[k+1] ... t->key[n] presunout
               // t->ref[k+1] ... t->ref[n+1] ponechat
               for (int j = 0; j <k; j++) r->key[j] = t->key[k+j];
               for (int j = 0; j <= k; j++) r->ref[j] = t->ref[k+j];

               // uvolnit b->key[i] 
               for (int j = b->p-1; j >= i; j --) b->key[j+1] = b->key [j];
               for (int j = b->p; j >= i+1; j --) b->ref[j+1] = b->ref [j];
               b->key [i] = y;
               b->ref [i+1] = r;
           }
       }
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    insert (root, 10);
    insert (root, 15);
    insert (root, 12);
    // print (root);
    cout << endl;
    system ("pause");

    return 0;
}


</code>