===== B-tree =====

<code C++>
#include <iostream>
// #include <cassert>
#include <time.h>
using namespace std;

const int Max = 4; // max. pocet klicu v jednom uzlu
const int Min = Max / 2;

struct Item
{
    int cnt; // 1 <= cnt <= Max, cnt == Max+1 pri preplneni
    int key [Max+1]; // o jeden klic navic pri preplneni
    Item * ref [Max+2];
    // vyuzivame key [0] , ... , key [cnt-1]
    // vyuzivame ref [0] , ... , ref [cnt-1], ref [cnt]
    Item ();
};

Item::Item ()
{
    cnt = 0;
    for (int k = 0; k < Max+1; k++) key [k] = -1;
    for (int k = 0; k < Max+2; k++) ref [k] = nullptr;
}

void split (Item * p, int & center, Item * & r)
{
    int n = p->cnt;

    int a = Min; // pocet klicu v levem bloku, key[0] ...key[a-1]
    center = p->key [a];
    int b = n - a - 1; // pocet klicu v pravem bloku

    r = new Item;

    // ponechame v levem bloku, key[0] ...key[a-1]
    // nahoru key [a]
    // do praveho bloku, key[a+1] ... key[n-1]
    for (int k = a+1; k <= n-1; k++) r->key [k-a-1] = p->key [k];

    // ponechame v levem bloku, ref[0] ... ref[a]
    // do praveho bloku, ref[a+1] ... ref[n]
    for (int k = a+1; k <= n; k++) r->ref [k-a-1] = p->ref [k];

    // pro poradek
    for (int k = a; k <= n-1; k++) p->key [k] = -1;
    for (int k = a+1; k <= n; k++) p->ref [k] = nullptr;

    p->cnt = a;
    r->cnt = b;
}

void shift (Item* p, int i, int new_key, Item* new_ref)
{
    for (int k = p->cnt-1; k >= i; k--) p->key [k+1] = p->key [k];
    for (int k = p->cnt; k >= i+1; k--) p->ref [k+1] = p->ref [k];
    p->key [i] = new_key;
    p->ref [i+1] = new_ref;
    p->cnt++;
}

void insertValue (Item * p, int value)
{
    int i = 0;
    while (i < p->cnt && p->key [i] < value) i++;
    if (i < p->cnt && p->key [i] == value) { /* duplicita */ }
    else
    {
        if (p->ref [0] == nullptr)
        {
            shift (p, i, value, nullptr);
        }
        else
        {
            Item * t = p->ref [i];
            insertValue (t, value);

            if (t->cnt > Max)
            {
                int center;
                Item* r;
                split (t, center, r);
                shift (p, i, center, r);
            }
        }
    }
}

void enter (Item * & p, int value)
{
    if (p == nullptr)
    {
        p = new Item;
        p->cnt = 0;
    }
    insertValue (p, value);
    if (p->cnt > Max)
    {
        int center;
        Item * r;
        split (p, center, r);

        Item * t = new Item;
        t->cnt = 1;
        t->ref [0] = p;
        t->key [0] = center;
        t->ref [1] = r;
        p = t; // novy koren
    }
}

void print (Item* p, int level = 1)
{
    if (p != nullptr)
    {
        for (int i = 2; i <= level; i++)
            cout << "        ";

        for (int i = 0; i < p->cnt; i++)
        {
            cout << p->key [i];
            if (i < p->cnt-1) cout << ",";
        }
        cout << endl;

        for (int i = 0; i <= p->cnt; i++)
            print (p->ref [i], level + 1);
    }
}

void printValue (Item * p)
{
    if (p != nullptr)
    {
        for (int i = 0; i < p->cnt; i++)
        {
            printValue (p->ref [i]);
            cout << p->key [i] << " ";
        }
        printValue (p->ref [p->cnt]);
    }
}

int main ()
{
    Item * root = nullptr;

    enter (root, 30);
    enter (root, 20);
    enter (root, 10);
    enter (root, 40);
    enter (root, 50);

    for (int i = 21; i <= 30; i++)
        enter (root, i);

    enter (root, 51);
    enter (root, 52);
    enter (root, 53);

    /*
    for (int i = 1 ; i <= 1024; i++)
        enter (root, i);
    */

    /*
    srand (time (nullptr));
    for (int i = 1; i <= 1000000; i++)
        enter (root, (rand () % 1000) + 1000 * (rand () % 1000));
    */

    print (root);
    printValue (root);

    cout << "O.K." << endl;
}
</code>