Pesquisa em Memória Primária
Algoritmos e Estruturas de Dados II
Pesquisa em Memória Primária

Pesquisa:



Objetivo:


Recuperação de informação em um grande volume de
dados.
Informação é dividida em registros e cada registro contém
uma chave.
Encontrar itens com chaves iguais a chave dada.
Aplicações:


Contas em um banco
Reservas de uma companhia aérea
2
Pesquisa em Memória Primária

Escolha do método de busca



Quantidade de dados envolvidos.
Frequência com que operações de inserção e retirada são
efetuadas.
Métodos de pesquisa:



Pesquisa sequencial
Pesquisa binária
Árvore de pesquisa




Árvores binárias de pesquisa sem balanceamento
Árvores binárias de pesquisa com balanceamento
Pesquisa digital
Hashing
3
Tabelas de Símbolos

Estrutura de dados contendo itens com chaves que
suportam duas operações



Inserção de um novo item
Retorno de um item que contém uma determinada chave.
Tabelas são também conhecidas como dicionários


Chaves – palavras
Item – entradas associadas as palavras (significado,
pronúncia)
4
Tipo Abstrato de Dados

Considerar os algoritmos de pesquisa como tipos
abstratos de dados (TADs), com um conjunto de
operações associado a uma estrutura de dados,


Há independência de implementação para as operações.
Operações:





Inicializar a estrutura de dados
Pesquisar um ou mais registros com uma dada chave
Inserir um novo registro
Remover um registro específico
Ordenar os registros
5
Pesquisa Sequencial

Método de pesquisa mais simples

A partir do primeiro registro, pesquisa sequencialmente até
encontrar a chave procurada

Uma possibilidade de implementação é armazenar os
registros em um vetor.

Inserção de um novo item


Adiciona no final do vetor.
Remoção de um item com chave específica

Localiza o elemento, remove-o e coloca o último item do
vetor em seu lugar.
6
Pesquisa Sequencial
# define MAX
10
typedef int TipoChave;
typedef struct {
TipoChave Chave;
/* outros componentes */
} Registro;
typedef int Indice;
typedef struct {
Registro Item[MAX + 1];
Indice n;
} Tabela;
7
Pesquisa Sequencial
void Inicializa(Tabela *T) {
T->n = 0;
}
/* retorna 0 se não encontrar um registro com a chave x */
Indice Pesquisa(TipoChave x, Tabela *T){
int i;
T->Item[0].Chave = x; /* sentinela */
i = T->n + 1;
do {
i--;
} while (T->Item[i].Chave != x);
return i;
}
8
Pesquisa Sequencial
void Insere(Registro Reg, Tabela *T) {
if (T->n == MAX)
printf("Erro : tabela cheia\n");
else {
T->n++;
T->Item[T->n] = Reg;
}
}
void Remove(TipoChave x, Tabela *T) {
Int idx;
idx = Pesquisa(x, T);
/* se encontrou o item, troca pelo último, reduz o n */
if (idx) T->Item[idx] = T->Item[T->n--];
}
9
Pesquisa Sequencial

Análise:

Pesquisa com sucesso




melhor caso: C(n) = 1
pior caso: C(n) = n
caso médio: C(n) = (n+1) / 2
Pesquisa sem sucesso

C(n) = n + 1
10
Pesquisa Binária

Redução do tempo de busca aplicando o paradigma
dividir para conquistar.
1.
2.
3.
4.

Compare a chave com o registro do meio.
Se for menor, o registro procurado está à esquerda.
Se for maior, está à direita.
Repita.
Restrição: chaves precisam estar ordenadas


Manter chaves ordenadas na inserção pode levar a
comportamento quadrático.
Se chaves estiverem disponíveis no início, um método de
ordenação rápido pode ser usado.
11
Pesquisa Binária

Exemplo: pesquisa pela chave L
A
A
A
C
E
E
E
G
H
I
L
M
N
P
R
A
A
A
C
E
E
E
G
H
I
L
M
N
P
R
H
I
L
M
N
P
R
H
I
L
L
12
Pesquisa Binária

Exemplo: pesquisa pela chave J
A
A
A
C
E
E
E
G
H
I
L
M
N
P
R
A
A
A
C
E
E
E
G
H
I
L
M
N
P
R
H
I
L
M
N
P
R
H
I
L
L
13
Pesquisa Binária
Indice Binaria(TipoChave x, Tabela *T) {
Indice i, Esq, Dir;
if (T->n == 0) return 0; /* vetor vazio */
Esq = 1;
Dir = T->n;
do {
i = (Esq + Dir) / 2;
if (x > T->Item[i].Chave)
Esq = i + 1; /* procura na partição direita */
else
Dir = i - 1; /* procura na partição esquerda */
}
while ((x != T->Item[i].Chave) && (Esq <= Dir));
if (x == T->Item[i].Chave)
return i;
else
return 0;
14
Pesquisa Binária

Análise

Tamanho do vetor:



𝑛 𝑛
2 4
𝑛, , , ..., 1=
𝑛 𝑛 𝑛
𝑛
,
,
,
...,
20 21 22
2𝑙𝑜𝑔2 𝑛
Cerca de 𝑙𝑜𝑔2 𝑛 passos: O(logn).
Ressalva


Alto custo para manter a tabela ordenada: a cada inserção
na posição p da tabela implica no deslocamento de n-p+1
registros a partir da posição p para as posições seguintes.
Portanto, a pesquisa binária não deve ser usada em
aplicações muito dinâmicas.
15
Árvore Binária de Pesquisa

Estrutura de dados constituída de nós.

Cada nó (pai) pode apontar para até dois outros nós
(filhos): denotados por esquerda e direita.

O nó que não possui pai é chamado de raiz. Nós sem
filho são nós folha.

Árvores binárias de pesquisa mantêm a propriedade
de que um nó possui chave maior que a de seu filho à
esquerda e menor que a de seu filho à direita.
16
Árvore Binária de Pesquisa
1
2
4
7
2
6
3
3
5
4
6
9
8
1
17
Árvore Binária de Pesquisa
Nó 1 é o nó
raiz
1
Nó 2 é pai de 4 e 5
2
4
7
1
2
6
3
3
5
4
6
9
8
Nós 4 e 5 são os filhos
à esquerda e direita de
2
18
Árvore Binária de Pesquisa

Busca

Compare a chave com o elemento raiz.

Se for menor, o registro procurado só pode estar à
esquerda.

Se for maior, só pode estar à direita.
19
Árvore Binária de Pesquisa
struct arvore {
struct arvore *esq;
struct arvore *dir;
Registro reg;
};
struct arvore *cria_arvore(Registro reg) {
struct arvore *novo;
novo = malloc(sizeof(struct arvore));
novo->esq = NULL;
novo->dir = NULL;
novo->reg = reg;
}
0
Árvore Binária de Pesquisa: Busca
void Pesquisa(Registro *x, struct arvore *t) {
if (t == NULL) {
printf("Registro não esta presente na árvore\n");
}
else
if (x->Chave < t->reg.Chave)
Pesquisa(x, t->Esq); /* busca no filho esquerdo */
else if (x->Chave > t->reg.Chave)
Pesquisa(x, t->Dir); /* busca no filho direito */
else
*x = t->reg;
}
Árvore Binária de Pesquisa: Inserção


O elemento vai ser inserido como uma folha da
árvore de busca
Vamos procurar o lugar de inserção navegando da
raiz até a folha onde ele será inserido
Árvore Binária de Pesquisa: Inserção
4.5
6
5
4
8
7
2
1
B
A
3
9
C
Árvore Binária de Pesquisa: Inserção
6
4.5
4
5
8
7
2
1
B
A
3
9
C
Árvore Binária de Pesquisa: Inserção
6
5
4.5
4
8
7
2
1
B
A
3
9
C
Árvore Binária de Pesquisa: Inserção
6
5
4
2
1
8
7
A
4.5
3
B
9
C
Árvore Binária de Pesquisa: Inserção
void insere_elemento(struct arvore *t, Registro reg) {
if(reg.Chave < t->reg.Chave) {
/* chave menor */
if (t->esq) { insere_elemento(t->esq, reg); }
else { /* achou local de inserção */
struct arvore *novo = cria_arvore(reg);
t->esq = novo;
}
} else {
/* chave maior ou igual ao nodo atual */
if (t->dir) { insere_elemento(t->dir, reg); }
else {
struct arvore *novo = cria_arvore(reg);
t->dir = novo;
}
}
}
Árvore Binária de Pesquisa: Remoção



Remover folhas
Remover nós com um filho
Remover nós com
dois filhos
6
5
4
8
7
2
1
B
A
3
9
C
Árvore Binária de Pesquisa: Remoção

Nó com 1 filho
6
5
4
8
7
2
1
B
A
3
9
C
Árvore Binária de Pesquisa: Remoção

Nó com 1 filho
6
5
2
1
8
7
3
B
A
9
C
Árvore Binária de Pesquisa: Remoção


Nó com 2 filhos
Substituído pelo registro mais à
esquerda da sub-árvore á
direita ou pelo registro mais à
5
direita da sub-árvore à
esquerda.
4
6
8
7
2
1
B
A
3
9
C
Árvore Binária de Pesquisa: Remoção


Nó com 2 filhos
Substituído pelo registro mais à
esquerda da sub-árvore á
direita ou pelo registro mais à
5
direita da sub-árvore à
esquerda.
4
7
8
7
2
1
B
A
3
9
C
Árvore Binária de Pesquisa: Remoção
struct arvore *remove(struct arvore *t, TipoChave Chave) {
struct arvore *aux;
if(t == NULL) { printf(“elemento ausente\n”); }
else if(Chave < t->reg.Chave){ t->esq=remove(t->esq, Chave); }
else if(Chave > t->reg.Chave){ t->dir=remove(t->dir, Chave); }
else if (t->esq == NULL && t->dir == NULL) {
free(t); return NULL; /* zero filhos */
}
else if(t->esq == NULL) {
aux = t->dir; free(t); return aux; /* 1 filho direita */
}
else if(t->dir == NULL) {
aux = t->esq; free(t); return aux; /* 1 filho esquerda */
} else { /* 2 filhos */
struct arvore *suc = acha_menor(t->dir);
t->reg = suc->reg;
t->dir = remove(t->dir, suc->reg.Chave);
return t;
}
return t;
}
Árvore Binária de Pesquisa: Remoção
void acha_menor(arvore *t) {
if(t->esq == NULL) {
return t;
}
return acha_menor(t->esq);
}
Árvore Binária de Pesquisa: Análise

Número de comparações: busca com sucesso



melhor caso: C(n) = O(1)
pior caso: C(n) = O(n)
caso médio: C(n) = O(log n)