Arvore AVL inserção e remocão

# include"stdio.h"


# include"stdlib.h"








struct avl
{
    int info;
    int bal;
    struct  avl *pai;
    struct  avl *esq;
    struct  avl *dir;
};














int avl_height ( struct  avl *node )
{
    /*retorna a altura da arvore*/


    int esq, dir;


    if ( node == NULL ) return -1;


    esq = avl_height ( node->esq );
    dir = avl_height ( node->dir );


    if ( esq > dir )
        return esq + 1;
    else
        return dir + 1;
}


























struct  avl *rotacaoLL(struct  avl *p )
/* Rotação simples para a esquerda */
{
    struct  avl *q;


    q = p->esq;
    //----------------> Realiza a rotação
    p->esq = q->dir;
    if ( q->dir != NULL )
        q->dir->pai = p;
    q->dir = p;
    q->pai = p->pai;
    if ( p->pai != NULL )
    {
        if ( p->pai->esq == p )
            p->pai->esq = q;
        else
            p->pai->dir = q;
    }
    p->pai = q;
    //----------------> Rebalanceia
    q->bal = avl_height ( q->esq ) - avl_height ( q->dir );
    p->bal = avl_height ( p->esq ) - avl_height ( p->dir );


    return q;
}








struct avl *rotacaoRR ( struct avl *p )
/* Rotação simples para a direita */
{
    struct avl *q;


    q = p->dir;
    //----------------> Realiza a rotação
    p->dir = q->esq;
    if ( q->esq != NULL )
        q->esq->pai = p;
    q->esq = p;
    q->pai = p->pai;
    if ( p->pai != NULL )
    {
        if ( p->pai->esq == p )
            p->pai->esq = q;
        else
            p->pai->dir = q;
    }
    p->pai = q;
    //----------------> Rebalanceia
    q->bal = avl_height ( q->esq ) - avl_height ( q->dir );
    p->bal = avl_height ( p->esq ) - avl_height ( p->dir );


    return q;
}






void avl_remove ( struct avl **node,int info )
{
    int aux;
    struct avl * P;
    /*se se o elemento nao esta na arvore sai da funçao*/
    if ( *node == NULL ) return ;




    if ( info<(*node)->info )


    {
        /*se remove da esquerda é como inserir na direita*/
        avl_remove ( &((*node)->esq), info );
        (*node)->bal=avl_height ( (*node)->esq ) - avl_height ( (*node)->dir );
        if( (*node)->bal==-2)
        {


            if( (*node)->dir->bal!=1)
            {
                (*node)= rotacaoRR ( (*node) );
            }
            else if(  (*node)->dir->bal==1)
            {
                (*node)->dir=rotacaoLL ( (*node)->dir);
                (*node)= rotacaoRR ( (*node) );
            }
        }










    }
    else
    {
        if ( info>(*node)->info )
        {
            /*se remove da direita é como inserir na esquerda*/


            avl_remove ( &((*node)->dir), info );
            (*node)->bal=avl_height ( (*node)->esq ) - avl_height ( (*node)->dir );
            if( (*node)->bal==2)
            {


                if( (*node)->esq->bal!=-1)
                {
                    (*node)= rotacaoLL ( (*node) );
                }
                else if( (*node)->esq->bal==-1)
                {
                    (*node)->esq =rotacaoRR ( (*node)->esq );
                    (*node)=  rotacaoLL ( (*node) );
                }
            }










        }
        else
        {
            /*se achou a informaçao na folha ela remove*/
            if ( info==(*node)->info )
            {




                if ( ((*node)->esq==NULL)&&((*node)->dir==NULL ))
                {
                    free ( *node );
                    *node = NULL;






                }
                else
                {
                    
                    /*se tive so filho direito ou lado direito mais alto troca com menor valor a direita ate chegar a folha  remover do lado mais alto é muito importante */
                    if ( ((*node)->esq==NULL&&(*node)->dir!=NULL)||(*node)->bal==-1)
                    {
                        P=(*node)->dir;
                        while(P->esq!=NULL)
                            P=P->esq;




                        aux=P->info;
                        avl_remove ( &((*node)), P->info );
                        (*node)->info=aux;










                    }
                    else
                    {
                        /*se tiver so filho esquerdo ou os 2 filhos troca com menor valor a esquerda ate chegar a folha */
                        P=(*node)->esq;
                        while(P->dir!=NULL)
                            P=P->dir;




                        aux=P->info;
                        avl_remove ( &((*node)), P->info );
                        (*node)->info=aux;










                    }




                }




            }






        }




    }


}






























void inserir(struct avl **pRaiz,struct avl **PAI, int numero)
{
    if(*pRaiz == NULL)
    {
        * pRaiz = (struct avl  *) malloc(sizeof(struct avl ));
        (*pRaiz)->esq = NULL;
        (*pRaiz)->dir = NULL;
        (*pRaiz)->info = numero;
        (*pRaiz)->pai=(*PAI);
        (*pRaiz)->bal=0;
    }
    else
    {
        if(numero <(*pRaiz)->info)
        {
            inserir(& (*pRaiz)->esq,& (*pRaiz), numero);
            (*pRaiz)->bal=avl_height ( (*pRaiz)->esq ) - avl_height ( (*pRaiz)->dir );
            if( (*pRaiz)->bal==2)
            {
                if(  (*pRaiz)->esq->bal==1)
                    (*pRaiz)= rotacaoLL ( (*pRaiz) );
                else if(  (*pRaiz)->esq->bal==-1)
                {
                    (*pRaiz)->esq =rotacaoRR ( (*pRaiz)->esq );
                    (*pRaiz)=  rotacaoLL ( (*pRaiz) );
                }
            }




        }
        else
        {
            if(numero >(*pRaiz)->info)
            {
                inserir(& (*pRaiz)->dir,& (*pRaiz), numero);
                (*pRaiz)->bal=avl_height ( (*pRaiz)->esq ) - avl_height ( (*pRaiz)->dir );
                if( (*pRaiz)->bal==-2)
                {
                    if(  (*pRaiz)->dir->bal==-1)
                        (*pRaiz)= rotacaoRR ( (*pRaiz) );
                    else if(  (*pRaiz)->dir->bal==1)
                    {
                        (*pRaiz)->dir=rotacaoLL ( (*pRaiz)->dir);
                        (*pRaiz)= rotacaoRR ( (*pRaiz) );
                    }
                }
            }




        }
    }
}








/* Output function */


void Output(struct avl *Tree,int Level)
{
    int i;
    if (Tree)
    {
        Output(Tree->dir, Level+1);
        printf("\n");
        for (i = 0; i < Level; i++)
            printf("   ");
        printf("(%d)%d",Tree->bal, Tree->info);
        Output(Tree->esq, Level+1);
    }
}


void destruir(struct avl **Tree)
{


    if ((*Tree)!=NULL)
    {
        destruir(&(*Tree)->dir);


        destruir(&(*Tree)->esq);
        free((*Tree));
        (*Tree)=NULL;
    }
}






/* Function main */


int main()
{
    int op;
    int  valor ;


    struct avl *L,*aux ;
    L = aux= NULL;
    do
    {




        printf("\nopcao\n1-insere\n2remove\n3destruir\n4-sair ");
        scanf("%d", &op);
        switch(op)
        {


        case 1:
                
           for(int i=0; i<1000; i++)
                inserir(&L,&aux,rand()%1000);
            Output(L, 1);




            fflush(stdin);
            break;


        case 2:


       




             for(int i=0; i<1000; i++)
            avl_remove ( &L, rand()%1000);
            Output(L, 1);
           
                   










            break;


        case 3:
            destruir (&L);
            Output(L, 1);
            break;




        }


    }
    while(op!=4);


    return 0;


}