Vyvážené stromy

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