35
Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

Embed Size (px)

Citation preview

Page 1: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

Pesquisa em Memória Primária

Algoritmos e Estruturas de Dados II

Page 2: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

2

Pesquisa em Memória Primária

Pesquisa: Recuperação de informação em um grande

volume de dados. Informação é dividida em registros e cada

registro contém uma chave.

Objetivo: Encontrar itens com chaves iguais a chave

dada.

Aplicações: Contas em um banco Reservas de uma companhia aérea

Page 3: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

3

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

Page 4: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

4

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)

Page 5: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

5

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

Page 6: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

6

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.

Page 7: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

7

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;

Page 8: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

8

Pesquisa Sequencialvoid 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;}

Page 9: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

9

Pesquisa Sequencialvoid 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--];}

Page 10: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

10

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

Page 11: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

11

Pesquisa Binária

Redução do tempo de busca aplicando o paradigma dividir para conquistar.1. Compare a chave com o registro do meio.2. Se for menor, o registro procurado está à

esquerda.3. Se for maior, está à direita.4. 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.

Page 12: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

12

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

Page 13: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

13

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

Page 14: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

14

Pesquisa BináriaIndice 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;

Page 15: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

15

Pesquisa Binária

Análise Tamanho do vetor:

, , , ..., = , , , ..., Cerca de 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.

Page 16: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

16

Á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.

Page 17: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

17

Árvore Binária de Pesquisa

6

3

84

9

2

1

6

1

7

4 5

2 3

Page 18: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

18

Árvore Binária de Pesquisa

6

3

84

9

2

1

Nó 2 é pai de 4 e 5

6

1

7

4 5

2 3

Nó 1 é o nó raiz

Nós 4 e 5 são os filhos à esquerda e

direita de 2

Page 19: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

19

Á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.

Page 20: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

Á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

Page 21: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

Á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;

}

Page 22: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

Á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

Page 23: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

Árvore Binária de Pesquisa: Inserção

85

6

4 B

2 A C

1 3 9

7

4.5

Page 24: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

Árvore Binária de Pesquisa: Inserção

85

6

4 B

2 A C

1 3 9

7

4.5

Page 25: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

Árvore Binária de Pesquisa: Inserção

85

6

4 B

2 A C

1 3 9

74.5

Page 26: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

Árvore Binária de Pesquisa: Inserção

85

6

4 B

2 A C

1 3 9

7

4.5

Page 27: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

Á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;

}

}

}

Page 28: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

Árvore Binária de Pesquisa: Remoção

Remover folhas Remover nós com um filho Remover nós com

dois filhos85

6

4 B

2 A C

1 3 9

7

Page 29: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

Árvore Binária de Pesquisa: Remoção Nó com 1 filho

85

6

4 B

2 A C

1 3 9

7

Page 30: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

Árvore Binária de Pesquisa: Remoção Nó com 1 filho

85

6

B2

A C1 3

9

7

Page 31: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

Á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 à direita da sub-árvore à esquerda.

85

6

4 B

2 A C

1 3 9

7

Page 32: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

Árvore Binária de Pesquisa: Remoção

85

7

4 B

2 A C

1 3 9

7

Nó com 2 filhos Substituído pelo registro

mais à esquerda da sub-árvore á direita ou pelo registro mais à direita da sub-árvore à esquerda.

Page 33: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

Á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;}

Page 34: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

Árvore Binária de Pesquisa: Remoçãovoid acha_menor(arvore *t) {

if(t->esq == NULL) {

return t;

}

return acha_menor(t->esq);

}

Page 35: Pesquisa em Memória Primária Algoritmos e Estruturas de Dados II

Á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)