#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;
 
struct Item
{
    string key;
    int height;
    Item* left;
    Item* right;
    Item ();
};
 
Item::Item () : key (""), height (1), left (nullptr), right (nullptr) {}
 
Item* root = nullptr;
 
Item * search (Item * p, string name)
{
    while (p != nullptr && p->key != name)
    {
        if (name < p->key)
            p = p->left;
        else
            p = p->right;
    }
    return p;
}
 
inline int findHeight (Item* p) {
    if (p == nullptr) return 0;
    else return p->height;
}
 
void correctLL (Item*& p) {
    Item* a = p;
    Item* b = p->left;
    Item* c = p->left->left;
    p = b;
    a->left = b->right;
    b->right = a;
    // opravit vysku 
}
 
void correctLR (Item *& p)
{
    Item* a = p;
    Item* b = p->left;
    Item* c = p->left->right;
    Item* x = c->left;
    Item* y = c->right;
    p = c;
    c->left = b;
    c->right = a;
    b->right = x;
    a->left = y;
    // opravit vysku 
}
 
void correctRR (Item*& p) {
    Item* a = p;
    Item* b = p->right;
    Item* c = p->right->right;
    p = b;
    a->right = b->left;
    b->left = a;
    // opravit vysku 
}
 
void correctRL (Item *& p)
{
    Item* a = p;
    Item* b = p->right;
    Item* c = p->right->left;
    Item* x = c->right;
    Item* y = c->left;
    p = c;
    c->right = b;
    c->left = a;
    b->left = x;
    a->right = y;
    // opravit vysku 
}
 
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 (p->key < name) */
        enter (p->right, name);
 
    int a = findHeight (p->left);
    int b = findHeight (p->right);
 
    // cout << "enter " << p->key << ":" << a << "," << b << endl;
    if (a > b + 1) {
        if (findHeight (p->left->left) > findHeight (p->left->right))
            correctLL (p);
        else
            correctLR (p);
    } 
    else if (b > a + 1) {
        if (findHeight (p->right->right) > findHeight (p->right->left))
            correctRR (p);
        else
            correctRL (p);
    }
 
    a = findHeight (p->left);
    b = findHeight (p->right);
    if (a > b)
        p->height = a + 1;
    else
        p->height = b + 1;
}
 
 
 
void print (Item* p)
{
    if (p != nullptr)
    {
        print (p->left);
        cout << p->key << endl;
        print (p->right);
 
    }
}
 
void display (Item* p, int level = 1)
{
    if (p != nullptr)
    {
        display (p->left, level + 1);
        for (int i = 1; i < level; i++)
            cout << "    ";
        cout << p->key << endl;
        display (p->right, level + 1);
 
    }
}
 
int main ()
{
    enter (root, "5");
    enter (root, "3");
    enter (root, "4");
    cout << "---" << endl;
    display (root);
 
    /*
    enter (root, "3");
    cout << "---" << endl;
    display (root);
 
    enter (root, "2");
    cout << "---" << endl;
    display (root);
    */
 
    cout << "Konec programu" << endl;
    system ("pause");
    return 0;
}