http://kmlinux.fjfi.cvut.cz/~culik/zalg/Tree05.zip

#include "stdafx.h"
 
#include "form.h"
#include "tree.h"
 
#include <string>
using namespace std;
 
struct Item
{
    int key;
    int height;
    Item * left;
    Item * right;
    Item () : key (0), height(1), left (nullptr), right (nullptr) { }
};
 
inline int h (Item * p)
{
    if (p == nullptr)
        return 0;
    else
        return p->height;
}
 
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 enter(Item * & root, int val)
{
    if (root == nullptr)
    {
        root = new Item;
        root->key = val;
    }
    else if (val < root->key) enter (root->left, val);
    else if (val > root->key) enter (root->right, val);
    else { }
 
    update (root);
    int L = h(root->left);
    int R = h(root->right);
    Item * a = root;
    if (L > R + 1)
    {
        Item * b = a->left;
        int LL = h(b->left);
        int RR = h(b->right);
        if (LL > RR)
        {
            Item * c = b->left; // prvek (3. dole)
            //     a
            //   b
            // c
            Item * t = b->right; // podstrom
            root = b; // novy koren
            //     b
            //  c     a
            b->right = a;
            a->left = t;
            update (a);
            update (b); // posledni
        }
        else
        {
            Item * c = b->right; // prvek (3. dole)
            //         a
            //   b
            //      c
            Item * t = c->left; // podstrom
            Item * u = c->right; // podstrom
            root = c; // novy koren
            //     c
            //  b     a
            c->left = b;
            c->right = a;
            b->right = t;
            a->left = u;
            update(a);
            update(b);
            update(c); // posledni
        }
    }
    else if (R > L + 1)
    {
        Item * b = a->right;
        int LL = h(b->right);
        int RR = h(b->left);
        if (LL > RR)
        {
            Item * c = b->right; // prvek (3. dole)
            //  a
            //     b
            //        c
            Item * t = b->left; // podstrom
            root = b; // novy koren
            //     b
            //  a     c
            b->left = a;
            a->right = t;
            update(a);
            update(b); // posledni
        }
        else
        {
            Item * c = b->left; // prvek (3. dole)
            //  a
            //        b
            //     c      
            Item * t = c->right; // podstrom
            Item * u = c->left; // podstrom
            root = c; // novy koren
            //     c
            //  a     b
            c->right = b;
            c->left = a;
            b->left = t;
            a->right = u;
            update(a);
            update(b);
            update(c); // posledni
        }
    }
}
 
void display (Item * root)
{
    if (root != nullptr) 
    {
        string s = to_string(root->key) + " (" + to_string(h(root)) + ")";
        openBranch (s);
        display (root->left);
        if (root->left != nullptr || root->right != nullptr) addNode(".");
        display(root->right);
        closeBranch();
    }
}
 
void run()
{
    Item * root = nullptr;
 
    for (int k = 1; k <= 16*1024; k++)
       enter(root, k);
 
    display(root);
 
    print("Hello " + to_string (h(root)));
    status("O.K.");
}