#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;
 
struct Item 
{
    string key;
    int height;
 
    Item*left;
    Item*right;
 
    Item ();
};
 
Item*root = nullptr;
 
Item::Item () :key (""), height (1), left (nullptr), right (nullptr) {}
 
Item*search (Item* p, string name)
{
    while (p != nullptr && p->key != name)
    {
        if (name < p->key)
            p = p->left;
        else /* if (p->key < name) */
            p = p->right;
    }
    /* p == nullptr || p->key == name */
    return p;
}
 
void print (Item*p)
{
    if (p != nullptr) {
        print (p->left);
        cout << p->key << endl;
        print (p->right);
    }
}
 
inline int v (Item * p)
{
    if (p == nullptr)
        return 0;
    else
        return p->height;
}
 
void update (Item* p)
{
    int vL = v (p->left);
    int vR = v (p->right);
    if (vL > vR)
        p->height = vL + 1;
    else
        p->height = vR + 1;
 
}
void correctLL (Item*& p)
{
    Item * a = p;
    Item * b = a->left;
 
    a->left = b->right; // podstrom
    b->right = a; 
 
    p = b; // zmenim ukotveni, b bude nahore
    update (a);
    // update (b); // na konci enter
}
 
void correctLR (Item*& p)
{
    Item * a = p;
    Item * b = a->left;
    Item * c = b->right;
 
    b->right = c->left;
    a->left = c->right;
 
    c->left = b;
    c->right = a;
 
    p = c; // zmenim ukotveni, t bude nahore
    update (a);
    update (b);
    // update (c);
}
 
void correctRR (Item*& p)
{
    Item * a = p;
    Item * b = a->right;
 
    a->right = b->left; // podstrom
    b->left = a;
 
    p = b; // zmenim ukotveni, b bude nahore
    update (a);
    // update (b); // na konci enter
}
 
void correctRL (Item*& p)
{
    Item * a = p;
    Item * b = a->right;
    Item * c = b->left;
 
    b->left = c->right;
    a->right = c->left;
 
    c->right = b;
    c->left = a;
 
    p = c; // zmenim ukotveni, t bude nahore
    update (a);
    update (b);
    // update (c);
}
 
void enter (Item*& p, string name)
{
    if (p == nullptr)
    {
        Item * n = new Item ();
        n->key = name;
        n->height = 1;
        n->left = nullptr;
        n->right = nullptr;
        p = n;
    }
    else if (p->key == name)
    {
    }
    else if (name < p->key)
        enter (p->left, name);
    else /* if (name > p->key) */
        enter (p->right, name);
 
    int vL = v (p->left);
    int vR = v (p->right);
    if (vL > vR + 1)
    {
        Item * t = p->left;
        int vA = v (t->left);
        int vB = v (t->right);
        if (vA > vB)
            correctLL (p);
        else 
            correctLR (p);
    }
    else (vR > vL + 1)
    {
        Item * t = p->right;
        int vA = v (t->right);
        int vB = v (t->left);
        if (vA > vB)
            correctRR (p);
        else
            correctRL (p);
    }
 
    update (p);
}
 
int main ()
{
    enter (root, "5");
    enter (root, "3");
    enter (root, "1");
    print (root);
    cout << "Konec programu" << endl;
    system ("pause");
    return 0;
}