# 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;
}
