L2Q2 ~AVL Tree~Complete

#include <stdio.h>
#include <string.h>


//AVL BY DIMASDARK ~ALGORITMOS~

int _numeroElementos = 0;
int _nivel = 0;
int _valor = 0;
int _rotacao = 0;

typedef struct avl
{
    int identificador;
    int valor;
    int altura; //hdireita - hesquerda
    struct avl* esquerda;
    struct avl* direita;

} Arv;

Arv* inicializar()
{
    return NULL;
}

//Remove o minimo a direita e ja retorna o no
Arv* removerMinimoDireita(Arv* arvdir)
{
    Arv* aux = new Arv();

    if (arvdir -> esquerda == NULL)
    {
        aux = arvdir -> direita;
        delete(arvdir);
        return aux;
    }
    else
    {
        arvdir -> esquerda = removerMinimoDireita(arvdir -> esquerda);
        return arvdir;
    }
}


int altura(Arv* no)
{
    if (no == NULL)
        return 0;
    int hesq = altura(no->esquerda);
    int hdir = altura(no->direita);
    return hesq > hdir ? hesq + 1 : hdir + 1;
}

int maximo(int a, int b)
{
    return (a > b)? a : b;
}

int fatorBalanceamento(Arv* raiz)
{
    if (raiz == NULL)
        return 0;
    return altura(raiz->esquerda) - altura(raiz->direita);
}

Arv* novoNo(int i, int v)
{
    Arv* no = new Arv();
    no->identificador = i;
    no->valor = v;
    no->esquerda = NULL;
    no->direita = NULL;
    no->altura = 1;
    return(no);
}


Arv* rotacaoDireita(Arv* no)
{

    Arv* a = no->esquerda;
    Arv* b = a->direita;

    // Faz a rotacao
    a->direita = no;
    no->esquerda = b;

    // Atualiza altura
    no->altura = maximo(altura(no->esquerda), altura(no->direita))+1;
    a->altura = maximo(altura(a->esquerda), altura(a->direita))+1;

    // Retorna o novo no
    return a;
}

Arv* rotacaoEsquerda(Arv* no)
{
    Arv* a = no->direita;
    Arv* b = a->esquerda;

    a->esquerda = no;
    no->direita = b;

    no->altura = maximo(altura(no->esquerda), altura(no->direita))+1;
    a->altura = maximo(altura(a->esquerda), altura(a->direita))+1;

    return a;
}

//Pega menor valor da esquerda de uma subarvore
Arv* pegaMenor(Arv* no)
{
    Arv* aux = no;
    while (aux->esquerda != NULL)
        aux = aux->esquerda;

    return aux;
}

Arv* buscaNo(Arv* arv, int t, int &nivel, int &valor,int n = 0)
{
    nivel = n;
    Arv* aux = arv;
    if (arv == NULL)
        return NULL; /* árvore vazia: não encontrou */
    else
    {
        if (t > arv->identificador)
        {
            aux = buscaNo(arv->direita, t, nivel, valor, n+1);
        }
        else if (t < arv->identificador)
        {
            aux = buscaNo(arv->esquerda,t, nivel, valor, n+1);
        }
        else
        {
            valor = aux->valor;
        }
        return aux;
    }
}

Arv* insere(Arv* no, int i, int v, int &nivel, int &rotacao, int n = 0)
{
    nivel = n;
    //Se for nulo, ele vai ser a cabeça
    if (no == NULL)
        return(novoNo(i, v));

    if (i < no->identificador)
        no->esquerda  = insere(no->esquerda, i, v, nivel, rotacao, n+1);
    else
        no->direita = insere(no->direita, i, v, nivel, rotacao, n+1);

    //atualiza altura
    no->altura = maximo(altura(no->esquerda), altura(no->direita)) + 1;

    //ver se esta balanceado
    int bal = fatorBalanceamento(no);

    // Se nao estiver balanceado, existem 4 possibilidades

    // Pesado pra esquerda ~rotação direita
    if (bal > 1 && i < no->esquerda->identificador)
    {
        nivel -= 1;
        rotacao = 1;
        return rotacaoDireita(no);
    }

    // Pesado pra direita ~rotação esquerda
    if (bal < -1 && i > no->direita->identificador)
    {
        rotacao = 2;
        nivel -= 1;
        return rotacaoEsquerda(no);
    }

    // rotacao dupla pra direita
    if (bal > 1 && i > no->esquerda->identificador)
    {
        rotacao = 3;
        nivel -= 2;
        no->esquerda =  rotacaoEsquerda(no->esquerda);
        return rotacaoDireita(no);
    }

    // rotação dupla pra esquerda
    if (bal < -1 && i < no->direita->identificador)
    {
        rotacao = 4;
        nivel -= 2;
        no->direita = rotacaoDireita(no->direita);
        return rotacaoEsquerda(no);
    }

    //Retorna arvore atualizada
    return no;
}

Arv* remover(Arv* raiz, int identificador)
{
    if (raiz == NULL)
        return raiz;

    // Valor menor, pega sub a esquerda
    if ( identificador < raiz->identificador )
        raiz->esquerda = remover(raiz->esquerda, identificador);

    //Valor maior, pega sub a direita
    else if( identificador > raiz->identificador )
        raiz->direita = remover(raiz->direita, identificador);

    //Achou
    else
    {
        // CASO TENHA 1 OU ZERO FILHOS
        if( (raiz->esquerda == NULL) || (raiz->direita == NULL) )
        {
            Arv* aux = raiz->esquerda ? raiz->esquerda : raiz->direita;

            // FOLHA
            if(aux == NULL)
            {
                aux = raiz;
                raiz = NULL;
            }
            else // NO COM 1 FILHO
                *raiz = *aux;

            delete(aux);
        }
        else
        {
            // NO COM 2 FILHOS
            Arv* aux = pegaMenor(raiz->direita);

            // Copia as informações do sucessor
            raiz->identificador = aux->identificador;
            raiz->valor = aux->valor;

            // Deleta o sucessor
            raiz->direita = remover(raiz->direita, aux->identificador);
        }
    }

    // Se o no for nulo
    if (raiz == NULL)
        return raiz;

    // atualiza altura do no
    raiz->altura = maximo(altura(raiz->esquerda), altura(raiz->direita)) + 1;

    // verifica se no esta desbalanceado
    int bal = fatorBalanceamento(raiz);

    // Caso desbalanceie, tem 4 possibilidades

    // Pesa pra esquerda ~rotacao direita
    if (bal > 1 && fatorBalanceamento(raiz->esquerda) >= 0)
        return rotacaoDireita(raiz);

    // Rotação dupla pra direita
    if (bal > 1 && fatorBalanceamento(raiz->esquerda) < 0)
    {
        raiz->esquerda =  rotacaoEsquerda(raiz->esquerda);
        return rotacaoDireita(raiz);
    }

    // Pesa pra direita ~rotacao esquerda
    if (bal < -1 && fatorBalanceamento(raiz->direita) <= 0)
        return rotacaoEsquerda(raiz);

    // Rotacao dupla esquerda
    if (bal < -1 && fatorBalanceamento(raiz->direita) > 0)
    {
        raiz->direita = rotacaoDireita(raiz->direita);
        return rotacaoEsquerda(raiz);
    }

    return raiz;
}


void preOrdem(Arv* arv, bool cabeca = true)
{

    if (arv != NULL)
    {
        if (cabeca)
            printf("%d", arv->identificador);
        else
            printf(" %d", arv->identificador);
        preOrdem(arv->esquerda, false);
        preOrdem(arv->direita, false);
    }

}

void deletarArvore(Arv* arvore)
{
    if ( arvore != NULL )
    {
        deletarArvore( arvore->esquerda );
        deletarArvore( arvore->direita );
        delete(arvore);
    }
}



int main()
{

    freopen("L2Q2.in", "r", stdin);
    freopen("L2Q2.out", "w", stdout);
    Arv* arvore = new Arv();
    arvore = inicializar();

    int comando = 0, identificador = 0, valor = 0;

    while (scanf("%d", &comando) != EOF)
    {
//        printf("Operacoes: %d\n", operacoes);




    //comando 1
       if (comando == 1)
                { //Se for comando 1 le mais 2
                    scanf("%d %d", &identificador, &valor);
                    arvore = insere(arvore,  identificador, valor, _nivel, _rotacao);

                    if (_rotacao == 0)
                    {
                        printf("1 %d N\n", _nivel);
                    }
                    else if (_rotacao == 1)
                    {
                        printf("1 %d RSD\n", _nivel);
                    }
                    else if (_rotacao == 2)
                    {
                        printf("1 %d RSE\n", _nivel);
                    }
                    else if (_rotacao == 3)
                    {
                        printf("1 %d RDD\n", _nivel);
                    }
                    else if (_rotacao == 4)
                    {
                        printf("1 %d RDE\n", _nivel);
                    }
                    _nivel = 0;
                    _rotacao = 0;
                }
            else if (comando == 2)
            {
                //comando 2 ~busca~le mais um
                scanf("%d", &identificador);
                if (buscaNo(arvore, identificador, _nivel, _valor))   //Se encontrou
                {
                    printf("2 %d %d", _nivel,_valor);

                }
                else
                {
                    //Imprime nada
                }
                printf("\n");
                _nivel = 0;
                _valor = 0;
            }
            else if (comando == 3)      //imprimir em preOrdem
            {
                   preOrdem(arvore);
                    printf("\n");
            }
            else if (comando == 0){ //reinicia a arvore
                    Arv* aux = arvore;
                    arvore = inicializar();
                    deletarArvore(aux);

            }


            }

    return 0;

}