avl.c

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

avl.c
// Por: Walisson Prrª
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct no{
	int var ;
	struct no *es, *di ;
	int balance ;
}no ;
int max(int a, int b)
{
	return ((a > b)? a : b) ;
}
// altura da subarvore
int altura(no *avl)
{
	if(avl == NULL)
		return -1 ;
	return avl->balance ;
}
// rotacao simples a direita
no *rotate_r(no *avl)
{
	no *aux = avl->di ;
	avl->di = aux->es ;
	aux->es = avl ;
	
	avl->balance = max( altura(avl->es), altura(avl->di)) + 1 ;
	aux->balance = max( altura(aux->es), avl->balance) + 1 ;
	return aux ;
}
// rotacao simples a esquerda
no *rotate_l( no *avl )
{
	no *aux ;
	aux = avl->es ;
	avl->es = aux->di ;
	aux->di = avl ;
	
	avl->balance = max( altura( avl->es ), altura( avl->di ) ) + 1 ;
	aux->balance = max( altura( aux->es ), avl->balance) + 1 ;
	return aux ;
}
//rotacao dupla a esquerda
no *rotate_DL( no *avl )
{
	//	r e
	avl->es = rotate_r( avl->es ) ;
	return avl = rotate_l(avl) ;
}
//rotacao dupla a direita 
no *rotate_DR(no *avl)
{
	//	e r
	avl->di = rotate_l(avl->di);
	return avl = rotate_r(avl);
}
// insercao
no* push(no *avl, int elemento)
{
	if( (avl) == NULL)
	{
		avl = (no *)malloc(sizeof(no)) ;
		avl->var = elemento ;
		avl->es = NULL ;
		avl->di = NULL ;
		avl->balance = 0 ;
	}
	else if(elemento < avl->var)
	{
		avl->es = push( avl->es, elemento ) ;
		if( altura( avl->es ) - altura( avl->di ) == 2 )
			if( elemento < avl->es->var )
				avl = rotate_l( avl ) ;
		else
			avl = rotate_DL( avl ) ;
	}
	else if( elemento > avl->var )
	{
		avl->di = push( avl->di, elemento ) ;
		if( altura( avl->di ) - altura( avl->es ) == 2 )
			if( elemento > avl->di->var )
				avl = rotate_r( avl ) ;
		else
			avl = rotate_DR( avl ) ;
	}
	avl->balance = max( altura(avl->es), altura(avl->di)) + 1 ;
	return avl ;
}
void print(no *avl, int prof)
{
	if(avl == NULL)
		return ;
	print(avl->di, prof+1) ;
	printf("%*d\n", 5*prof, avl->var);
	print(avl->es, prof+1) ;
}
main()
{
	no *avl = NULL ;
	int n ;
	char i ;
	printf( "i para insercao.\np para printar.\ns para sair\n" ) ;
	while( scanf(" %c", &i) && i != 's' )
	{
		if( i == 'i' )
		{
			int ans ;
			scanf(" %d", &ans ) ;
			avl = push( avl, ans ) ;
		}
		if(i == 'p')
		{
			print( avl, 0 ) ;
			puts("") ;
		}
	}
}