#include <iostream>

using namespace std;

struct AVLnode {
    int val;
    AVLnode* l;
    AVLnode* r;
    int h;
};

int max(int a, int b) {
    return (a > b) ? a : b;
}
int height(AVLnode* node) {
    if (!node) return 0;
    else return node->h;
}
int getBalance(AVLnode* node) {
    if (!node) return 0;
    else return height(node->l) - height(node->r);
}
AVLnode* minVal(AVLnode* node) {
    AVLnode* min = node;
    while (node->l) {
        min = min->l;
    }
    return min;
}

class AVL {
private:
    AVLnode* root;
    void InsertNode(AVLnode* &node, int val);
    void PrintInOrder(AVLnode* node);
    AVLnode* RotL(AVLnode* &piv);
    AVLnode* RotR(AVLnode* &piv);
    void DeleteNode(AVLnode* &node, int val);
public:
    AVL();
    void Insert(int val);
    void Print();
    void Delete(int val);
};

AVL::AVL() {
    root = NULL;
}

void AVL::InsertNode(AVLnode* &node, int val) {
    if (!node) {
        AVLnode* newNode = new AVLnode;
        newNode->val = val;
        newNode->l = newNode->r = NULL;
        newNode->h = 1;
        node = newNode;
    }
    else {
        if (val < node->val) {
            InsertNode(node->l, val);
        }
        else {
            InsertNode(node->r, val);
        }
        node->h = 1 + max(height(node->l), height(node->r));
        int balance = getBalance(node);

        //Left Left Case
        if (balance > 1 && val < node->l->val) {
            node = RotR(node);
        }
        //Left Right Case
        else if (balance > 1 && val > node->l->val) {
            node->l = RotL(node->l);
            node = RotR(node);
        }
        //Right Right Case
        else if (balance < -1 && val > node->r->val) {
            node = RotL(node);
        }
        //Right Left Case
        else if (balance < -1 && val < node->r->val) {
            node->r = RotR(node->r);
            node = RotL(node);
        }

    }
}
void AVL::Insert(int val) {
    InsertNode(root, val);
}

void AVL::PrintInOrder(AVLnode* node) {
    if (node) {
        PrintInOrder(node->l);
        cout << node->val << " ";
        PrintInOrder(node->r);
    }
}
void AVL::Print() {
    PrintInOrder(root);
}

void AVL::DeleteNode(AVLnode* &node, int val) {
    if (node) {
        if (val > node->val) DeleteNode(node->r, val);
        else if (val < node->val) DeleteNode(node->l, val);
        else {
            if (!node->l) {
                AVLnode* t = node->r;
                delete node;
                node = t;
            }
            else if (!node->r) {
                AVLnode* t = node->l;
                delete node;
                node = t;
            }
            //ma dwoje dzieci
            else {
                AVLnode* t = minVal(node->r);
                node->val = t->val;
                DeleteNode(node->r, t->val);
            }
        }
    }
    if (node) {
        node->h = 1 + max(height(node->l), height(node->r));
        int balance = getBalance(node);
        //Left Left Case
        if (balance > 1 && getBalance(node->l) >= 0) {
            node = RotR(node);
        }
        //Left Right Case
        if (balance > 1 && getBalance(node->l) < 0) {
            node->l = RotL(node->l);
            node = RotR(node);
        }
        //Right Left Case
        if (balance < -1 && getBalance(node->r) > 0) {
            node->r = RotR(node->r);
            node = RotL(node);
        }
        //Right Right Case
        if (balance < -1 && getBalance(node->r) <= 0) {
            node = RotL(node);
        }
    }
}
void AVL::Delete(int val) {
    DeleteNode(root, val);
}

AVLnode* AVL::RotL(AVLnode* &node) {
    //AVLnode* t = node->r;
    //AVLnode* t2 = t->l;
    //t->l = node;
    //node->r = t2;
    AVLnode* t = node->r;
    node->r = t->l;
    t->l = node;
    node->h = 1 + max(height(node->l), height(node->r));
    t->h = 1 + max(height(t->l), height(t->r));
    return t;
}
AVLnode* AVL::RotR(AVLnode* &node) {
    //AVLnode* t = node->l;
    //AVLnode* t2 = t->r;
    //t->r = node;
    //node->l = t2;
    AVLnode* t = node->l;
    node->l = t->r;
    t->r = node;
    node->h = 1 + max(height(node->l), height(node->r));
    t->h = 1 + max(height(t->l), height(t->r));
    return t;
}



int main() {
    AVL tree;

    //tree.Insert(13);
    //tree.Insert(10);
    //tree.Insert(15);
    //tree.Insert(5);
    //tree.Insert(11);
    //tree.Insert(16);
    //tree.Insert(4);
    //tree.Insert(6);
    //tree.Insert(7);

    tree.Insert(2);
    tree.Insert(1);
    tree.Insert(3);

    tree.Delete(2);


    system("PAUSE");
    return 0;
}