/*

*/
#include <stdio.h>

struct nodoAVL{
    nodoAVL *izq, der;
    int altura;
    int dato;
}

typedef nodoAVL* AVL;

void rotarIzquierda(AVL &z){
    AVL y = z->der;
    AVL T2 = y->izq;
    
    y->izq=z;
    z->der=T2;
    
    z->altura=maximo(alturaAVL(z->izq),alturaAVL(z->der)) + 1;
    y->altura=maximo(alturaAVL(y->izq),alturaAVL(y->der)) + 1;
    
    z=y;
}

void rotarDerecha(AVL &z){
    AVL y = z->izq;
    AVL T3 = y->der;
    
    y->der=z;
    z->izq=T3;
    
    z->altura=maximo(alturaAVL(z->izq),alturaAVL(z->der)) + 1;
    y->altura=maximo(alturaAVL(y->izq),alturaAVL(y->der)) + 1;
    
    z=y;
}

int alturaAVL(AVL A){
    if (A==NULL){
        return 0;
    }else{
        return A->altura;
    }
}

void insertarAVL(int x, AVL &A){
    if (A==NULL){
        AVL nuevo = new nodoAVL;
        nuevo->dato=x;
        nuevo->altura=1;
        nuevo->izq=NULL;
        nuevo->der=NULL;
        A=nuevo;
    }else{
        if (x < A->dato){
            insertarAVL(x, A->izq);
            A->altura=maximo(alturaAVL(A->izq),alturaAVL(A->der)) + 1;
            int dif = alturaAVL(A->izq) - alturaAVL(A->der);
            if (dif>1) //quedo desbalanceado 
            {
               if (alturaAVL(A->izq->izq) > alturaAVL(A->izq->der){ //inserte en la izquierda
                   rotarDerecha(A);
               }else{// inserte a la derecha
                   rotarIzquierda(A->izq); //seria y 
                   rotarDerecha(A); // seria z
               }
            }  
        }else{
            insertarAVL(x, A->der);
            A->altura=maximo(alturaAVL(A->izq),alturaAVL(A->der)) + 1;
            int dif = alturaAVL(A->izq) - alturaAVL(A->der);
            if (dif<-1){ //quedo desbalanceado 
                if (alturaAVL(A->der->der) > alturaAVL(A->der->izq){ //inserte en el derecho
                   rotarIzquierda(A);
               }else{// inserte a la derecha
                   rotarDerecha(A->der); //seria y 
                   rotarIzquierda(A); // seria z
               }
            }
        }
            
        }
    }
}

void borrarAVL(int x, AVL &A){
    if (A!=NULL){
        if (x>A->dato){
            borrarAVL(x, A->der);
            reajustarDer(A);
        }else if (x<A->dato){
            borrarAVL(x, A->izq);
            reajustarIzq(A);
        }else{ //caso en el que es igual
            if (A->izq ==NULL && A->der ==NULL){
                delete A;
                A=NULL;
            }else if (A->izq ==NULL){
                AVL aborrar = A;
                A=A->der;
                delete aborrar;
            }else if (A->der ==NULL){
                AVL aborrar = A;
                A=A->izq;
                delete aborrar;
            }else{ //ambos distintos de NULL
                A->dato = maxAVL(A->izq); // sobreescribo el dato con el maximo de la izquierda
                borrarAVL(A->dato, A->izq); // borro el maximo de la izquierda
                reajustarIzq(A);
            }
        }
    }
}

void reajustarDer( AVL &A){
    if (alturaAVL(A->izq) == alturaAVL(A->der) + 2){ // como es AVL, la dif era maximo 1, si pasa a ser 2 hay que rotar
        if (alturaAVL(A->izq->der) >alturaAVL(A->izq->izq)){ // hago una rotacion doble
            rotacionIzquierda(A->izq);
        }
        rotacionDerecha(A); //hago una rotacion simple o la segunda de la doble 
    }else{
        A->altura=maximo(alturaAVL(A->izq),alturaAVL(A->der)) + 1; // no se desbalanceo pero hay que actualizar la altura
    }
}

void reajustarIzq( AVL &A){
    if (alturaAVL(A->der) == alturaAVL(A->izq) + 2){ // como es AVL, la dif era maximo 1, si pasa a ser 2 hay que rotar
        if (alturaAVL(A->der->izq) >alturaAVL(A->der->der)){ // hago una rotacion doble
            rotacionDerecha(A->der);
        }
        rotacionIzquierda(A); //hago una rotacion simple o la segunda de la doble 
    }else{
        A->altura=maximo(alturaAVL(A->izq),alturaAVL(A->der)) + 1; // no se desbalanceo pero hay que actualizar la altura
    }
}


int main()
{
    printf("Hello World");

    return 0;
}