Pesquisa em memoria primaria(ARVORE BINARIA)

Páginas: 63 (15572 palavras) Publicado: 7 de junho de 2015
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária

3

Introdução - Conceitos Básicos

Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária

Introdução - Conceitos Básicos

• Conjunto de registros ou arquivos ⇒ tabelas

• Estudo de como recuperar informação a partir de uma grande massa
de informação previamente armazenada.

• Tabela:

• A informação é dividida em registros.associada a entidades de vida curta, criadas na memória interna
durante a execução de um programa.

• Cada registro possui uma chave para ser usada na pesquisa.

• Arquivo:

• Objetivo da pesquisa:

geralmente associado a entidades de vida mais longa, armazenadas
em memória externa.

Encontrar uma ou mais ocorrências de registros com chaves iguais à
chave de pesquisa.

• Distinção não é rígida:
tabela:arquivo de índices

• Pesquisa com sucesso X Pesquisa sem sucesso.

arquivo: tabela de valores de funções.

Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária

1

Pesquisa em Memória Primária
• Introdução - Conceitos Básicos

• Pesquisa Digital

• Pesquisa Sequencial

– Trie

• Pesquisa Binária

– Patricia

• Árvores de Pesquisa
– Árvores Binárias de Pesquisa
sem Balanceamento
– ÁrvoresBinárias de Pesquisa
com Balanceamento
∗ Árvores SBB
∗ Transformações para Manutenção da Propriedade SBB

• Transformação de Chave
(Hashing)

Pesquisa em Memória Primária∗

– Funções de Transformação
– Listas Encadeadas
– Endereçamento Aberto
– Hashing Perfeito com ordem Preservada

Última alteração: 7 de Setembro de 2010

– Hashing Perfeito Usando
Espaço Quase Ótimo
∗ Transparências

elaboradas porFabiano C. Botelho, Israel Guerra e Nivio Ziviani

2

Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.1

7

Pesquisa Sequencial

Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária

Dicionário

• Método de pesquisa mais simples: a partir do primeiro registro,
pesquise sequencialmente até encontrar a chave procurada; então
pare.

• Nome comumente utilizado para descrever umaestrutura de dados
para pesquisa.
• Dicionário é um tipo abstrato de dados com as operações:

• Armazenamento de um conjunto de registros por meio do tipo
estruturado arranjo:

1. Inicializa
2. Pesquisa

#define MAXN 10
typedef long TipoChave;

3. Insere

typedef struct TipoRegistro {

4. Retira

TipoChave Chave;

• Analogia com um dicionário da língua portuguesa:

/∗ outros componentes ∗/

– Chaves⇐⇒ palavras

} TipoRegistro ;

– Registros ⇐⇒ entradas associadas com cada palavra:
∗ pronúncia
∗ definição
∗ sinônimos
∗ outras informações

typedef int TipoIndice ;
typedef struct TipoTabela {
TipoRegistro Item [ MAXN + 1];
TipoIndice n;
} TipoTabela;

Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária

Algoritmos de Pesquisa ⇒ Tipos Abstratos de Dados
• É importante considerar osalgoritmos 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.

5

Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária

Escolha do Método de Pesquisa mais Adequado a uma
Determinada Aplicação
• Depende principalmente:
1. Quantidade dos dados envolvidos.
2. Arquivoestar sujeito a inserções e retiradas frequentes.

• 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 para formar um arquivo maior.

6

Se conteúdo do arquivo éestável é importante minimizar o tempo
de pesquisa, sem preocupação com o tempo necessário para
estruturar o arquivo

4

Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.1

11

Pesquisa Sequencial: Análise

Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.1

10

Pesquisa Sequencial

• Pesquisa com sucesso:

• Utilização de um registro sentinela na posição zero do...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Pesquisa sobre arvore binaria e recursividade
  • Árvore Binárias
  • Arvore Binaria
  • Arvore Binaria
  • Arvore Binaria
  • Árvore Binária
  • Árvore Binária
  • Arvore binaria

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!