Pesquisa em memoria primaria(ARVORE BINARIA)

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
– Árvores Biná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 por Fabiano 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 uma