====== Vyvážené stromy ======

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

struct Item
{
    int key;
    int height;
    Item * left;
    Item * right;
    Item () { key = 0; height = 1; left = nullptr; right = nullptr; }
    // Item () : key (0), height (1), left (nullptr), right (nullptr) { }
};

inline int h (Item * p)
{
    if (p == nullptr)
        return 0;
    else
        return p->height;
}

inline void update (Item * p)
{
    int L = h (p->left);
    int R = h (p->right);
    if (L > R)
        p->height = L + 1;
    else
        p->height = R + 1;
}

void insert (Item * & p, int value)
{
    if (p == nullptr)
    {
        Item* t = new Item;
        t->key = value;
        t->height = 1;
        p = t;
    }
    else if (p->key == value)
    {
    }
    else if (value < p->key)
    {
        insert (p->left, value);
    }
    else
    {
        insert (p->right, value);
    }

    int L = h (p->left);
    int R = h (p->right);
    if (L > R + 1)
    {
        Item * a = p;
        Item * b = a->left;
        if (h (b->left) > h (b->right))
        {
            Item * c = b->left;
            //        a
            //     b
            //  c
            Item* B = b->right;

            p = b; // koren podstromu
            b->right = a;
            a->left = B;

            //              b
            //     c                  a
            //   .   .              B   .
            update (a);
        }
        else
        {
            Item * c = b->right;
            Item * C = c->left;
            Item * D = c->right;

            p = c;
            c->left = b;
            c->right = a;

            b->right = C;
            a->left = D;

            update (b);
            update (a);
        }
    }
    else if (R > L + 1)
    {
        Item* a = p;
        Item* b = a->right;
        if (h (b->right) > h (b->left))
        {
            Item* c = b->right;
            Item* B = b->left;

            p = b; // koren podstromu
            b->left = a;
            a->right = B;

            update (a);
        }
        else
        {
            Item* c = b->left;
            Item* C = c->right;
            Item* D = c->left;

            p = c;
            c->right = b;
            c->left = a;

            b->left = C;
            a->right = D;

            update (b);
            update (a);
        }
    }

    update (p);
}

void print (Item* p, int level = 1)
{
    if (p != nullptr)
    {
        print (p->left, level+1);

        for (int i = 1; i <= level-1; i++) cout << "    ";
        cout << p->key << " (" << p->height << ")" << endl;

        print (p->right, level+1);
    }
}

Item * root = nullptr;

int main ()
{
    /*
    insert (root, 10);
    insert (root, 20);
    insert (root, 15);
    */

    /*
    for (int i = 1 ; i <= 31; i++)
        insert (root, i);
    */

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

    // print (root);

    cout << "vyska stromu " << h (root) << endl;
}
</code>