Pesquisa Ordenação e Técnicas de Armazenamento: Técnicas de Pesquisa Sequencial e Binária

PESQUISA ORDENACAO E TECNICAS DE ARMAZENAMENTO UNIDADE 4 TECNICAS DE PESQUISAS SEQUENCIAL E BINARIA Keila Barbosa Costa 21082023 1628 Pesquisa Ordenação e Técnicas de Armazenamento httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 230 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento Introducao A busca por uma palavrachave ou por elementos valores ou dados especificos informaées é a base de muitos aplicativos de computaao Serve para visualizar o saldo de uma conta bancaria a partir de um mecanismo de pesquisa na internet por exemplo ou para procurar um arquivo no computador Este inclusive lida com muitos dados por isso precisamos de algoritmos eficientes para a pesquisa No entanto que tipos de algoritmos podem ser eficientes Como os computadores precisam buscar informagées em colecées de dados muito grandes é essencial usar o algoritmo certo para pesquisar mas como definir 0 algoritmo adequado para cada situacdo Sera que podemos aplicar métodos de pesquisas binaria ou sequencial com os dados organizados de qualquer forma A pesquisa é o processo de encontrar o elemento em determinada lista Neste processo verificamos que o item esta disponivel ou nado A pesquisa esta em toda parte desde encontrarmos o endereco de uma pessoa até um numero de telefone em uma lista telef6nica Neste contexto ao longo desta ultima unidade iremos explorar algoritmos comuns que sao usados para procurar dados em computadores Aprenderemos sobre pesquisa binaria em vetores e pesquisa sequencial Veremos a respeito das particularidades de cada uma e como sao aplicadas no dia a dia dos profissionais da area Também estudaremos a respeito das tabelas de dispersdo e das arvores de busca Vamos entdo nos aprofundar a respeito desses assuntos Acompanhe e e 41 Tecnicas de pesquisas Podemos definir como dado um conjunto de elementos em que cada um é identificado por uma chave O objetivo da pesquisa é localizar dentro desse conjunto o elemento que corresponde a uma chave especifica Assim uma tarefa bastante importante hoje nado sé na computaao como também em outras areas éa pesquisa de informacdo contida em coledes de dados De forma geral é desejado que o procedimento seja realizado de forma que nao tenha a necessidade de se verificar toda a colecao VIANA CINTRA NOBRE 2015 A busca é muito comum na area da computacao sendo que podemos usar métodos e estruturas de dados para se encontrar o elemento esperado A busca em vetor por exemplo pode ser feita por indice ou valor A busca realizada pelo indice é considerada uma busca direta ou seja vai direto na posido da memoria Podemos tomar como exemplo o quadro a seguir com o vetor nome Passando no indice 2 teriamos o valor Khyonara 0 1 2 3 4 Keila Arthur Khyonara Berenice Aparecido Quadro 1 Exemplo de quadro com vetores PraCegoVer A figura mostra uma tabela de duas linhas e 4 colunas Na primeira linha da esquerda para a direita temos os valores 0 1 2 3 4 Na segunda linha da esquerda da direita temos os valores Keila Arthur Khyonara Berenice Aparecido httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 330 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento Agora vamos imaginar que nado sabemos onde o valor Khyonara esta Neste caso temos que verificar todos os elementos do vetor até encontralo Portanto para realizar a busca por um valor temos dois métodos a serem considerados realizamos uma busca sequencial ou uma busca binaria A busca sequencial percorre todas as posiées do vetor verificando uma a uma até achar o valor desejado ou simplesmente chegar ao final sem achalo Ja na busca binaria o vetor é dividido ao meio e a busca é realizada apenas em uma das metades Vamos entender melhor sobre os dois métodos a partir de agora No préximo item ainda mostraremos exemplos de como 0 processo é realizado dentro da computaao 411 Busca sequencial De acordo com Viana Cintra e Nobre 2015 a busca sequencial é definida como a procura por um valor x em um vetor L Inspecionando em sequéncia as posiées de L a partir da primeira posido podemos encontrar o x Ao encontrar o elemento procurado podemos dizer que a busca obteve sucesso Caso contrario se chegarmos a ultima posido sem encontrarmos a posicado desejada concluimos que ela nao ocorre no vetor L Vamos imaginar 0 mesmo vetor nome em que desejamos encontrar 0 nome Khyonara Como isto pode ser realizado Comparando elemento a elemento ou seja o valor que esta no indice pelo valor a ser procurado 0 1 2 3 4 Keila Arthur Khyonara Berenice Aparecido Procurar o nome Khyonara Procurar o nome José 14 comparacao Keila KhyonaraNao 14 comparacdo Keila JoséNao 24 comparagao Arthur KhyonaraNao 24 comparacao Arthur JoséNao 34 comparacgao Khyonara KhyonaraSim 34 comparacdo Khyonara JoséNao 42 comparacao Berenice JoséNao Achou o nome do indice 2 54 comparacao Aparecido JoséNao Achou o nome do indice 2 Figura 1 Exemplo de busca sequencial PraCegoVer A figura mostra um exemplo de busca sequencial Primeiramente é mostrado um vetor de 4 posicdes com os seguintes valores Keila Arthur Khyonara Berenice Aparecido Em seguida mostrase um passo a passo para encontrar o nome Khyonara O passo a passo é mostrado através de uma série de comparacées As comparacoées sao 1 comparagdo Keila Khyonara Nao 2 comparacdao Arthus Khyonara Nao 3 comparacao Khyonara Khyonara Sim httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 430 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento Achou 0 nome do indice 2 Por fim mostrasse outro passo a passo Desta vez o objetivo é encontrar o nome José O passo a passo também é mostrado através de uma série de comparacées As comparaées sao 1 comparagao Keila José Nao 2 comparacao Arthur José Nao 3 comparacao Khyonara José Nao 4 comparacdo Berenice José Nao 5 comparaao Aparecido José Nao Achou 0 nome do indice 2 De acordo com a figura anterior temos a primeira comparacéo realizada Nela percorremos o valor que esta na posicao 0 Ele é igual ao valor que estamos procurando Khyonara Na verdade nao Incrementando o indice e realizando a mesma verificacdo podemos dizer que o valor que esta na posido ou no indice 1 60 mesmo que estamos procurando Arthur é igual a Khyonara Também ndo certo Incrementando novamente o indice e realizando mais uma comparaao podemos dizer que o indice 2 é igual ao valor que estamos procurando Khyonara é igual a Khyonara Sim Assim encontramos nosso elemento a partir da posiao do indice que esta no valor buscado Agora imagine que iremos procurar o nome José Perceba que ele nao se encontra no vetor que estamos analisando por isso o algoritmo ira parar de executar quando chegar ao final retornando e informando que nao foi encontrado o nome desejado No entanto imaginemos que 0 vetor tenha mais de um milhdo de posi6es sendo que o valor desejado nao se encontra no vetor Sera necessario entdo realizar um milhdo de verificagées para se descobrir que 0 valor nao se encontra no vetor a ser verificado Isto ocorre com frequéncia na busca sequencial sendo que para resolver o problema de o algoritmo ter que verificar elemento por elemento podemos usar a busca binaria Na busca binaria o vetor precisa estar ordenado A mesma ldgica serve para nimeros textos ou letras Assim agora que vocé ja conhece o processo de como fazer uma busca sequencial iremos conhecer como se daa busca binaria Vejamos Oe 412 Busca binaria A busca binaria s6 funciona em vetores que estejam ordenados Isto porque ela divide sucessivamente 0 vetor ao meio e procura apenas em uma das metades ou seja 0 algoritmo é executado até encontrar o valor ou posiao Vamos ver um exemplo com a figura a seguir Observe com atenao httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 530 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento 0 1 2 3 4 5 6 7 8 9 10 Il 2 4 6 8 10 12 14 16 18 20 22 24 Posiao inicial 0 Posiao final11 2 4 6 8 10 12 14 16 18 20 22 24 Posiao inicial6 Meio8 Final11 2 4 6 8 10 12 14 16 18 20 22 24 Posigdoinicial9 Meio10 Final11 2 4 6 8 10 12 14 16 18 20 22 24 Posigao inicial 20 Figura 2 Exemplo de busca binaria PraCeoVer A figura mostra um exemplo de busca binaria Inicialmente é mostrado um vetor de 12 posiées com os seguintes valores 2 4 6 8 10 12 14 16 18 20 22 24 Abaixo do vetor tem duas frases destacando duas posic6es do vetor As frases sdo respectivamente Posicao inicial 0 e Posicao final 11 Em seguida mostrase 0 mesmo vetor Contudo mudouse as frases que indicam as posiées em destaque Desta vez temos 3 frases que sdo respectivamente Posiao inicial 6 Meio 8 e Final 11 Depois disso mostrase o mesmo vetor novamente Desta vez houve outra alteracdo nas frases que destacam algumas posiées do vetor As frases sao respectivamente Posicao inicial 9 Meio 10 e Final 11 Por fim mostrase novamente esse mesmo vetor com uma Unica frase destacando uma Unica posicao A frase diz Posicao inicial 20 Imagine o vetor ordenado na figura anterior Pretendemos procurar 0 elemento 20 por isso a primeira coisa que o vetor ira fazer é descobrir a posicdo inicial 0 e depois a posiao final 11 Sera realizado o seguinte calculo meio posiaolnicial posicaoFinal 2 meio 0112 meio 55 Arredondar para o inteiro mais préximo 5 Temos assim que a quinta posiao sera a posiao do meio com valor igual a 12 Encontrada a posiao do meio sera realizada a verificaao a seguir Se meio numeroProcurado 18 20 Achou o valor Do contrario Se numeroProcurado meio 20 18 posicdoFinal meio 1 Do contrario httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 630 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento posidolnicial meio 1 Realizar novamente a posiao inicial Dessa forma podemos verificar 0 nimero procurado ou seja se o elemento do meio é igual ao numero procurado 12 20 Como a afirmacado é falsa seguese entdo para 20 12 Como a afirmacdo também nao é verdadeira o vetor ira andar com a posicAo inicial Como a posiao inicial era 0 agora ele vai passar a ser posicdolnicial meio 1 5 1 6 entdo recebe a posicdo 6 Perceba que a posicdo 6 tem o valor 14 A parte do vetor com valor menor que 12 posiao 5 foi desconsiderada pois como o vetor esta ordenado iremos considerar apenas da posi4o 6 até a 11 Com a posido inicial 6 e a posicao final 11 é realizado um calculo para obtermos a posido meio como vemos a Seguir até se alcancgar a posicdo desejada No nosso caso tratase da posiao 9 Observe meio posiaoInicial posicaoFinal 2 meio 6112 meio 85 inteiro 8 vetor formado por numeros inteiros Realizando a verificacdo temos Se meio numeroProcurado 12 20 Achou o valor Do contrario Se numeroProcurado meio 20 12 posicdoFinal meio 1 Do contrario posicdolnicial meio 1 Assim foram necessarias muitas verificagdes até se encontrar 0 elemento desejado porém se fossemos usar a verificagdo da busca sequencial seriam necessarias ainda mais verificaées Isto é para a busca sequencial terfamos que realizar 10 verificagées enquanto a busca binaria realizou apenas trés a VAMOS PRATICAR e De acordo com o que vimos imagine o vetor ordenado a seguir Pr elemento 22 usando a busca binaria eee eee eee renee reer e reer eeeeeeeee eee eee httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 730 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento 3 7 9 Jl 12 14 15 22 23 25 PraCegoVer A figura mostra um vetor de 10 posicédes Os valores armazenados nesse vetor sao respectivamente 3 7 9 11 12 14 15 22 23 25 Agora que ja entendemos a respeito das buscas sequencial e binaria no t6pico a seguir veremos com mais detalhes a respeito das tabelas de dispersdo também conhecidas como tabelas de espalhamento ou tabelas de hashing Acompanhe 42 Tabelas de dispersao Um paradigma muito comum no processamento de dados envolve o armazenamento de informacé6es em uma tabela e posteriormente a recuperacdo dos dados guardados Por exemplo considere um banco de dados de registros de carteira de trabalho ele contém um registro para cada carteira de trabalho emitida sendo que dado o numero da carteira de trabalho podemos procurar as informagées associadas a ele Normalmente 0 banco de dados compreende uma coledo de pares e valores As informacées sdo recuperadas do banco a partir de uma determinada chave No caso do banco de dados da carteira de trabalho a chave é 0 numero da carteira de trabalho Ja no caso de uma tabela de simbolos por exemplo a chave é 0 nome do simbolo Viana Cintra e Nobre 2015 nos explicam que podemos definir as tabelas de dispersao também conhecidas como tabelas de espalhamento ou de hashing como aquelas que armazenam uma colecdo de valores sendo que cada valor esta associado a uma chave As chaves precisam ser todas diferentes pois sao usadas para mapear os valores das tabelas As vantagens da tabela de dispersao é que ela pode ser usada como indice porém a grande vantagem esta em se ter uma operacdo cujo acesso é direto Isto é ndo sera preciso fazer um percurso em uma arvore ou comparar registro Ainda de acordo com Viana Cintra e Nobre 2015 outra vantagem é 0 curso da operacao O1 acesso em que a determinagao da posiao onde o registro sera armazenado vira de uma funao hashing A ideia essencial por tras de uma tabela de dispersdo é que todas as informades sdéo armazenadas em uma matriz de tamanho fixo O hashing é usado para identificar a posido em que um item deve ser armazenado Quando acontece uma colisdo 0 item em colisdo é armazenado em outro lugar na matriz VIANA CINTRA NOBRE 2015 Os tipos de hashings podem ser divididos em Clique no recurso a seguir Hashing Em que é permitido armazenar um conjunto de informaées de tamanho limitado fechado Hashing Em que é permitido armazenar um conjunto de informaées de tamanho ilimitado aberto A fungao de hashing sera responsavel por converter a chave em um indice de alocaao Vejamos um exemplo de funao de dispersdo hchave endereco Funcao hx x mod 7 em que x éa chave e hx é 0 endereco httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 830 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento h4315 615 em que 4315 éachave e 615 é 0 endereco VAMOS PRATICAR e De acordo com a funcao de hashing encontre o endereco para a chave Adote a formula Funcao hx x mod 5 ener eeeeeeeeeeeeeeeeee reer ee ener eee Assim temos que a funcdo hashing vai ditar o desempenho do algoritmo trazendo 0 ponto em que devemos armazenar o registro O segredo esta na qualidade da fundo hashing ou seja quanto melhor for a funao mais dispersos os registros serdo Além disso o hashing funciona da seguinte forma a chave D1 passa pela fundo que é convertida no indice 1 enquanto a chave D2 passa pela fundo que vai ser convertida no indice 2 Veja o esquema a seguir para compreender melhor D1 1 L Pa Fungao hashing D 2 Figura 3 Fundo hashing PraCegoVer A figura mostra um exemplo de uma funcdo de hashing No centro da imagem é mostrado um circulo contendo o texto Funcdo hashing Conectado a esse circulo tem mais outros 4 circulos Um dos circulos esta posicionado no canto superior esquerdo e possui 0 texto D1 Outro circulo esta posicionado no httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 930 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento canto superior direito e possui o texto 1 O terceiro circulo esta posicionado no canto inferior esquerdo e possui 0 texto D Por fim o Ultimo circulo esta posicionado no canto inferior direito e possui 0 texto 2 Agora vejamos um exemplo de como a funao de hashing funciona em uma tabela de dados Observe 0 quadro na sequéncia indice Chave x Valor Fungao hx x mod 7 0 1 2 30 Khyonara hx x mod 7 307 3 45 Keila hx x mod 7 457 4 5 40 Arthur hx x mod 7 407 6 Quadro 2 Processo da funao hashing PraCegoVer A figura mostra uma tabela para descrever a funado de hashing A tabela possui 8 linhas e 4 colunas Na primeira linha temos a colunas 1 com valor Indice coluna 2 com valor Chave coluna 3 com o valor Valor coluna 4 com o valor Fungao hx x mod 7 Na segunda linha temos a coluna 1 com o valor 0 Na terceira linha temos a coluna 1 com o valor 1 Na quarta linha temos a coluna 1 com o valor 2 coluna 2 com o valor 30 coluna 3 com o valor Khyonara coluna 4 com o valor hx x mod 7 307 Na quinta linha temos a coluna 1 com o valor 3 coluna 2 com o valor 45 coluna 3 com o valor Keila coluna 4 com o valor hx x mod 7 457 Na sexta linha temos a coluna 1 com o valor 4 Na sétima linha temos a coluna 1 com o valor 5 coluna 2 com o valor 40 coluna 3 com o valor Arthur coluna 4 com o valor hx x mod 7 407 Observe que 0 valor 30 nao esta na posiao 0 mas sim na posido 2 devido a formula ou seja hx x mod 7 307 42 Como o restante é aproximadamente 2 temos para a chave 30 o lugar de alocacdo para a posido 2 Damesma forma procede para as demais chaves httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 1030 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento Agora digamos que desejamos incluir uma nova chave que também na divisdo com 7 gere um resto 2 A este caso damos o nome de colisdo ou hashing fechado hash overflow eee eeeeeeeeeeeeeeeeeeeee ener ener VOCE SABIA e O hash overflow é quando tentamos inserir um elementochave na tabela de dispersdo mas a tabela ja se encontra cheia invalidando essa inserdo Neste caso dizemos que aconteceu um estouro de tabela de dispersdo ee A colisao acontece quando determinado indice posido no vetor gerado por uma chave se encontra alocado por um registro Isto é quando o valor de uma chave ganha uma posiccdo que ja esta cheia Vejamos um exemplo na figura a seguir httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 1130 21082023 1628 Pesquisa Ordenação e Técnicas de Armazenamento httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 1230 PraCegoVer A imagem mostra o processo de hashing fechado Inicialmente mostrase a palavra chaveinformaçao que possui uma seta conectando com a palavra Funçao e por sua vez possui uma seta apontando para a palavra funçao Abaixo desta palavra esta escrito vetor com as posiçoes Em seguida e mostrado uma tabela com 13 linhas e 4 colunas Enumerando cada linha destas tabelas temos Linha 1 Chave Resto Adote hx x mod m 84 0 Linha 2 47 5 h47 47 mod 14 5 70 1 Linha 3 9 9 h9 9 mod 14 9 25 3 Linha 4 75 5 47 4 Linha 5 16 2 47 4 Linha 6 24 10 75 5 Linha 7 52 10 34 6 Linha 8 84 0 12 7 Figura 4 Processo de hashing fechado 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento Linha 9 70 0 8 Linha 10 10 10 99 Linha 11 25 11 24 10 Linha 12 34 6 52 11 Linha 13 12 12 h12 12 mod 14 12 10 12 Na figura anterior temos 0 esquema de como funciona o hashing fechado em que temos o dado com a chave que é convertida pela funao em um indice no qual sera alocada a informagao Podemos observar que nas chaves 24 e 52 acontece uma colisdo pois as duas tém um resto 10 ou seja precisam ser alocadas na mesma posido 10 Porém a posiao ja tem uma chave alocada que chegou primeiro 24 Neste caso o que fazemos com a chave que precisa ser alocada sendo que sua posiao ja esta ocupada por outra chave O 24 ja esta alocando a posicdo 10 entdo a chave 52 vai procurar a proxima posiao vazia que seria a 11 Portanto a chave 52 ficara na posiao 11 com asterisco deixando claro que se trata de uma chave deslocada Na implementaao real adotamos que cada entrada Hi da tabela é uma lista cujo elemento tém hash code i Para inserir um elemento na tabela computamos o hash code i e inserimos o elemento na lista ligada a Hi A inserao é realizada seguindo a ordem de cima para baixo na tabela sendo que ao final da lista retornase para o inicio seguindo o ciclo novamente A chave deslocada s6 sai da posido também deslocada se for para ir a sua respectiva posiao de acordo com a funcao A técnica de hashing aberto por outro lado denota que em uma tabela cada posiao possui um ponteiro que da para uma lista encadeada sendo que esta contém todas as chaves mapeadas por uma fundo hashing na posicdo VIANA CINTRA NOBRE 2015 Alias na técnica aberta nao existe limite de chaves que podem ser armazenadas na tabela A primeira estratégia comumente conhecida como hashing aberto ou encadeamento separado é manter uma lista de todos os elementos com hashing no mesmo valor Vejamos um exemplo concreto na tabela a seguir em que é possivel observar na posido 10 duas colis6es Assim foram adicionados dois campos extras para alocar as posiGes httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 1330 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento EWE Resto Adote hx x mod m Oo 84 70 AT 5 1 h47 47 mod 145 9 9 2 16 15 5 h9 9 mod 149 3 16 2 4 24 10 5 47 75 52 10 6 34 84 0 T 70 0 8 10 10 5 9 25 1l 10 24 52 10 34 6 11 25 12 12 h1212mod1412 12 12 Tabela 1 Processo de hashing aberto PraCegoVer A figura mostra o processo de hashing aberto O processo é descrito através de uma tabela contendo 13 linhas e 8 colunas Enumerando cada linha da tabela temos Linha 1 Chave Resto adote hx x mod m 0 84 70 Linha 2 47 5 h47 47 mod 14 5 1 Linha 3 9 9 h9 9 mod 14 9 2 16 Linha 4 75 5 3 Linha 5 16 2 4 Linha 6 2410 5 47 75 Linha 7 52 10 6 34 Linha 8 84 0 7 Linha 9 70 0 8 Linha 10 10 10 9 9 Linha 11 25 11 10 24 52 10 Linha 12 34 6 11 25 Linha 13 12 12 h12 12 mod 14 12 12 12 Para realizar uma localizagdo usamos a funado hash para determinar qual lista percorrer Em seguida percorremos a lista da maneira normal retornando a posido em que o item foi encontrado Para executar uma insercdo percorremos a lista apropriada para verificar se o elemento ja esta no lugar Se sao esperadas duplicatas geralmente um campo extra é mantido e este seria incrementado no caso de uma correspondéncia VIANA CINTRA NOBRE 2015 Se o elemento for novo ele sera inserido na frente da lista ou no final Este é httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 1430 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento um problema facil de resolver enquanto 0 cédigo esta sendo gravado As vezes novos elementos sao inseridos na frente da lista pois é conveniente e também porque frequentemente acontece que os elementos inseridos recentemente tém maior probabilidade de serem acessados em um futuro proximo a VAMOS PRATICAR e Usando a tabela a seguir realize a localizagdo das posides das chaves u funcdo hash Em seguida percorra a lista da maneira normal retort posicdo em que o item foi encontrado Em caso de colisdo adote o pro hashing aberto para resolver o conflito a 50 1 23 2 Adote hx x mod 3 45 3 17 4 5 Ie 37 6 PraCegoVer A figura mostra uma tabela com 7 linhas e 8 colunas Enumerando cada linha da tabela temos Linha 1 Chave Resto Adote hx mod 3 0 Linha 2 50 Adote hx mod 3 1 Linha 3 23 Adote hx mod 3 2 Linha 4 45 Adote hx mod 3 3 Linha 5 17 Adote hx mod 3 4 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 1530 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento Linha 6 9 Adote hx mod 3 5 Linha 7 37 Adote hx mod 3 6 Assim 0 hashing aberto é uma estratégia em que nenhum dos objetos é realmente armazenado na matriz da tabela de hashing Em vez disto ele é armazenado em uma lista separada da matriz interna da tabela 6 43 Arvores de buscas balanceadas Uma arvore de pesquisa binaria balanceada mantém automaticamente sua altura pequena garantida como logaritmica para uma sequéncia de inserc6es e exclus6es Conforme Viana Cintra e Nobre 2015 essa estrutura fornece implementacées eficientes para dados abstratos como matrizes associativas Diferentemente das listas em que as informaées se encontram em uma sequéncia nas arvores esses dados sao representados de forma hierarquica sendo que cada n6 possui um contetdo VIANA CINTRA NOBRE 2015 ee VOCE QUER VER e Uma arvore binaria é composta de nds sendo que cada no contém uma referéncia esquerda uma referéncia direita e um elemento de dados O n6 superior da arvore é chamado de raiz Para compreender melhor o funcionamento de uma arvore binaria sugerimos que vocé assistia ao video disponivel no link httpsyoutubePgZflufXGUU Com ele sera mais facil identificar os pontos apresentados eee eeeeeeeeeeeeeeeeeeeeeeeeeeeee eee eee Nas arvores de busca balanceada as chaves alocadas sdo mantidas ordenadas permitindo que a operacdo de busca seja realizada percorrendose um ramo da arvore desde a base até chegar ao infcio VIANA CINTRA NOBRE 2015 As arvores de pesquisa séo como um método para armazenar dados de modo a oferecer suporte para as operac6ées de inserado rapida pesquisa e exclusao O principal problema das arvores de busca é 0 desejo que elas sejam equilibradas para que as pesquisas possam ser executadas rapidamente No entanto nado é necessario que elas sejam perfeitas visto que seria muito caro de manter para inserir ou excluir um novo elemento Nesse contexto varios algoritmos foram desenvolvidos para a construcgdo de arvores de busca que permanecem equilibradas httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 1630 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento eo 431 Arvore AVL A arvore AVL é uma arvore binaria que vai seguir as mesmas regras para inserdo busca e remocdo de elementos bem como adicionar tais regras a métodos para se manter o equilibrio da arvore Ela é muito balanceada em suas inser6des e exclus6es procurase executar uma rotina de balanceamento em que as alturas das subarvores sejam proximas a VOCE O CONHECE e Georgy Adelson era um matemiatico e cientista de computacdo Nascido em Samara Adelson foi originalmente educado como um matematico puro Seu primeiro trabalho com o colega e eventual colaborador de longa data Alexander Kronrod em 1945 ganhou um prémio da Sociedade Matematica de Moscou Ele comecou a trabalhar em inteligéncia artificial e outros tépicos aplicados no final da década de 1950 Junto com Evgenii Landis inventou a arvore AVL em 1962 Esta foi a primeira estrutura de dados da arvore de pesquisa binaria balanceada ja conhecida ener eeeeeeee rere ener ener eee eee eee eee Conforme nos explicam Viana Cintra e Nobre 2015 as operaées basicas como busca insercdo remocao e outras levam um tempo proporcional ao nimero de niveis da arvore binaria de busca Isto é a quantidade de opera6ées para busca inserdo e remocao no pior dos casos depende de quantos niveis existem na arvore Dada esta observacdo podemos concluir que é desejado manter a arvore sempre com a menor quantidade de niveis possivel para que as operac6es basicas nado custem tanto tempo Vejamos um exemplo em que a inserdo dos nimeros se encontra em sequéncia 10 11 12 13 14 15 16 17 e 18 ou seja foi inserido numero por numero de forma sequencial na arvore Observe a figura a seguir httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 1730 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento 10 11 12 13 14 15 Arvore desequilibrada 15 15 15 15 15 15 15 15 ce J Arvore ideal 15 Figura 5 Distribuido de arvore sequencial PraCegoVer A figura mostra duas representa6es de arvores Na primeira representacdo temos uma arvore desequilibrada em que todos os nds estado conectados do seu lado direito A sequéncias de nds é 10 ao lado direito deste tem o no 11 ao lado direito deste tem o no 12 ao lado direito deste tem o n6 13 ao lado direito deste tem 0 no 14 e ao lado direito deste tem o no 15 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 1830 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento Em seguida mostrase o desenho de uma arvore ideal em que cada no possui dois filhos um filho ou nenhum filho Neste caso para elementos a arvore teria niveis resultando em uma péssima distribuicao O ideal seria que os nos conforme sejam inseridos também sejam rearranjados para manter um equilibrio Assim o ideal seria manter a mesma quantidade de niveis na subarvore da direita e na subarvore da esquerda A questao é como fazer para garantir esse equilibrio A resposta vai estar nas chamadas rotaées Podemos inclusive dividir o problema em duas partes como detectar o desequilibrio e como corrigir o desequilibrio Vamos comegar entendendo como detectar o desequilibrio O equilibrio de uma arvore de busca é medido subtraindo o numero de niveis na subarvore da esquerda do numero de niveis na subarvore da direita Vejamos um exemplo a seguir em que temos uma arvore qualquer e podemos observar cada um dos nés bem como contar quantos niveis existe a esquerda e a direta subtraindo esse numero a7 Tey Desequilibrioé 2 1 propriedade dona ae 0 f o Subarvore desequilibrada Figura 6 Desequilibrio de uma arvore binaria PraCegoVer A figura destaca 0 desequilibrio de uma arvore binaria é uma propriedade do no Para demonstrar esse fato esta sendo mostrado uma arvore em que um no possui altura esquerda com valor 2 e altura direita com valor 2 Sendo assim causando o desequilibrio da subarvore Podese dizer que a arvore esta desequilibrada apenas quando o numero for maior que 1 ou menor que 1 Assim iremos tolerar nimeros de equilibrio de 0 1 e de 1 pois podemos ter um numero impar de nds ou seja em alguns casos ndo conseguiremos fazer a arvore ter um equilibrio completamente nulo Uma vez detectado o desequilibrio na arvore o préximo passo é entender como corrigilo sendo este feito por meio das rotacées httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTPEORTE19unidade4ebookindexhtml 1930 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento ee VOCE QUER LER e Um jogo educacional digital denominado DEG4Trees Digital Educational Game four Trees foi construido para apoiar o ensino de estrutura de arvores binarias de buscas e arvores AVL No jogo é preciso observar as propriedades das estruturas de dados e interagir com elas para atingir os objetivos Para saber mais sugerimos a leitura do artigo DEG4Trees um jogo educacional digital de apoio ao ensino de estruturas de dados de Weider Alves Barbosa Isabella de Freitas Nunes Ana Carolina Gondim Inocéncio Thiago Borges de Oliveira e Paulo Afonso Parreira Junior disponivel em httpswwwresearchgatenetprofileWeiderAlvesBarbosa2 publication2657866 05DEG4TreeUmJogoEducacionalDigitaldeApoioaoEnsinodeEstruturasdeDad oslinks55fc6c1808ae07629e0d3628 pdf eee eeeeeeeeeeeeeeeeeeeee ee eee neers Existem quatro tipos de rotaées sendo dois tipos primitivos e dois compostos de rotades rotacdo a esquerda rotacao a direita rotagdo dupla a esquerda e rotaao dupla a direita Clique no recurso a seguir para conhecer a rotacdo a esquerda e rotaao a direita Rotacdo a esquerda A rotacgdo a esquerda é como o proprio nome sugere Os primeiros nds que estado na subarvore da direita passam para a esquerda fazendo com que o filho da direita se torne a nova raiz Também temos o caso particular em que o filho da direita ja possui o filho da esquerda com todos os elementos da subarvore da direita maiores que a raiz x 1 Rotacao a direita Ja a rotacdo a direita vai funcionar de forma analoga seguindo a mesma légica da rotado a esquerda Nela temos uma diagonal para 0 outro lado ou seja o filho da esquerda vira a nova raiz 2 raiz e o filho da direita de 2 sera o filho da esquerda de 3 Depois 3 se tornara o filho da direita de 2 Veja a figura a seguir para entender melhor httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 2030 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento 1 2 2 1 3 3 a b 1 2 2 1 3 wee Plated 4 army ix 3 an é See d 3 2 2 J me f 3 1 1 r atts 1 a ee i 1 xX fF d e Figura 7 Tipos de rotacdo para arvore AVL PraCegoVer A figura mostra alguns exemplos de rotado em uma arvore AVL No primeiro exemplo temos uma arvore com trés nds cada um deles conectado ao lado direito do outro Os valores dos nés sao 1 2 e 3 respectivamente Logo em seguida é mostrado uma rotaao a esquerda em que o no 2 passou a Ser 0 né6 raiz eo no 1 ficou conectado a sua esquerda e né 3 continuou conectado a sua direita No segundo exemplo mostrase uma arvore com trés nés em que cada né esta conectado ao lado direito do outro no Os valores do nds sAo 1 2 e 3 respectivamente Depois disso mostrase o valor x sendo adicionado no no 2 o que vai obrigar a execucdo de uma rotacdo da arvore Sendo assim apos a rotado 0 nd 2 passoua httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 2130 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento ser o no raiz e do seu lado esquerdo ficou 0 né 1 Do lado direito do nd 1 foi encaixado 0 novo né com o valor x O né 3 continuou ao lado direito do no 2 O terceiro e ultimo exemplo mostra uma arvore com 3 nds em que cada né esta conectado ao lado esquerdo do outro no Os valores dos nés sao 3 2 e 1 respectivamente Depois disso mostrase 0 valor x sendo adicionado no n6 2 o que vai obrigar que aconteca uma rotaao Apds a rotacdo 0 né 2 passou a Ser 0 né raiz o né 1 ficou do seu lado esquerdo e 0 no 3 continuou do seu lado direito O novo né com o valor x ficou conectado ao lado esquerdo do né 3 Vamos tentar compreender agora como funciona a rotacdo dupla a esquerda e a rotacdo dupla a direita que sao rotagdes duplas compostas Considere a seguinte situacdo a rotacdo simples a esquerda nao resolve o desequilibrio Para detectar isto basta olharmos o desequilibrio das subarvores de onde a nova raiz vai vir 3 Temos assim um desequilibrio positivo na raiz original 1 mas na subarvore da direita percebemos um desequilibrio negativo 3 Para corrigir o problema podemos adotar como soludo uma rotacdo a direita na subarvore da direita e em seguida uma rotacdo a esquerda na arvore original A rotacgao dupla a direita vai ser bem similar a rotagado dupla a esquerda conforme vemos na figura na sequéncia httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 2230 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento 1 2 3 XY 1 a Desequilibrio 1 Negativo 3 N 2 2 b a 1 1 2 3 LY 1 3 3 3 e Rotagdo a esquerda na d arvore original c Rotacdo a direita na subarvore da direita 1 1 3 3 2 JL 1 2 2 3 7 f g h Rotacdo 4 esquerda na oo arvore original Rotacao a direita da subarvore da direita Figura 8 Processo da rotacdo dupla a direita e a esquerda respectivamente PraCegoVer A figura mostra trés exemplos de rotado No primeiro exemplo temos uma arvore com um né raiz com valor 1 e ao seu lado direito tem um né com o valor 3 Do lado esquerdo do né 3 tem um né com o valor 2 Ao lado do né 1 tem o numero 2 indicando o httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTPEORTE19unidade4ebookindexhtml 2330 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento valor balanceamento do né e ao né 3 possui 0 valor 1 indicando seu balanceamento Ao lado direito desta arvore tem uma seta apontando para outra arvore que possui 0 n6 3 como né raiz 0 né 1 conectado ao seu lado direito e por fim 0 n6 2 conectado ao lado direito do no 1 No segundo exemplo temos uma arvore com um né6 raiz com valor 1 e ao seu lado direito tem um n6é com o valor 3 Do lado esquerdo do né 3 tem um no com o valor 2 Ao lado direito desta arvore tem uma seta apontando para uma outra arvore que possui 0 nd 1 como né raiz Ao lado direito do né 1 tem um né com o valor 2 e ao lado direito do nd 2 tem um no com o valor 3 Embaixo desta arvore tem um texto escrito Rotacdo a direita na subarvore da direita Ao lado desta segunda arvore tem uma seta apontando para uma terceira arvore a qual contém o né 2 como né raiz Do lado esquerdo do no 2 tem um né com o valor 1 e do lado direito tem um no com o valor 3 Embaixo desta arvore tem um texto com a frase Rotado a esquerda na arvore original No terceiro exemplo temos uma arvore com um né raiz com valor 1 e ao seu lado direito tem um né com o valor 3 Do lado esquerdo do né 3 tem um no com o valor 2 Ao lado direito desta arvore tem uma seta apontando para uma outra arvore que possui 0 nd 1 como no raiz Ao lado direito deste nd tem um né com o valor 2 e ao lado esquerdo desse né tem um n6 com o valor 3 Embaixo desta arvore tem um texto escrito Rotacdo a direita da subarvore da direita Ao lado direito dessa arvore tem uma seta apontando para uma outra arvore com 3 nds O né raiz tem o valor 3 ao lado esquerdo tem um no com valor 1 e ao lado direito tem um no com valor 2 Agora que ja conhecemos a rotacdo dupla a esquerda e a rotado dupla a direita como decidir qual delas devemos usar Para tanto precisamos seguir um passo a passo Clique nos cones a seguir Calcular o fator de equilibrio Q R L em que R o numero de niveis a direita e L é o numero de niveis a esquerda Se 1Q1a arvore é equilibrada Se Q 1 temos duas opoes se a subarvore da direita tem Q 0 entdo a rotacao seria dupla a esquerda mas do contrario seria rotagao a esquerda se a subarvore da direita tem Q 0 entao a rotacdo seria dupla a direita mas do contrario seria rotacao a direita httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 2430 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento a VAMOS PRATICAR e Uma vez detectado o desequilibrio na arvore 0 préximo passo é entend corrigilo Use 0 processo da rotagdo dupla para corrigir o desequilibrio d a seguir 2 4 3 PraCegoVer A figura mostra a representacdo de uma arvore com 3 nos O né raiz possui 0 valor 2 Ao lado direito do no 2 esta conectado o n6é com o valor 4 Ao lado esquerdo do no 4 esta conectado o né com o valor 3 Como ja conhecemos a respeito da arvore AVL vamos no proximo item estudar a respeito das arvores B e B Vejamos 432 Arvores B e B As arvores B sao uma forma de arvore de pesquisa equilibrada baseada em arvores gerais Um no da arvore B pode conter varios elementos em vez de apenas um como nas arvores de pesquisa binaria Isto é em vez de ter apenas dois filhos ela pode ter varios httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 2530 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento De acordo com Viana Cintra e Nobre 2015 as arvores B sao especialmente Uteis para estruturas de pesquisa armazenadas em discos Estes tém caracteristicas de recuperacdo diferentes da memoria interna RAM e obviamente seu acesso é muito mais lento Na maioria das arvores de pesquisas como a AVL supG6ese que tudo esteja na memoria principal Contudo para entender o uso das arvores B devemos pensar na quantidade de dados que nado cabe na memoria principal Quando o numero de chaves é alto os dados sao lidos do disco na forma de blocos A ideia principal do uso de arvores B é reduzir o numero de acessos ao disco Temos assim que as arvores B sao uma boa combinaao para armazenamento e pesquisa em disco pois é possivel escolher o tamanho do no para corresponder ao tamanho do cilindro Ao fazer isto armazenaremos muitos membros de dados em cada nd tornando a arvore mais plana para que sejam necessarias menos transigdes VIANA CINTRA NOBRE 2015 Uma estrutura de arvore B é balanceada automaticamente e geralmente permite que um no tenha mais de dois filhos para manter a arvore larga e portanto crescer em altura com varias chaves inseridas em um no Normalmente definimos uma arvore B com ordem b em que b é 0 numero minimo de filhos e 2b é 0 numero maximo de filhos que qualquer no pode ter A seguir temos um exemplo de uma arvore B com b 2 8 21 34 8 21 34 14 23 31 45 Figura 9 Exemplo de arvore B PraCegoVer A figura mostra uma representacado de uma arvore B No topo da imagem temos um vetor de 3 posicdes com os seguintes valores 8 21 e 34 Tem 4 setas saindo deste vetor Cada seta aponta para um vetor diferente A primeira seta aponta para um vetor com os valores 8 21 34 A segunda seta aponta para um vetor com os valores 14 A terceira seta aponta para um vetor com 0 valor 23 31 Por fim a ultima seta aponta para um vetor com o valor 45 Na arvore da figura anterior podemos perceber que cada numero inteiro é considerado uma chave separada ou seja cada um teria seu proprio nd Assim como em outras arvores todas as chaves na subarvore a esquerda sdo menores que a chave atual bem como todas as chaves na subarvore a direita s4o maiores Por exemplo comecando na chave 8 as chaves 3 4 e 7 sdo menores enquanto a chave 14 é maior Observe também que como o nimero maximo de filhos é 2 2 4 um n6 pode armazenar apenas trés chaves pois os indicadores para filhos sao armazenados entre as chaves e nas bordas Para implementar a indexacao dindamica em varios niveis geralmente sao utilizadas as arvores B e B A desvantagem da arvore B usada para indexaao é que ela armazena 0 ponteiro de dados ponteiro para o bloco de arquivos do disco que contém o valor da chave correspondente a um valor de chave especifico juntamente com o valor de chave no no de um B Esta técnica reduz bastante o numero de entradas que podem ser empacotadas em um né de uma arvore B contribuindo para o aumento do nimero de niveis e do tempo de pesquisa de um registro httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 2630 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento A arvore B elimina essa desvantagem armazenando ponteiros de dados apenas nos nds das folhas da arvore Assim a estrutura é bem diferente da dos nos internos da arvore B Vejamos algumas propriedades das arvores B e B Clique nos icones a seguir Todas as folhas estado no mesmo nivel Uma arvore B é definida pelo termo grau minimo t sendo que seu valor depende do tamanho do bloco de disco Todo no exceto a raiz deve conter pelo menos chaves t 1 A raiz pode conter no minimo uma chave Todos os nos incluindo raiz podem conter no maximo 2t 1 chaves O numero de filhos de um no é igual ao numero de chaves mais 1 Todas as chaves de um no sao classificadas em ordem crescente O filho entre duas chaves k1 e k2 contém todas as chaves no intervalo de k1 e k2 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 2730 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento A arvore B cresce e diminui a partir da raiz diferente da arvore de pesquisa binaria Todo no do tipo folha possui a mesma profundidade entre eles e o no da raiz Como outras arvores de pesquisa binaria equilibradas a complexidade do tempo para pesquisar inserir e excluir é OLog n Cada no esta 50 cheio com excecdo o no da raiz Na figura a seguir podemos observar um exemplo de arvore B 23 31 a 8 21 26 34 2 4 8 ll 21 23 26 28 31 34 37 Figura 10 Arvore B PraCegoVer A figura mostra uma representacdo de uma arvore B Primeiramente é mostrado um vetor com os valores 2331 Existem trés seta saindo desse vetor Uma das setas aponta para um vetor com os valores 8 21 A segunda seta aponta para um vetor com o valor 23 e a terceira seta aponta para um vetor com o valor 34 O vetor com os valores 8 21 também possui 3 setas apontando para outros 3 vetores A primeira seta aponta para um vetor com o valor 2 4 A segunda seta aponta para um vetor com os valores 811 e a terceira seta aponta para um vetor com o valor 21 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 2830 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento O vetor com o valor 26 possui duas setas aponta para outros dois vetores A primeira sera aponta para um vetor com valor 23 e a segunda seta aponta para um vetor com 0 valor 26 28 O vetor com valor 34 possui 2 apontando para outros dois vetores A primeira seta esta apontando para um vetor com 0 valo 31 e a segunda seta esta apontando para um vetor com os valores 34 e 37 Dessa forma a arvore B é muito semelhante a arvore B As duas se equilibram automaticamente e possuem operacoées logaritmicas de inserdo localizacao e exclusdo Uma arvore B pode ser vista como uma arvore B em que cada no contém apenas chaves nado pares de chave valor e um nivel adicional é inserido na parte inferior com folhas vinculadas Sintese Chegamos ao fim de mais uma unidade de estudos Aqui pudemos compreender as técnicas de pesquisa sequencial e binaria em que foi possivel aprender os conceitos e a aplicabilidade de tabelas de dispersao Também pudemos conhecer as principais arvores de buscas e suas complexidades Nesta unidade vocé teve a oportunidade de conhecer as técnicas de pesquisas sequencial e binaria entender sobre as tabelas de dispersao compreender a respeito das arvores de buscas balanceadas e identificar as tecnicas de manutengao das arvores de pesquisas e verificar a complexidade dos algoritmos de pesquisa Clique para baixar o contetido deste tema Bibliografia BARBOSA W A et al DEG4Trees um jogo educacional digital de apoio ao ensino de estruturas de dados Goias Universidade Federal de Goias 2015 Disponivel em httpswwwresearchgatenetprofileWeiderAlvesBarbosa2publication265786605DEG4TreeUmJogo EducacionalDigitaldeApoioaoEnsinodeEstruturasdeDados links httpswwwresearchgatenetprofileWeiderAlvesBarbosa2publication265786605DEG4TreeUmJogo EducacionalDigitaldeApoioaoEnsinodeEstruturasdeDadoslinks55fc6c1808ae07629e0d3628 pdf httpswwwresearchgatenetprofileWeiderAlvesBarbosa2publication265786605DEG4TreeUmJogo EducacionalDigitaldeApoioaoEnsinodeEstruturasdeDadoslinks 55fc6c1808ae07629e0d3628pdf Acesso em 11 out 2019 VIANA G V R CINTRA G F NOBRE R H Pesquisa e ordenacao de dados 2 ed Ceara EdeuECE 2015 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 2930 21082023 1628 Pesquisa Ordenação e Técnicas de Armazenamento httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade4ebookindexhtml 3030