Algoritmos de Busca em Estruturas de Dados

DAOO DESENVOLVIMENTO DE APLICACOES ORIENTADAS A OBJETOS Algoritmos de Busca 1 Definigées Preliminares 2 Busca Sequencial Um algoritmo de busca é um algoritmo que recebe como 3 Busca Sequencial em Tabela Ordenada 4 Busca Sequencial Indexada entrada 5 Busca Binaria 6 Hashing e uma chave c e uma tabela arquivo conjunto de registros ordenados ou nao e tenta achar a localizagao do registro cuja chave é c na tabela O algoritmo deve produzir como saida um ponteiro indice posiao etc dependendo da estrutura de dados usada para a tabela para oO registro ou nuLLptr ou indice invalido posigdo invalida caso um registro com chave c nao seja encontrado na tabela K Algoritmo de indice chave PSeR FIGURA 1 Algoritmo de Busca Uma tabela de registros ou arquivo na qual uma chave 6 usada para a busca é chamada de tabela de busca ou dicionario A tabela pode estar organizada em um vetor de registros em uma lista ligada em uma arvore ou mesmo em um grafo Diferentes técnicas de busca podem ser mais adequadas para determinadas estruturas de tabela WR A busca sequencial é usada para tabelas organizadas em vetores ou listas ligadas O elemento com a dada chave é procurado sequencialmente a partir do primeiro da tabela Exercicio Seja k um vetor com N chaves k0 a kN1 e r um vetor de N registros r0 a rN1 sendo ki a chave de ri Seja C o parâmetro ou chave da busca Escreva o algoritmo da função para achar e retornar o menor inteiro i tal que kiC ou retornar 1 se a chave não for encontrada em k Quantas comparações serão necessárias no pior dos casos 3 Busca Sequencial em Tabela Ordenada Que vantagens há para a busca sequencial o fato da tabela estar ordenada Pense em quando a chave não for encontrada Exercício Altere o programa C do exercício anterior para que a busca sequencial tire vantagem do fato da tabela estar ordenada Se o tamanho da tabela é N quantas comparações serão necessárias no pior dos casos para encontrar ou não o elemento Na média serão necessárias comparações 4 Busca Sequencial Indexada Para melhorar a busca sequencial em tabelas ordenadas podemos utilizar uma tabela auxiliar índice Cada elemento do índice tem dois campos chave kindex ponteiro ou índice para o registro no arquivo correspondente a kindex pindex Os elementos no índice como os elementos da tabela devem estar ordenados pela chave Exemplo Se o tamanho do índice for 14 do tamanho do arquivo cada quarto registro do arquivo é representado no índice como na figura abaixo N 2 FIGURA 2 Busca Sequencial Indexada 41 Implementação Seja N o tamanho do arquivo e seja TI o tamanho do índice Definimos a tabela e o índice da seguinte forma struct RegIndice int kindex chave no indice int pindex ponteiro para chave na tabela struct Registro int k chave TipoReg r registro using Indice RegIndiceTI using Tabela RegistroN A função que encontra a chave C inteira na tabela tab dada a tabela índice ind é implementada da seguinte forma int BuscaSeqIndexadaint C Indice ind Tabela tab int i 0 while iTI indikindexC i int liminf if i0 liminf 0 else liminf indi1pindex int limsup if iTI limsup N1 else limsup indipindex 1 i liminf while ilimsup tabik C i if ilimsup return 1 nao encontrado else return i Vantagem a busca sequencial é feita somente no índice que é menor que a tabela em si Em seguida a busca sequencial é feita somente em uma parte da tabela indicada pelo índice Se a tabela for muito grande um índice secundário índice do índice pode também ser utilizado Outros níveis de índices também são possíveis 5 Busca Binária A busca binária é um dos métodos mais eficientes para se encontrar um elemento em um vetor ordenado 51 O Método A chave é comparada com o elemento do meio da tabela Se for igual a busca terminou Caso contrário ela deve continuar ou na metade inferior se a chave for menor que o elemento do meio ou na metade superior da tabela se a chave for maior que o elemento do meio 52 Implementação A função para se encontrar a chave chave na tabela k de tamanho N é dada por int BuscaBinariachar chave const vectorchar k int inf 0 int sup ksize 1 while inf sup int meio infsup2 if chave kmeio return meio if chave kmeio sup meio 1 else inf meio 1 return 1 nao encontrado Exercício Crie uma função recursiva que implemente a busca binária A busca binária é utilizada quando o arquivo é armazenado em um vetor por precisar calcular o meio mas é inútil quando há muitas inserções e remoções de elementos pois neste caso é mais provável que se utilize listas ligadas e com listas ligadas só é possível descobrir o elemento do meio percorrendoa a partir do primeiro elemento Podemos melhorar a busca binária em vetores ordenados fazendo uma busca interpolada que altera a função de cálculo do meio para algo mais adequado se há informação a respeito da distribuição das chaves no vetor 6 Hashing Obviamente técnicas de busca eficientes são aquelas que minimizam o número de comparações Idealmente gostaríamos de ter uma organização de tabela e uma técnica de busca na qual não precisaríamos fazer nenhuma comparação Seria isto é possível Surpreendentemente a resposta é sim Hashing é um método para referenciar diretamente os registros em uma tabela através de transformações aritméticas das chaves em endereços ou posições da tabela Exemplo Um servigo de telecomunicagdes mantém um arquivo com 100 clientes assinantes cada um tendo um identificador unico de 2 digitos const int MAXTAB100 RegistroAssinante tabclienteMAXTAB tabclientei representa o registro do cliente cujo identificador 6 i Normalmente as tabelas tém tamanho maior do que o numero real de itens O gasto adicional com memoria é compensado com a velocidade de acesso Na pratica no entanto se os identificadores dos clientes tiverem 7 digitos precisariamos de um vetor com 10 milhées de registros Neste caso 0 gasto de memoria nao seria razoavel Suponhamos que os identificadores sejam de 7 digitos mas ha no maximo 1000 clientes do servicgo Precisaremos de um vetor de 1000 registros no maximo Para isso podemos por exemplo utilizar somente os trés ultimos digitos do identificador para determinar a posigdo do registro no vetor 4967000 1 2 8421002 3 397 6589397 398 399 400 2456400 A fungdo que transforma uma chave em um indice de uma tabela 6 chamada fungao de hash No exemplo acima a fungao de hash é hchave chave 1000 Problema como tratar os casos quando hc1 hc2 mas cl c2 por exemplo h1234001 h5678001 Neste caso dizemos que houve Métodos para lidar com colisdes 1 Encadeamento criar lista ligada de todos os itens cujas chaves transformadas pela fungao de hash dao o mesmo valor 2 Rehashing aplicar fungao de hashing secundaria até que uma posigdo vazia seja encontrada Uma boa fungao de hash é aquela que minimiza as colisdes e espalha os registros uniformemente na tabela 61 Rehashing No exemplo anterior queremos inserir um novo cliente com identificador 5032397 Mas h5032397 h6589397 colisão então deve ser inserido em uma outra posição e não na 397 Exemplo Supondo que a posição 398 está vazia poderíamos inserir o elemento nessa posição Esta técnica que consiste em aplicar uma nova função função de rehash no índice calculado pela função de hash é chamada rehashing Uma função de rehash rh recebe o índice de um vetor e produz um outro índice Se hchave já está ocupado com algum registro com chave diferente rh é aplicado ao valor de hchave para encontrar o lugar onde o registro deve ser inserido ou encontrado Se a posição rhhchave também estiver ocupada por alguma outra chave calculase rhrhhchave e assim por diante Quando a função de rehash é i1 i sendo o resultado da aplicação da função de hash dizemos que estamos fazendo rehash linear No exemplo que consideramos acima hchave chave 1000 rhi i1 1000 62 Implementação Se cada registro da tabela de hash tab é definido como sendo composto de chave chave restante do registro reg então a função BuscaInsere que retorna o índice do registro cuja chave é rchave em tab se foi encontrada ou o índice onde foi inserido r em tab se não foi encontrado pode ser assim implementada constexpr int VAZIO 1 valor de chave para indicar que determinada posiç da tabela está vazia struct Registro int chave TipoReg reg int BuscaInsere Registro r Registro tab r é ponteiro para registro procurado ou a inserir na tabela tab é a tabela vetor de registros int i hrchave while tabichave rchave tabichave VAZIO i rhi if tabichave VAZIO posição vazia encontrada na tabela ie chave não encontrada tabichave rchave tabireg rreg return i Observe o laço while ele para quando acha a chave ou quando acha espaço vazio VAZIO Mas pode ser infinito se a tabela estiver cheia e o registro precisar ser inserido ou a função rh for inadequada não cobrindo todas as posições da tabela No primeiro caso podemos usa um contador para indicar se a tabela está cheia MAXTAB é o tamanho da tabela Se tivéssemos por exemplo funções de rehash como rhi i2 1000 rhi i200 1000 haveria muitas colisões e o laço poderia ser infinito mesmo havendo ainda espaço na tabela A situação ideal é quando rhrhi cobre o maior número de inteiros entre 0 e MAXTAB1 Por exemplo rhi ic MAXTAB Neste caso c e MAXTAB devem ser primos entre si 2021 Luiz A de P Lima Jr