// 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;
}