Vyvážené stromy

#include <iostream>
using namespace std;
 
struct Item
{
    int key;
    int height;
    Item* left;
    Item* right;
 
    Item () { key = 0; height = 1; left = nullptr; right = nullptr; }
};
 
Item* root = 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;
        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))
        {
            // Left Left Case
            // Item* c = b->left;
 
            // Item* A = a->right;
            Item* B = b->right;
            // Item* C = c->right;
            // Item* D = c->left;
 
            //               a
            //                  A
            //         b
            //            B
            //   c     
            // D   C
 
            p = b; // ukotveni
            // b->left = c;
            b->right = a;
            a->left = B; // <-- tady byla chyba
 
            //         b
            //   c            a 
            // D   C        B   A
            update (a);
        }
    }
 
    update (p);
    // cout << "UPDATE " << p->key << " (" << p->height << ")" << endl;
}
 
void print (Item* p)
{
    if (p != nullptr)
    {
        print (p->left);
        cout << p->key << " (" << p->height << ")" << endl;
        print (p->right);
    }
}
 
int main ()
{
    insert (root, 10);
    insert (root, 5);
    insert (root, 3);
 
    cout << endl;
    print (root);
 
    cout << "O.K." << endl;
}