#include <iostream>
#include<cctype>
#include <stdlib.h>
#include <conio.h>

using namespace std;

struct node
{
    int key; // @AVR
    int desc; //@AVR
    int element;
    node *left;
    node *right;
    int height;
};
typedef struct node *nodeptr;
class bstree
{
    public:
        void insert(int,nodeptr &);
        void del(int, nodeptr &);
        int deletemin(nodeptr &);
        int countmax(int, nodeptr &);  //@ AVR
        void find(int,nodeptr &);
        nodeptr findmin(nodeptr);
        //nodeptr findmax(nodeptr);
        void makeempty(nodeptr &);
        void copy(nodeptr &,nodeptr &);
        nodeptr nodecopy(nodeptr &);
        //void preorder(nodeptr);
        void inorder(nodeptr);
    //void postorder(nodeptr);
        int bsheight(nodeptr);
        nodeptr srl(nodeptr &);
        nodeptr drl(nodeptr &);
        nodeptr srr(nodeptr &);
        nodeptr drr(nodeptr &);
        int max(int,int);
        int nonodes(nodeptr);
};
// Inserting a node
void bstree::insert(int x,nodeptr &p)
{
    if (p == NULL)
    {
        p = new node;
        p->element = x;
        p->left=NULL;
        p->right = NULL;
        p->height=0;
        if (p==NULL)
        {
            cout<<"S-a terminat spatiul\n"<<endl;
        }
    }
    else
    {
        if (x<p->element)
        {
            insert(x,p->left);
            if ((bsheight(p->left) - bsheight(p->right))==2)
            {
                if (x < p->left->element)
                {
                    p=srl(p);
                }
                else
                {
                    p = drl(p);
                }
            }
        }
        else if (x>p->element)
        {
            insert(x,p->right);
            if ((bsheight(p->right) - bsheight(p->left))==2)
            {
                if (x > p->right->element)
                {
                    p=srr(p);
                }
                else
                {
                    p = drr(p);
                }
            }
        }
        else
        {
            cout<<"Elementul exista\n"<<endl;
        }
}
int m,n,d;
m=bsheight(p->left);
n=bsheight(p->right);
d=max(m,n);
p->height = d + 1;
}
// Finding the Smallest
nodeptr bstree::findmin(nodeptr p)
{
    if (p==NULL)
    {
        cout<<"Arborele este gol\n"<<endl;
        return p;
    }
    else
    {
        while(p->left !=NULL)
        {
            p=p->left;
            //return p;
        }
        return p;
    }
}

/*
// Finding the Largest node
nodeptr bstree::findmax(nodeptr p)
{
    if (p==NULL)
    {
        cout<<"Arborele este gol\n"<<endl;
        return p;
    }
    else
    {
        while(p->right !=NULL)
        {
            p=p->right;
            //return p;
        }
        return p;
    }
}


// Finding an element
void bstree::find(int x,nodeptr &p)
{
    if (p==NULL)
    {
        cout<<"Elementul nu a fost gasit!\n"<<endl;
    }
    else
    {
        if (x < p->element)
        {
            find(x,p->left);
        }
        else
        {
            if (x>p->element)
            {
                find(x,p->right);
            }
            else
            {
                cout<<"Elementul nu a fost gasit!\n"<<endl;
            }
        }
    }
}
// Copy a tree
void bstree::copy(nodeptr &p,nodeptr &p1)
{
    makeempty(p1);
    p1 = nodecopy(p);
}
// Make a tree empty
void bstree::makeempty(nodeptr &p)
{
    nodeptr d;
    if (p != NULL)
    {
        makeempty(p->left);
        makeempty(p->right);
        d=p;
        free(d);
        p=NULL;
    }
}
// Copy the nodes
nodeptr bstree::nodecopy(nodeptr &p)
{
    nodeptr temp;
    if (p==NULL)
    {
        return p;
    }
    else
    {
        temp = new node;
        temp->element = p->element;
        temp->left = nodecopy(p->left);
        temp->right = nodecopy(p->right);
        return temp;
    }
}







/*


// Returns count of
//int CountGreater(struct Node* root, int x)
 bstree::countmax(int x,nodeptr &p)                              //x=x ; Node* = nodeptr, root = &p
{
    int res = 0;

        nodeptr d;
    // Search for x. While searching, keep
    // updating res if x is greater than
    // current node.
    while (p != NULL) {

        int desc = (p->right != NULL) ?
                   p->right->desc : -1;

        if (p->key > x) {
            res = res + desc + 1 + 1;
            p = p->left;
        } else if (p->key < x)
            p = p->right;
        else {
            res = res + desc + 1;
            break;
        }
    }
    return res;
}







*/





// Deleting a node
void bstree::del(int x,nodeptr &p)
{
    nodeptr d;
    if (p==NULL)
    {
        cout<<"Elementul nu a fost gasit!\n"<<endl;
    }
    else if ( x < p->element)
    {
        del(x,p->left);
    }
    else if (x > p->element)
    {
        del(x,p->right);
    }
    else if ((p->left == NULL) && (p->right == NULL))
    {
        d=p;
        free(d);
        p=NULL;
        cout<<"Elementul a fost sters\n"<<endl;
    }
    else if (p->left == NULL)
    {
        d=p;
        free(d);
        p=p->right;
        cout<<"Elementul a fost sters\n"<<endl;
    }
    else if (p->right == NULL)
    {
        d=p;
        p=p->left;
        free(d);
        cout<<"Elementul a fost sters\n"<<endl;
    }
    else
    {
        p->element = deletemin(p->right);
    }
}

int bstree::deletemin(nodeptr &p)
{
    int c;
    cout<<"interior stergemin\n"<<endl;
    if (p->left == NULL)
    {
        c=p->element;
        p=p->right;
        return c;
    }
    else
    {
        c=deletemin(p->left);
        return c;
    }
}

/*

void bstree::preorder(nodeptr p)
{
    if (p!=NULL)
    {
        cout<<p->element<<"\t";
        preorder(p->left);
        preorder(p->right);
    }
}

*/



// Inorder Printing
void bstree::inorder(nodeptr p)
{
    if (p!=NULL)
    {
        inorder(p->left);
        cout<<p->element<<"\t";
        inorder(p->right);
    }
}




/*
// PostOrder Printing
void bstree::postorder(nodeptr p)
{
    if (p!=NULL)
    {
        postorder(p->left);
        postorder(p->right);
        cout<<p->element<<"\t";
    }
}

*/

int bstree::max(int value1, int value2)
{
    return ((value1 > value2) ? value1 : value2);
}
int bstree::bsheight(nodeptr p)
{
    int t;
    if (p == NULL)
    {
        return -1;
    }
    else
    {
        t = p->height;
        return t;
    }
}


nodeptr bstree:: srl(nodeptr &p1)
{
    nodeptr p2;
    p2 = p1->left;
    p1->left = p2->right;
    p2->right = p1;
    p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
    p2->height = max(bsheight(p2->left),p1->height) + 1;
    return p2;
}
nodeptr bstree:: srr(nodeptr &p1)
{
    nodeptr p2;
    p2 = p1->right;
    p1->right = p2->left;
    p2->left = p1;
    p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
    p2->height = max(p1->height,bsheight(p2->right)) + 1;
    return p2;
}
nodeptr bstree:: drl(nodeptr &p1)
{
    p1->left=srr(p1->left);
    return srl(p1);
}
nodeptr bstree::drr(nodeptr &p1)
{
    p1->right = srl(p1->right);
    return srr(p1);
}

int bstree::nonodes(nodeptr p)
{
    int count=0;
    if (p!=NULL)
    {
        nonodes(p->left);
        nonodes(p->right);
        count++;
    }
    return count;
}

int main()
{
    //clrscr();
    nodeptr root,nr,root1,min,max;//,flag;
    int a,choice,findele,delele;
    char ch='y';
    bstree bst;

    //system("clear");
    root = NULL;
    root1=NULL;
    cout<<"\n\t\t\t\t     ARBORE AVL"<<endl;
    cout<<"\t\t\t\t:::::::::::::::::::\n"<<endl;

    do
    {
        cout<<"\t\t::::::::::::::::::::::::::::::::::::::::::::::::"<<endl;
        cout<<"\t\t::::Apasa 1 pentru a insera nod:::::::::::::::::"<<endl;
        cout<<"\t\t::::Apasa 2 pentru valoare min::::::::::::::::::"<<endl;
        //cout<<"\t\t::::Apasa 3 pentru valoare max::::::::::::::::::"<<endl;
        //cout<<"\t\t::::Apasa 4 pentru a cauta::::::::::::::::::::::"<<endl;
        cout<<"\t\t::::Apasa 5 pentru a sterge:::::::::::::::::::::"<<endl;
        //cout<<"\t\t::::Apasa 6 pentru afisare Preorder:::::::::::::"<<endl;
        cout<<"\t\t::::Apasa 7 pentru afisare ordonata:::::::::::::"<<endl;
        //cout<<"\t\t::::Apasa 8 pentru afisare Postorder::::::::::::"<<endl;
        //cout<<"\t\t::::Apasa 9 pentru inaltimea arborelui::::::::::"<<endl;
        //cout<<"\t\t::::Apasa 10 pentru nr nod mai mari:::::::::::::"<<endl;
        cout<<"\t\t::::Apasa 0 pentru a iesi:::::::::::::::::::::::"<<endl;
        cout<<"\t\t::::::::::::::::::::::::::::::::::::::::::::::::\n"<<endl;

        cout<<"\nIntrodu alegerea: ";
        cin>>choice;

        switch(choice)
        {
            case 1:
                cout<<"\n\t\tINSERARE NOD"<<endl;
                cout<<"\t\t:::::::::::::\n"<<endl;
                cout<<"Introdu nod nou: ";
                cin>>a;
                bst.insert(a,root);
                cout<<"\nNodul a fost introdus cu succes!\n"<<endl;
                break;
            case 2:
                if (root !=NULL)
                {
                    min=bst.findmin(root);
                    cout<<"\nNodul minim este: "<<min->element<<endl;
                }
                break;

                /*
            case 3:
                if (root !=NULL)
                {
                    max=bst.findmax(root);
                    cout<<"\nNodul maxim este: "<<max->element<<endl;
                }
                break;
        */

        /*
            case 4:
                cout<<"\nIntrodu nodul cautat: ";
                cin>>findele;
                if (root != NULL)
                {
                    bst.find(findele,root);
                }
                break;
                */

            case 5:
                cout<<"\nIntrodu nodul pentru stergere: ";
                cin>>delele;
                bst.del(delele,root);
                bst.inorder(root);
                cout<<endl;
                break;
    /*

            case 6:
                cout<<"\n\t\tPRE-ORDER TRAVERSAL"<<endl;
                bst.preorder(root);
                cout<<endl;
        */      break;
            case 7:
                cout<<"\n\t\tAFISARE IN ORDINE"<<endl;
                bst.inorder(root);
                cout<<endl;
                break;

            /*
            case 8:
                cout<<"\n\t\tPOST ORDER TRAVERSAL"<<endl;
                bst.postorder(root);
                cout<<endl;
                break;
            case 9:
                cout<<"\n\t\tINALTIMEA\n"<<endl;
                cout<<"Inaltimea arborelui este: "<<bst.bsheight(root)<<endl;

                break;

                */

        /*
            case 10:
                if (root !=NULL) {
                cout<<"\n\t\tNODURI MAI MARI\n"<<endl;
                 nr=bst.countmax(root);
                cout<<"Nr de noduri mai mari este: "<<max->element<<endl; // @ AVR
                }
                break;
            case 0:
                cout<<"\n\tO zi buna!\n"<<endl;
                break;
            default:
                cout<<"Input gresit!\n"<<endl;
                break;

            */
        }
        system("pause");
        system("cls");
    }while(choice != 0);
    return 0;
}