Inteligencia Artificial
Trabalho Universitário: Inteligencia Artificial. Pesquise 862.000+ trabalhos acadêmicosPor: rafaeleneide • 31/3/2014 • 4.100 Palavras (17 Páginas) • 391 Visualizações
Sistema de informação
CLASSIFICAÇÃO E PESQUISA
Unidade: Facnet
Curso: Sistema de Informação
Semestre: 6
Disciplina: Classificação e pesquisa
Aluno:
Rafael Almeida de Oliveira RA: 1299887800
Ramon de Andrade Silva RA: 2504124709
Vinícius Vives Chalub RA: 7632736784
ETAPA 3
- Aula tema: Árvores de Pesquisa, Árvores Binárias de Pesquisa. Árvores AVL. B-Trees.
Esta atividade é importante para que você se familiarize com árvores de busca e assimile seu comportamento e operação.
Para realizá-la é importante seguir os passos descritos.
Relatório 3 – Árvores – Parte 1
1. a análise sobre cada algoritmo utilizado;
2. apontar as diferenças entre os algoritmos;
3. indicar sua aplicação.
Todos os Dados podem utilizar esse algoritmo para realizar a pesquisa:
em_ordem(pt)
{
if(pt == null) return ();
em_ordem (pt ->esq);
visite(raiz);
em_ordem (pt → dir);
}
Para realizar a busca utilizando o no de comparações :
Depende da ordem original dos dados
Se o array oficial está ordenado (ascendente ou descendente), as árvores resultantes só tem filhos a direita ou a esquerda
a inserção do 1o. nó - 0 comparações
a inserção do 2o. nó - 2 comparações
a inserção do 3o. nó - 3 comparações
2 + 3 +....+n = n*(n+1)/2 -1
Complexidade - O(n2) - para inserir n nós
Se a lista original estiver organizada, e se uma árvore completa (parecida com completa) for se formando:
complexidade da inserção = O( n log n )
Para realizar a pesquisa utilizando a Árvore AVL:
void ins_no_avl(AVL *A,float x)
{
int f=0;
A->RaizPrincial = ins_avl(A->RaizPrincial,x,&f);
}
NO_AVL *ins_avl(NO_AVL *RaizPrincial,float x,int *flag)
{
if (RaizPrincial)
{
if (RaizPrincial->elem > x)
{
RaizPrincial->fesq = ins_avl(RaizPrincial->fesq,x,flag);
RaizPrincial->fesq->pai = RaizPrincial;
if (*flag)
{
switch(RaizPrincial->bal){
case -1: RaizPrincial->bal = 0;
*flag = 0;
break;
case 0: RaizPrincial->bal = 1;
break;
case 1: if (RaizPrincial->fesq->bal == 1)
{
RaizPrincial = rotacao_LL(RaizPrincial);
RaizPrincial->bal = 0;
RaizPrincial->fdir->bal = 0;
}
else
{
RaizPrincial = rotacao_LR(RaizPrincial);
if (RaizPrincial->bal == 1)
{
RaizPrincial->fesq->bal = 0;
RaizPrincial->fdir->bal = -1;
}
else
{
RaizPrincial->fesq->bal = 1;
RaizPrincial->fdir->bal = 0;
}
RaizPrincial->bal = 0;
}
*flag = 0;
break;
}
}
}
else
{
RaizPrincial->fdir = ins_avl(RaizPrincial->fdir,x,flag);
RaizPrincial->fdir->pai = RaizPrincial;
if (*flag)
{
switch(RaizPrincial->bal){
case -1:
...