// tree.cpp : Defines the entry point for the console application.
 
#include "stdafx.h"
#include <iostream>
#include <string>
 
using namespace std;
 
struct item {
    int key;
    int v; /* 1, ... */ 
    item * left;
    item * right;
};
 
item* root=0;
 
item* search(int k){
    item* p=root;
    while (p!=NULL)
    {
       if (k < p->key)
           p = p->left;
       else if(k > p->key)
           p = p->right;
       else return p;
    }
    return p;
}
 
inline int vyska (item * p)
{
    if (p == NULL)
        return 0;
    else
        return p->v;
}
 
inline void uprav (item * p)
{
    int n = vyska (p->left);
    int m = vyska (p->right);
    if (n > m)
        p->v = n + 1;
    else
        p->v = m + 1;
}
 
void insert (item * & p, int k){
    if (p==NULL)
    {
       item * u = new item;
       u->key = k;
       u->v = 1;
       u->left = NULL;
       u->right = NULL;
       p = u;
    }
    else if (k < p->key)
       insert (p->left, k);
    else if (k > p->key)
       insert (p->right, k);
 
    uprav (p);
 
    int n = vyska (p->left);
    int m = vyska (p->right);
 
    if (n > m + 1)
    {
        item * t = p->left;
        int a = vyska (t->left);
        int b = vyska (t->right);
        if (a > b)
        {
            cout << "Varianta 1 " << p->key << endl;
            item* u = p;
            u->left = t->right;
            t->right = u;
            p = t;
            uprav(u);
            uprav(t);
        }
        else
        {
            cout << "Varianta 2 " << p->key << endl;
			item *u = p;
			item *v = t->right;
			u->left = v->right;
			t->right= v->left;
			p = v;
			v->left = t;
			v->right = u;
			uprav(u);
			uprav(t);
			uprav(v);
        }
    }
	else if (m > n + 1)
	{
        item * t = p->right;
        int a = vyska (t->right);
        int b = vyska (t->left);
        if (a > b)
        {
            cout << "Varianta 3 " << p->key << endl;
            item* u = p;
            u->right = t->left;
            t->left = u;
            p = t;
            uprav(u);
            uprav(t);
        }
        else
        {
            cout << "Varianta 4 " << p->key << endl;
			item *u = p;
			item *v = t->left;
			u->right = v->left;
			t->left= v->right;
			p = v;
			v->right = t;
			v->left = u;
			uprav(u);
			uprav(t);
			uprav(v);
        }
 
	}
 
    n = vyska (p->left);
    m = vyska (p->right);
    if (abs (n-m) > 1) cout << "Problem " << p->key << endl;
 
}
 
void print (item * p)
{
    if (p != nullptr)
    {
        cout << p->key<< ":" << p->v << "  ";
        print (p->left);
        print (p->right);
    }
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    insert (root, 10);
    insert (root, 15);
    insert (root, 12);
    //insert (root, 2);
    //insert (root, 1);
    print (root);
    cout << endl;
    system ("pause");
 
    return 0;
}