#include<stdio.h>
#include<stdlib.h>

struct noArvoreAVL{
    int info;
    struct noArvoreAVL *esq;
    struct noArvoreAVL *dir;
    int altura;
};

int altura(struct noArvoreAVL *N){
    if (N == NULL)
        return 0;
    return N->altura;
}
 
int max(int a, int b){
    return (a > b)? a : b;
}
 
struct noArvoreAVL* inicializa(int info){
    struct noArvoreAVL* noArvoreAVL = (struct noArvoreAVL*) malloc(sizeof(struct noArvoreAVL));
    noArvoreAVL->info   = info;
    noArvoreAVL->esq   = NULL;
    noArvoreAVL->dir  = NULL;
    noArvoreAVL->altura = 1;
    return(noArvoreAVL);
}

struct noArvoreAVL *rotaSimplesDir(struct noArvoreAVL *y){
    struct noArvoreAVL *x = y->esq;
    struct noArvoreAVL *T2 = x->dir;

    x->dir = y;
    y->esq = T2;
 
    y->altura = max(altura(y->esq), altura(y->dir))+1;
    x->altura = max(altura(x->esq), altura(x->dir))+1;

    return x;
}
 
struct noArvoreAVL* rotaSimplesEsq(struct noArvoreAVL *x){
    struct noArvoreAVL *y = x->dir;
    struct noArvoreAVL *T2 = y->esq;
 
    y->esq = x;
    x->dir = T2;

    x->altura = max(altura(x->esq), altura(x->dir))+1;
    y->altura = max(altura(y->esq), altura(y->dir))+1;

    return y;
}
 
int getFatorBalanceamento(struct noArvoreAVL *N){
    if (N == NULL)
        return 0;
    return altura(N->esq) - altura(N->dir);
}
 
struct noArvoreAVL* insert(struct noArvoreAVL* noArvoreAVL, int info){
    if (noArvoreAVL == NULL)
        return(inicializa(info));
 
    if (info < noArvoreAVL->info)
        noArvoreAVL->esq  = insert(noArvoreAVL->esq, info);
    else
        noArvoreAVL->dir = insert(noArvoreAVL->dir, info);
 
    /* 2. atualiza altura */
    noArvoreAVL->altura = max(altura(noArvoreAVL->esq), altura(noArvoreAVL->dir)) + 1;
 
    /* 3. Verifica fator de balanceamento */
    int fb = getFatorBalanceamento(noArvoreAVL);

    // 4 casos se a arvore tenha se tornado desbalanceada
    // esq esq
    if (fb > 1 && info < noArvoreAVL->esq->info)
        return rotaSimplesDir(noArvoreAVL);
    // dir dir
    if (fb < -1 && info > noArvoreAVL->dir->info)
        return rotaSimplesEsq(noArvoreAVL);
    // esq dir
    if (fb > 1 && info > noArvoreAVL->esq->info){
        noArvoreAVL->esq =  rotaSimplesEsq(noArvoreAVL->esq);
        return rotaSimplesDir(noArvoreAVL);
    }
    // dir esq
    if (fb < -1 && info < noArvoreAVL->dir->info){
        noArvoreAVL->dir = rotaSimplesDir(noArvoreAVL->dir);
        return rotaSimplesEsq(noArvoreAVL);
    }
    return noArvoreAVL;
}

struct noArvoreAVL * minValuenoArvoreAVL(struct noArvoreAVL* noArvoreAVL){
    struct noArvoreAVL* atual = noArvoreAVL;
     while (atual->esq != NULL)
        atual = atual->esq;
    return atual;
}
 
struct noArvoreAVL* deletenoArvoreAVL(struct noArvoreAVL* root, int info){
    if (root == NULL)
        return root;

    // Passo 1: remove o no
    if ( info < root->info )
        root->esq = deletenoArvoreAVL(root->esq, info);
    else if( info > root->info )
        root->dir = deletenoArvoreAVL(root->dir, info);

    else{
        // noArvoreAVL com um ou nenhum filho
        if( (root->esq == NULL) || (root->dir == NULL) ){
            struct noArvoreAVL *temp = root->esq ? root->esq : root->dir;

            if(temp == NULL){ // sem filho
                temp = root;
                root = NULL;
            }
            else // um filho
             *root = *temp;
            free(temp);
        }
        else{
            // dois filhos: troca pelo menor da subarvore da direita
            struct noArvoreAVL* temp = minValuenoArvoreAVL(root->dir);
            root->info = temp->info;
            root->dir = deletenoArvoreAVL(root->dir, temp->info);
        }
    }

    if (root == NULL)
      return root;
 
    // Passo 2: atualiza altura
    root->altura = max(altura(root->esq), altura(root->dir)) + 1;
 
    /* 3. Verifica fator de balanceamento */
    int fb = getFatorBalanceamento(root);

    // 4 casos se a arvore tenha se tornado desbalanceada
    // esq esq
    if (fb > 1 && getFatorBalanceamento(root->esq) >= 0)
        return rotaSimplesDir(root);

    // esq dir
    if (fb > 1 && getFatorBalanceamento(root->esq) < 0){
        root->esq =  rotaSimplesEsq(root->esq);
        return rotaSimplesDir(root);
    }

    // dir dir
    if (fb < -1 && getFatorBalanceamento(root->dir) <= 0)
        return rotaSimplesEsq(root);

    // dir esq
    if (fb < -1 && getFatorBalanceamento(root->dir) > 0){
        root->dir = rotaSimplesDir(root->dir);
        return rotaSimplesEsq(root);
    }

    return root;
}

void emOrdem(struct noArvoreAVL *root){
    if(root != NULL){
        emOrdem(root->esq);
        printf("%d ", root->info);
        emOrdem(root->dir);
    }
}

int main(){
  struct noArvoreAVL *root = NULL;

    root = insert(root, 9);
    root = insert(root, 5);
    root = insert(root, 10);
    root = insert(root, 0);
    root = insert(root, 6);
    root = insert(root, 11);
    root = insert(root, -1);
    root = insert(root, 1);
    root = insert(root, 2);
 
    /* The constructed AVL Tree would be
            9
           /  \
          1    10
        /  \     \
       0    5     11
      /    /  \
     -1   2    6
    */
 
    printf("Percurso Em Ordem:\n");
    emOrdem(root);
    printf("\n");
 
    root = deletenoArvoreAVL(root, 10);
 
    /* The AVL Tree after deletion of 10
            1
           /  \
          0    9
        /     /  \
       -1    5     11
           /  \
          2    6
    */
 
    printf("\nPercurso Em Ordem depois da exclusão do no 10 \n");
    emOrdem(root);
    printf("\n");
    return 0;
}