arvore-avl (Completa)

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

// Algoritmos para insercao e pesquisa em arvore AVL
// Autor: Denilson Alves Pereira
// Elaboracao: 26/08/2010
// Referencia: Jayme Luiz Szwarcfiter & Lilian Markenzon
// Estruturas de Dados e seus Algoritmos
// LTC Editora, 1994
// Adaptacao do codigo de Nivio Ziviani, Projeto de Algoritmos
// compilacao: g++ -g -o arvore-avl arvore-avl.c
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include "FuncoesAuxiliares.h"
typedef long long int TipoChave;
typedef struct Registro {
 TipoChave Chave;
 char *URL;
 /* outros componentes */
} Registro;
typedef struct No * Apontador;
typedef struct No {
 Registro Reg;
 Apontador Esq, Dir;
 long int balanceamento;
} No;
typedef Apontador TipoDicionario;
void Pesquisa(Registro *x, Apontador *p) //Função pesquisa recursiva
{ 
 if (*p == NULL)
 { 
 printf("Erro : Registro nao esta presente na arvore\n");
 return;
 }
 if (x->Chave < (*p)->Reg.Chave) 
 { 
 Pesquisa(x, &(*p)->Esq);
 return;
 }
 if (x->Chave > (*p)->Reg.Chave)
 Pesquisa(x, &(*p)->Dir);
 else
 *x = (*p)->Reg;
} 
void rotacaoEsquerda(Apontador *p) 
{
 if((*p)==NULL || (*p)->Dir==NULL) /*Verifica se o no passado, ou seu filho a direita e nulo*/
 {
 printf("Rotacao impossivel de ser realizada!\n");
 }
 else
 {
 //Efetua rotacao a esquerda 
 Apontador pfilhoDir = (*p)->Dir;
 (*p)->Dir = pfilhoDir->Esq;
 pfilhoDir->Esq = (*p);
 (*p)->balanceamento=0;
 (*p) = pfilhoDir;
 }
 
}
void rotacaoDireita(Apontador *p)
{
 
 if((*p)==NULL || (*p)->Esq==NULL) /*Verifica se o no passado, ou seu filho a esquerda e nulo*/
 {
 printf("Rotacao impossivel de ser realizada!\n");
 }
 else
 {
 //Efetua rotacao a direita
 Apontador pfilhoEsq = (*p)->Esq;
 (*p)->Esq = pfilhoEsq->Dir;
 pfilhoEsq->Dir = (*p);
 (*p)->balanceamento=0;
 (*p) = pfilhoEsq;
 }
}
void rotacaoEsqDir(Apontador *pAvo)
{
 if((*pAvo)->Esq==NULL || (*pAvo)->Esq->Dir==NULL || (*pAvo)==NULL) /*Verifica se o no avo, ou seu filho a esquerda, ou seu filho a direita do filho a esquerda e nulo*/
 {
 printf("Rotacao Impossivel de ser realizada!\n");
 }
 else
 {
 Apontador pPaiEsq = (*pAvo)->Esq;
 Apontador pfilhoDir = pPaiEsq->Dir;
// printf("rotacao dupla esquerda-direita com %ld\n", pfilhoDir->Reg.Chave);
 
 pPaiEsq->Dir = pfilhoDir->Esq;
 pfilhoDir->Esq = pPaiEsq;
 (*pAvo)->Esq = pfilhoDir->Dir;
 pfilhoDir->Dir = (*pAvo);
 if (pfilhoDir->balanceamento == -1) (*pAvo)->balanceamento = 1;
 else (*pAvo)->balanceamento = 0;
 if (pfilhoDir->balanceamento == 1) pPaiEsq->balanceamento = -1;
 else pPaiEsq->balanceamento = 0;
 (*pAvo) = pfilhoDir;
 } 
}
void rebalanceamento1 (Apontador *p, long int *h)
{
 if ((*p)->Esq->balanceamento == -1)
 { 
// printf("rotacao a direita com %ld\n", (*p)->Esq->Reg.Chave);
//Rotacao a direita utilizando a funcao separada
 rotacaoDireita(&(*p));
 }
 else
 {
 //Rotacao Dupla Esquerda-Direita
 rotacaoEsqDir(&(*p));
 }
 
 (*p)->balanceamento = 0;
 (*h) = 0;
}
void rotacaoDirEsq(Apontador *pAvo)
{
 if((*pAvo)->Dir==NULL || (*pAvo)->Dir->Esq==NULL || (*pAvo)==NULL) /*Verifica se o no avo, ou seu filho a esquerda, ou seu filho a direita do filho a esquerda e nulo*/
 {
 printf("Rotacao Impossivel de ser realizada!\n");
 }
 else
 {
 Apontador pPaiDir=(*pAvo)->Dir;
 Apontador pfilhoEsq =pPaiDir->Esq;
// printf("rotacao dupla direita-esquerda com %ld\n", pfilhoEsq->Reg.Chave);
 pPaiDir->Esq = pfilhoEsq->Dir;
 pfilhoEsq->Dir = pPaiDir;
 (*pAvo)->Dir = pfilhoEsq->Esq;
 pfilhoEsq->Esq = (*pAvo);
 if (pfilhoEsq->balanceamento == 1) (*pAvo)->balanceamento = -1;
 else (*pAvo)->balanceamento = 0;
 
 if (pfilhoEsq->balanceamento == -1) pPaiDir->balanceamento = 1;
 else pPaiDir->balanceamento = 0;
 (*pAvo) = pfilhoEsq;
 } 
}
void rebalanceamento2 (Apontador *p, long int *h)
{
 if ((*p)->Dir->balanceamento == 1)
 { 
// printf("rotacao a esquerda com %ld\n", (*p)->Dir->Reg.Chave);
 // Rotacao a Esquerda utilizando uma função separada
 rotacaoEsquerda(&(*p));
 }
 else
 { 
 // Rotacao Dupla Direita-Esquerda
 rotacaoDirEsq(&(*p));
 }
 (*p)->balanceamento = 0;
 (*h) = 0;
}
/*
Insere o registro x na arvore referenciada por p.
h retorna se houve ou nao alteracao na altura da subarvore do no em questao,
induzindo a atualizacao do campo balanceamento. 
*/
int Insere (Registro x, Apontador *p,long int *h)
{
 if (*p == NULL) {
 *p = (Apontador)malloc(sizeof(No));
 (*p)->Reg= x;
 (*p)->Esq = NULL; (*p)->Dir = NULL;
 (*p)->balanceamento = 0;
 *h = 1; // balanceamento deve ser verificado
 }
 else if (x.Chave < (*p)->Reg.Chave) {
 Insere(x, &(*p)->Esq, h);
 if (*h) { // verifica balanceamento
 switch ((*p)->balanceamento) {
 case 1: // subarvores esquerda e direita passam a ter a mesma altura
 (*p)->balanceamento = 0; (*h) = 0; break;
 case 0: // subarvore esquerda passa a ter uma unidade de altura maior do que a da direita
 (*p)->balanceamento = -1; break;
 case -1: // subarvore esquerda passa a ter duas unidades de altura maior do que a da direita
 rebalanceamento1(p, h); break;
 }
 }
 }
 else if (x.Chave > (*p)->Reg.Chave) {
 Insere(x, &(*p)->Dir, h);
 if (*h) { // verifica balanceamento
 switch ((*p)->balanceamento) {
 case -1: // subarvores esquerda e direita passam a ter a mesma altura
 (*p)->balanceamento = 0; (*h) = 0; break;
 case 0: // subarvore direita passa a ter uma unidade de altura maior do que a da esquerda
 (*p)->balanceamento = 1; break;
 case 1: // subarvore direita passa a ter duas unidades de altura maior do que a da esquerda
 rebalanceamento2(p, h); break;
 }
 }
 }
 else {
 *h = 0;
 return -1;
 }
 return 0;
} 
void Inicializa(Apontador *Dicionario)
{ *Dicionario = NULL;
}
void Central(Apontador p)
{ if (p == NULL)
 return;
 Central(p->Esq);
 printf("%ld\n", p->Reg.Chave);
 Central(p->Dir);
} 
long int max (long int x, long int y) {
 if (x > y) return x;
 else return y;
}
int Altura(Apontador p) {
 if (p == NULL) { return -1; }
 return 1 + max(Altura(p->Esq), Altura(p->Dir));
}
void TestaI(No *p, int pai)
{ if (p == NULL)
 return;
 if (p->Esq != NULL) 
 { if (p->Reg.Chave < p->Esq->Reg.Chave) 
 { printf("Erro: Pai %ld menor que filho a esquerda %ld\n", p->Reg.Chave, p->Esq->Reg.Chave);
 exit(1);
 }
 }
 if (p->Dir != NULL) 
 { if (p->Reg.Chave > p->Dir->Reg.Chave) 
 { printf("Erro: Pai %ld maior que filho a direita %ld\n", p->Reg.Chave, p->Dir->Reg.Chave);
 exit(1);
 }
 }
 TestaI(p->Esq, p->Reg.Chave);
 TestaI(p->Dir, p->Reg.Chave);
}
void Testa(No *p)
{ if (p != NULL)
 TestaI(p, p->Reg.Chave);
}
void ListarTabulado(No *p,int nivel)
{
 int i;
 nivel++;
 if (p != NULL)
 {
 for(i=1;i<nivel;i++)
 {
 printf(" ");
 }
 
 printf("%d\n",p->Reg.Chave);
 ListarTabulado(p->Esq,nivel);
 ListarTabulado(p->Dir,nivel);
 }else printf("---\n");
}
int main(int argc, char *argv[])
{
 TipoDicionario Dicionario;
 Registro x;
 long int val,h;
 long int qnt_reg,result, pos_rand;
 char**vetor;
 int importou=0;
 clock_t inicio,fim;
 Inicializa(&Dicionario);
 int opcao;
 do{
 system("cls");
 printf("\n Menu \n");
 printf("\n 0 - Inserir valor");
 printf("\n 1 - Imprimir Arvore");
 printf("\n 2 - Altura da
Arvore");
 if(importou==1) printf("\n 3 - Simular pesquisa de 100.000 chaves aleatorias");
 else printf("\n 3 - Simular pesquisa de 100.000 chaves aleatorias (IMPORTE DADOS.TXT)");
 printf("\n 4 - Pesquisar na Arvore");
 printf("\n 5 - Importar dados.txt");
 printf("\n 6 - Sair");
 printf("\n Digite a opcao desejada : ");
 
 scanf("%d",&opcao);
 switch(opcao)
 {
 case 0:
 printf("\n\nDigite o valor: ");
 scanf("%d",&val);
 x.Chave=val;
 x.URL=NULL;
 if(Insere(x,&Dicionario,&h)==-1) printf("Erro : Registro ja existe na arvore\n");
 Testa(Dicionario);
 break;
 case 1:
 ListarTabulado(Dicionario,0); 
 system("pause");
 break;
 case 2:
 printf("Altura da arvore = %d\n", Altura(Dicionario));
 system("pause");
 break;
 case 3:
 if(importou!=1) printf("Importe DADOS.TXT...\n");
 else
 {
 qnt_reg=qntRegArquivo("dados.txt");
 inicio=clock();
 int i;
 for(i=0;i<100000;i++)
 {
 x.Chave=PMrand()%qnt_reg;
 Pesquisa(&x,&Dicionario);
 }
 fim=clock();
 printf("A execucao durou %fms\n",(double)(fim - inicio));
 }
 system("pause"); 
 break;
 case 4:
 printf("Digite o numero que deseja pesquisar: ");
 scanf("%ld",&x.Chave);
 x.URL=NULL;
 inicio=clock();
 int k;
 //for(k=0;k<=100000;k++) Pesquisa(&x,&Dicionario);
 Pesquisa(&x,&Dicionario);
 fim=clock();
 if(x.URL!=NULL) puts(x.URL);
 printf("A execucao durou %fms\n",((double)(fim - inicio))/100000);
 system("pause");
 break;
 case 5:
 printf("Por favor, aguarde...\n");
 result=tamanho_arquivo("dados.txt");
 if(result==-1)
 {
 system("cls");
 printf("Arquivo nao encontrado!\n");
 system("pause");
 }
 else
 {
 vetor = (char**)(malloc ( sizeof (char*)*(result) ) );
 carregavetor(vetor,"dados.txt",&qnt_reg);
 
 system("cls");
 printf("Arquivo carregado com sucesso, foram %ld bytes, e %ld registros carregados!\n",result,qnt_reg);
 printf("Por favor aguarde, a arvore esta sendo preenchida...\n");
 long long int i=1;
 int *teste;
 int out;
 long long int div;
 
 teste=(int*)malloc(sizeof(int)*qnt_reg);
 inicio=clock();
 while(i<=qnt_reg)
 {
 
 pos_rand=PMrand()%qnt_reg;
 out=teste[pos_rand];
 if(out!=1)
 {
 x.Chave=pos_rand;
 x.URL=strdup(vetor[pos_rand]);
 Insere(x,&Dicionario,&h);
 teste[pos_rand]=1;
 i++;
 }
 }
 fim=clock();
 printf("A execucao durou %.0fms\n",((double)(fim - inicio)));
 system("pause");
 }
 importou=1;
 break;
 }
 }while(opcao!=6);
// Central(Dicionario);
 return 0;
}