AVL INSERÇÃO E REMOÇÃO

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

#include<stdio.h>
#include<stdlib.h>
typedef struct no{
	int dado ;
	int altura ;
	struct no *es, *di ;
}no;
inline int max( int a, int b )
{
	return (a > b)? a : b ;
}
inline int height( no *raiz )
{ 
	if(raiz == NULL)
		return 0 ;
	return raiz->altura ;
}
inline int balance( no *raiz )
{
	if(raiz == NULL)
		return 0 ;
	return ( height(raiz->es) - height(raiz->di) ) ;
}
inline void rotate_r(no **raiz)
{
	no *aux = (*raiz)->es ;
	(*raiz)->es = aux->di ;
	aux->di = (*raiz) ;
	(*raiz)->altura = max(height((*raiz)->es), height((*raiz)->di)) + 1 ;
	aux->altura = max(height(aux->es), height(aux->di)) + 1 ;
	(*raiz) = aux ;
}
inline void rotate_l(no **raiz)
{
	no *aux = (*raiz)->di ;
	(*raiz)->di = aux->es;
	aux->es = (*raiz) ;
	(*raiz)->altura = max(height((*raiz)->es), height((*raiz)->di)) + 1 ;
	aux->altura = max(height(aux->es), height(aux->di)) + 1 ;
	(*raiz) = aux ;
}
inline void double_rotate_r( no **raiz )
{
	rotate_l( &(*raiz)->es ) ;
	rotate_r( &(*raiz) ) ;
}
inline void double_rotate_l(no **raiz)
{
	rotate_r( &(*raiz)->di ) ;
	rotate_l( &(*raiz) ) ;
}
inline void verifica_balance( no **raiz )
{
	int b = balance( (*raiz) ) ;
	if( b > 1 )
	{
		if( balance( (*raiz)->es ) >= 0 )
			rotate_r( &(*raiz) ) ;
		else
			double_rotate_r( &(*raiz) ) ;
	}
	if( b < -1)
	{
		if( balance( (*raiz)->di ) <= 0 )
			rotate_l( &(*raiz) ) ;
		else
			double_rotate_l( &(*raiz) ) ;
	}
}
inline void insere( no **raiz, int var )
{
	if( (*raiz) == NULL )
	{
		(*raiz) = (no *)malloc( sizeof( no ) ) ;
		(*raiz)->es = (*raiz)->di = NULL ;
		(*raiz)->dado = var ;
		(*raiz)->altura = 1 ;
		return ;
	}
	if( (*raiz)->dado > var )
		insere( &(*raiz)->es, var) ;
	if( (*raiz)->dado < var )
		insere( &(*raiz)->di, var) ;
	(*raiz)->altura = max( height( (*raiz)->es ), height( (*raiz)->di ) ) + 1 ;
 	verifica_balance( &(*raiz) ) ;
}
inline no *filho(no *raiz)
{
	if( raiz == NULL )
		return raiz ;
	if(raiz->es == NULL)
		return raiz ;
	return filho( raiz->es ) ;
}
inline void remover( no **raiz, int var )
{
	if( (*raiz) == NULL )
		return ;
	else if( (*raiz)->dado > var)
		remover( &(*raiz)->es, var ) ;
	else if( (*raiz)->dado < var)
		remover( &(*raiz)->di, var ) ;
	else if( (*raiz)->es != NULL && (*raiz)->di != NULL )
	{
		no *aux = NULL ;
		aux = filho( (*raiz)->di ) ;
		(*raiz)->dado = aux->dado ;
		remover( &(*raiz)->di, aux->dado ) ;
	}
	else
	{
		no *aux = (*raiz) ;
		if( (*raiz)->di == NULL )
			(*raiz) = (*raiz)->es ;
		else
			(*raiz) = (*raiz)->di ;
		free(aux) ;
	}
	if( (*raiz) == NULL )
		return ;
	(*raiz)->altura = max( height( (*raiz)->es ), height( (*raiz)->di ) ) + 1 ;
	verifica_balance( &(*raiz) ) ;
}
// 10 6 15 3 7 17 2 4
inline void print( no *raiz, int prof )
{
	if( raiz == NULL )
		return ;
	print(raiz->di, prof + 1) ;
	printf("%*d\n", prof*4 , raiz->dado ) ;
	print(raiz->es, prof + 1) ;
}
main()
{
	no *raiz = NULL;
	while(1)
	{
		puts("1 - inserir\n2 - remover\n3 - printar\n4 - sair") ;
		int op ;
		scanf(" %d", &op);
		if(op == 4)
			break ;
		else if(op == 1)
		{
			int ans, var ;
			printf("Quantidade de valores: ") ;
			scanf("%d", &var) ;
			printf("Inserir valores: ") ;
			while(var--) 
			{
				scanf("%d", &ans ) ;
				insere( &raiz, ans);
			}
		}
		else if(op == 2)
		{
			int ans ;
			printf("Remover: ");
			scanf("%d", &ans) ;
			remover( &raiz, ans ) ;
		}
		else
		{
			puts("**** AVL ****");
			print(raiz, 0);
		}
		puts("\n");
	}
}