#include "stdafx.h"
 
#include <iostream>
#include <string>
using namespace std;
 
struct item {
    int key;
    int h;
    item* left;
    item* right;
};
 
item* root = nullptr;
 
inline int v (item * p)
{ 
    if (p == nullptr)
        return 0;
    else
        return p->h;
}
 
inline void oprav (item * p)
{
    int L = v (p->left);
    int R = v (p->right);
    p->h = L+1;
    if (R+1 > p->h) p->h = R+1;
}
 
void enter (item* & p, int k)
{
    if (p == nullptr ){
        item* t = new item;
        t->key = k;
        t->h = 1;
        t->left= nullptr;
        t->right= nullptr;
        p = t;
    }
   else if ( p->key == k)
   { }
   else if (k < p->key) 
      enter (p->left, k); 
   else 
      enter (p->right, k); 
 
   oprav (p);
   int hleft=v(p->left);
   int hright=v(p->right);
   item*n=p;
   if(hleft>hright+1){
        item*s=p->left;
        int sleft=v(s->left);
        int sright=v(s->right);
        if(sleft>sright){
            p=s;
            n->left=s->right; // podstrom C
            s->right=n; 
            oprav (n);
            oprav (s);
        }
        else
        {
            item *e = s->right;
            p = e;
            s->right = e->left;
            n->left = e->right;
            e->left = s;
            e->right = n;
            oprav(s);
            oprav(n);
            oprav(e);
        }
   }
   else if (hleft+1<hright)
   {
        item*s=p->right;
        int sright=v(s->right);
        int sleft=v(s->left);
        if(sright>sleft){
            p=s;
            n->right=s->left; // podstrom C
            s->left=n; 
            oprav (n);
            oprav (s);
        }
        else
        {
            item *e = s->left;
            p = e;
            s->left = e->right;
            n->right= e->left;
            e->right= s;
            e->left = n;
            oprav(s);
            oprav(n);
            oprav(e);
        }
   }
 
}
 
item* hledat(item* p, int k){
 
    while (p != nullptr)
    {
        if(p -> key == k){
        return p;
        }
        if (k < p->key) {p = p->left;} else {p = p->right;}
    }
 
return p;
}
 
 
 
void tiskni (item* p){
    if (p != nullptr){
    tiskni (p->left);
    cout << p->key << "(h=" << p->h << ")" << endl;
    tiskni (p->right);
    }
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    enter (root, 10);
    enter (root, 15);
    enter (root, 11);
    tiskni (root);
 
    system ("pause");
    return 0;
}