Classificaçao e Pesquisa

CLASSIFICAÇÃO E PESQUISA

PESQUISA EM MEMÓRIA
PRIMÁRIA

PESQUISA

EM

MEMÓRIA PRIMÁRIA

 Introdução
 Pesquisa Sequencial
 Pesquisa Binária
 Árvores de Pesquisa
 Árvores Binárias de Pesquisa sem Balanceamento
 Árvores Binárias de Pesquisa com Balanceamento

 Árvores SBB
 Transformações para Manutenção da Propriedade SBB

PESQUISA

EM

MEMÓRIA PRIMÁRIA

 Pesquisa Digital
 Trie
 Patricia

 Transformação de Chave (Hashing)
 Funções de Transformação

 Listas Encadeadas
 Endereçamento Aberto
 Hashing Perfeito

INTRODUÇÃO – CONCEITOS BÁSICOS
 Estudo de como recuperar informação a partir de uma grande massa de informação previamente armazenada

 A informação é dividida em registros
 Cada registro possui uma chave para ser usada na pesquisa  Objetivo da pesquisa:
 Encontrar uma ou mais ocorrências de registros com chaves iguais à chave de pesquisa

 Pesquisa com sucesso X Pesquisa sem sucesso

INTRODUÇÃO – CONCEITOS BÁSICOS
 Tabelas


Conjunto de registros ou arquivos  TABELAS

 Tabela:
 associada a entidades de vida curta, criadas na memória interna durante a execução de um programa

 Arquivo:
 geralmente associado a entidades de vida mais longa, armazenadas em memória externa

 Distinção não é rígida:
 tabela: arquivo de índices
 arquivo: tabela de valores de funções

ALGORITMOS

DE

PESQUISA – TADS

 É importante considerar os algoritmos de pesquisa como tipos abstratos de dados, com um conjunto de operações associado a uma estrutura de dados, de tal forma que haja uma independência de implementação para as operações ALGORITMOS

DE

PESQUISA – TADS

 Operações mais comuns:
1. Inicializar a estrutura de dados
2. Pesquisar um ou mais registros com determinada chave 3. Inserir um novo registro
4. Retirar um registro específico
5. Ordenar um arquivo para obter todos os registros em ordem de acordo com a chave

6. Ajuntar dois arquivos