Estruturas de Dados - Material de Revisão

o meu cavalo não seja bem vindo a nossa aula de revisão antes de começar o conteúdo propriamente dito eu gostaria de apresentar para você um lembrete de como nós executamos código em ser mais mais então aqui eu tenho código da aula 8 provavelmente um código que você já analisou e aqui nesse código da aula 8 eu tenho dois arquivos. H e dois arquivos pontos CPP na hora de compilar o código utilizando o comando gemas mais você vai apresentar para ele apenas os arquivos pontos CPP como estética alinhamento quando CPP e step cadeado. CPP aí depois

de clicar em entrar se ela gerado este arquivo a ponto alto que é o arquivo executável e para executar esse executável você colocar a ponto/a ponto alto e ele vai iniciar a execução do e vamos agora voltar para o nosso conteúdo programado para aula de hoje na hora de hoje eu pretendo apresentar para vocês um pouco sobre listas lineares pilhas e filas tabelas Hertz árvore binária de busca e árvores avl não vai dar para dar muitos detalhes de todos eles mas dá para lembrar o que que acontece com cada um começando com listas lineares que

são aquelas estruturas em que cada elemento de tempo um predecessor e um sucessor com exceção do primeiro elemento que não tem para defensor e do último elemento que não tem sucessor uma lista desenhar pela canonicamente pode ser implementada internamente utilizando vetores ou utilizando ponteiros no caso dos vetores nós podemos gerar isso que chamamos de lista sequencial em que a ordem lógica é igual a ordem física com ponteiros nós podemos gerar uma lista encadeada em que a ordem lógica vai ser no meio dos Ponteiros é uma lista sequencial como nós temos aqui na o primeiro elemento

ele vai estar fisicamente do lado do segundo elemento o segundo elemento vai estar fisicamente do lado do terceiro elemento e assim por diante coisa que não acontece com a lista encadeada em que o primeiro elemento ele pode estar numa região de memória muito diferente do segundo elemento que por sua vez pode estar numa posição de memória muito diferente da posição de memória do terceiro elemento então nós conseguimos implementar as listas lineares tanto com vetores e ponteiros e interessante saber as vantagens e desvantagens de cada uma dessas implementações numa lista sequencial a vantagem aqui dado o

índice do elemento por exemplo estou colocando os índices aqui por exemplo sabendo que queremos o elemento de índice três mas podemos acessar o registro que é o número 19 em tempo constante coisa que não acontece com uma lista encadeada em que você vai ter que começar a busca pelo primeiro e depois ir seguindo e no elemento de índice três Uma Outra vantagem da lista sequencial que na verdade é o resultado desse poder de acesso em tempo constantes é que nós podemos utilizar listas sequenciais se houver alguma outra restrição por exemplo A Rê está ordenado nós

podemos utilizar esses vetores para fazer busca binária que aquela busca entre nós podíamos primeiro para o elemento do meio e Dada a comparação entre esse elemento que está no meio e a chave de busca mas sabemos que devemos procurar ou no início do vetor ou na parte final do vetor a lista encadeada Ela também tem vantagens a primeira dessas vantagens a que nós não precisamos alocar Todo o espaço de memória antes de inserir os elementos nós vamos alocando enquanto os elementos são inseridos por exemplo se quisermos adicionar o elemento 50 basta adicionar uma posição de

memória para elemento 50 e depois colocar um ponteiro na direção dele a partir do elemento 33 é uma Outra vantagem de uma lista encadeada é que é muito mais fácil garantir a ordem lógica por exemplo se eu quero remover um elemento 10 basta deslocar essa memória e fazendo um elemento uma contar para elemento 15 coisa que eu não poderia fazer por exemplo nessa desse vetor entre para remover o elemento 10 eu teria provavelmente que fazer um deslocamento desses outros elementos para não deixar um buraco aqui no meu vetor ordenado Vamos falar agora sobre pilhas AA

pilha aquela estrutura de dados em que o primeiro elemento a entrar tem que ser um último elemento a sair aqui nós temos a mesma pilha tensão de uma maneira lógica representada como uma lista encadeada e representada aqui embaixo como vetor o que você deve saber é que nessa lista encadeada por exemplo o telamento que está sendo que está no topo ele apontado por esse ponteiro aqui que é o ponteiro redes quando você removeu o topo então 32 queira sair é um head apontará para o elemento 25 Então você tem que saber exatamente o que que

esse gráfico aqui significa E você tem que saber o que que acontece com esse gráfico aqui após uma infecção e uma remoção no caso do vetor aqui embaixo nós temos um índice aqui um inteiro apontando para o elemento número 4 digamos nessa implementação e isso aqui indica que eu 32 é o topo da pilha se você quiser inserir um novo elemento Basta fazer esse índice aqui apontar para o novo é prolongamento número 5 e colocar o elemento aqui que você quer inserir é bom não confundir porque muita gente confunde os alunos confundem achando que o

elemento que está no topo da pilha um elemento 0 isso não é verdade elemento que está no topo da pilha é o elemento mais à direita nessa nossa implementação Vista em sala de aula vamos falar um pouco agora sobre filas em fila o primeiro elemento a entrar é o primeiro a sair isso dá uma ideia aí de Justiça aquele que Quem foi o primeiro a ser atendido uma característica da fila é que a inserção EA remoção ela vai ocorrer em Pontos diferentes nessa estrutura de dados diferente trago que acontecer a cópia em que todas as

operações ocorreram no clube então aqui na nossa implementação Nós temos dois ponteiros nessa nossa implementação em lista encadeada um para aprontar para frente e um para apontar para trás da pilha esse que aponta para frente ele indica para gente tem é o próximo alimento que vai ser removido por exemplo o elemento 11 é o próximo a ser removido e esse elemento aqui que está apontando para trás da fila ele indica em que posição um novo elemento será inserido nós temos que notar que essas três dessas três filas aqui ela de maneira lógica só a mesma

estrutura porque porque aqui nós temos o elemento 11 na frente também aqui nós temos um elemento 11 e Aqui nós temos o elemento 11 na frente estou aqui colocando para vocês o índice que aponta para quem está na frente depois do 11 nós temos os 51 e depois eu 51 nós temos o 44 e aqui ou 44 nessa última apresentação vocês devem notar que ele veio para o início do vetor porque porque nós imaginamos esse vetor com uma estrutura circula chegou no segundo final do vetor e de volta para o início do vetor e daí

nós temos os elementos de 25 na sequência e os elementos 32 eles são aqueles que estão atrás nas filas aqui e como falar um pouco sobre tabela hash nessa tabela rest vamos assumir que nós queremos colocar dentro da tabela registros de pessoas então aqui eu tenho essa pessoa que a Daniele ela tem esse CPF e ela tem essa idade e Aqui nós temos essa outra pessoa que é o Marcelo ele tem esse CPF e ele tem essa idade aqui vamos supor que nós queremos adicionar esses elementos na tabela rest E nós queremos depois fazer as

buscas e se ações e remoções utilizando como informação o CPF Então vai ser o CPF a nossa chave de busca uma coisa que nós podemos imaginar é se nós tivéssemos um vetor gigantes com espaço suficiente para colocar todas as chaves possíveis Ou seja todos os CPF possíveis esse vetor ele teria que ter tamanho de 10 elevado a 9 porque porque no CPF ele tem 11 números entretanto dois desses números os números de validação então basicamente são os nove primeiros números que contam então se eu tivesse um vetor gigante de tamanho 10 elevado a 9 eu

poderia inserir todos os seres o registro naquela posição indicada pelo CPF e não haveria colisão por quê Porque não existem duas pessoas com o mesmo CPF Então seria uma tabela rest em que eu poderia ir seria remover e atualizar os registros em tempo constantes entretanto isso é impossível de garantir no mundo real a gente não tem um vetor com todo esse tamanho aqui Então nesse caso que que nós fazemos nós utilizamos vetores menores normalmente o alfabeto das chaves costuma ser muito maior de uma cardinalidade muito maior do que realmente o vetor que a gente coloca

e daí vai gerar o que nós chamamos de colisão ou seja duas Chaves indo para a mesma posição dentro do retorno O que é possível vetor aqui tivesse tamanhos em ou seja ele fosse de 0 até 99 eu poderia utilizar o resto da divisão do CPF para colocar um registro dentro do vetor entretanto como os dois CPF daqui terminam com 28 haveria uma colisão por quê Porque o resto da divisão desse número termina com 28 por 100 é 28 e desse daqui também então Eles teriam bater ados para mesma posição que haveria uma colisão aqui

e Existem várias formas de tratar de tratar com horizontes nós podemos tratar a colisão com o espaço adicional ou nós podemos tratar a colisão utilizando o próprio vetor nesse caso seria chamado de interesse tamento aberto uma coisa que você deve saber é que nós não precisamos só nós não precisamos necessariamente utilizar inteiros como vetores nós podemos utilizar por exemplo Strings como vetores na nossa implementação Vista em sala de aula tem que nós fizemos deveria haver uma função que mapear ia a stringhi em um número inteiro e depois esse número inteiro ele seria transformado para caber

dentro de um vetor de tamanho n então por exemplo você pode imaginar várias funções uma que dá números inteiros para cada caracter depois soma e computa o resto pelo tamanho do vetor isso é bem possível de qualquer forma uma coisa que tem que se preocupar é que as funções desses pagamentos que são e elas devem Diminuir a quantidade de condições mas tem possível garantir que a colisões não existiram Entretanto a função de pagamento ela tem que fazer pelo menos uma distribuição uniforme bom e depois as condições Claro elas vão existir elas devem ser tratadas de

alguma forma ou com espaço adicional ou com o endereçamento aberto e se tudo der certo nós teremos operações de inserção remoção e atualização em tempo constante no caso médio que justamente isso que a gente queria operações em tempo eficiente e e vamos falar aqui um pouco sobre a árvore binária de busca principalmente o caminhamento em pré-ordem pós-ordem em ordem que foi o que deu as maiores dúvidas aí do que eu fui acompanhando bom então vamos ver as árvores binárias de buscas são aquelas Árvores em binárias tá em que o conteúdo dos dos elementos ele importa

na hora de colocar um elemento na árvore porque porque dado um nó todos os elementos de conteúdo menor do que esse nó deve ficar do lado esquerdo e os elementos com conteúdo maior devem ficar do lado direito então para buscar um elemento nós só olhamos para o conteúdo e dependendo do do elemento que estamos buscando nós sabemos se devemos ir para a direita ou para esquerda na hora de inserir nós adicionamos um elemento na posição onde ele estaria se fosse buscado Isso quer dizer então que novo ela meta vai ser sempre uma folha e as

emoções ela leva em conta o número de filhos do nosso ser removido porque se queremos remover por exemplo um Nokia folha não tem filho basta deslocar a região de memória dele se queremos remover um nó por exemplo vamos tirar o elemento 30 e depois de tirar um elemento 30 eu quero é então que vai ter apenas um filho já que o 30 já saiu aonde será o 26 o que que eu tenho que fazer tenho que dizer local memória e reajustar esse ponteiro Ou seja eu coloco o filho dele no lugar dele se eu quero

remover unlock tem dois filhos por exemplo 20 pelo algoritmo Que Nós aprendemos em sala de aula nós iremos substituir ele pelo sucessor lógico quem é o sucessor Lógico é o elemento mais à esquerda da folha direito essa é a subir a árvore da direita e o elemento mais à esquerda da sub-árvore da direita é um elemento 25 então nós tiraremos o 20 daqui e colocaríamos o 25 no lugar dele removendo posteriormente o 25 dessa posição uma coisa que você precisa saber em árvores binárias de busca são os percursos existem basicamente ou melhor de maneira canônica

três percursos que são percurso em pré-ordem pós-ordem e em ordem sempre o percurso ele vai começar dono Raiz e e o percurso em pré-ordem vai ser aquele percurso em que foram chegar num determinado nó Nós visitamos aquele nó depois visitamos a árvore da esquerda E depois da árvore da direita Então vamos assumir que nós vamos visitar essa árvore aqui como um todo vamos começar do elemento 20 como estamos em pré-ordem Nós visitamos o elemento 20 tu colocou elemento 20 aqui depois sigo para esquerda quando chego na esquerda Agora eu tenho que olhar para essa árvore

aqui e eu visito alimento 18 e sigo para a esquerda ao seguir para a esquerda eu chego nessa árvore visita o alimento 7 depois de visitar o elemento sete eu volto por 18 aqui e aqui no 18 como eu já Visitei tanto na conta esquerda tenho que visitar a direita aparecendo 19 aqui daí eu volto para essa árvore roteada no 20 como eu já Visitei a esquerda e o nó eu vou para o lado direito visitando agora o 58 na verdade visitando toda essa árvore o resultado 58 e assim por diante Esse é o caminhamento

em pré-ordem o caminhamento em pós-ordem ele faz o contrário eu chego numa determinada árvore por exemplo a árvore como um todo aqui no nosso raiz Eu não visito esse nó raiz eu vou para o lado eu vou primeiro para árvore da esquerda Então agora eu olho para essa árvore aqui o Tiago no 18 Como é pós-ordem Eu não visito ainda é sinnott eu vou para a árvore da esquerda e visita o nosso site depois de visitar o nos ex eu volto aqui para o nosso 18 já coloquei 17 aqui e daí eu não visito aí

no nós 18 por quê porque após ordem visita o nosso depois de visitar a esquerda EA direita e daí eu visito o 19 então depois de visitar o 19 eu sei eu já Visitei a minha árvore da esquerda já Visitei a minha árvore da direita daqui 19 tá já Visitei a minha árvore da esquerda já Visitei a minha vida à direita aí e eu visito o 18 e depois de visitar esse 18 eu volto aqui para essa árvore maior tá roteada no vídeo entra tanta não visito 20 por quê Porque Um percurso em pó só

ontem eu visito a esquerda depois à direita então eu sigo para essa árvore aqui chegando nessa árvore Eu não visito 58 por quê Porque eu tenho que visitar a árvore da esquerda curte A Dalu 26 daí eu não visito 26 por quê Porque eu tenho que chegar no 25 como 25 iPhone eu sei que eu já posso visitar o 25 e depois eu volto por 26 como é pós-ordem tenho que visitar a direita antes de visitar o nó então eu visito 30 antes de visitar o 26 como eu já Visitei a esquerda EA direita agora

eu posso visitar o 26 aqui eu volto e depois por 58 como não tem ninguém do lado direito e tem eu posso visitar o 58 e daí eu volto para o 20 como eu Visitei já afabilidade esquerda EA árvore da direita que eu já posso visitar o 20 e no em ordem eu começo de novo com essa árvore aqui olhando para o nó raiz como eu tenho que visitar minha ordem a esquerda antes de visitar o nó então eu moro aqui para essa árvore da escrita e olha agora aparelhamento 18 como ele tem filho a

esquerda até o 7 então eu sei que eu tenho que visitar o set antes e o 7 é foi então coloca ele já que ele foi visitado depois eu volto para o 18 e como a gente está no percurso em ordem eu visito o 18 já que eu tenho que visitar a esquerda depois do nó e depois à direita então Visitei os apps depois do 18 que é o Nó e depois eu sigo para validar direita que aqui um 19 daí eu já Visitei essa árvore completamente como eu já Visitei essa árvore completamente eu volto

para o rins e aqui no 20 ao Senhor eu já Visitei a subir a rampa e da esquerda então eu já posso visitar o 20 já que no percurso em ordem uma visita à esquerda E depois o Nó e daí eu sirvo para Lavras Oi e a árvore da direita tem esse noc esse essa árvore aqui essa subiado eu olho para os 58 mas como 58 tem uma árvore a esquerda dele Eu não visito 58 eu visito essa árvore aqui e daí eu olho por 26 mas como 26 tem um nó a esquerda que é

o 25 eu sei que eu não visito 26 ainda visita o primeiro 25 e daí sim eu visito 26 por já ter visitado a árvore esquerda dele visitado 26 eu já posso visitar árvore direita dele que é o 30 e depois de visitar o 30 eu posso voltar e visitar e o 58 por quê Porque eu já vou ter visitado a vida às quintas dele você tem que saber fazer esses caminhamentos assim de maneira natural e discussão tão complicados mas talvez demore um pouco para você pegar o ritmo o que é que eu vou falar

um pouco sobre árvore avl são as árvores que garantem o balanceamento o que você tem que se preocupar com a obra sabe ergue é saber quais operações fazer você vai fazer uma operação quando houver um novo desbalanceado então aqui eu estou computando fator de balanceamento dos nós e quando tiver um fator de balanceamento menos dois ou mais dois você sabe que uma rotação é necessária nesse caso eu tenho um fator de balanceamento menos dois e o filho dele é o fator de balanceamento menos um então eu sei que eu tenho que fazer uma rotação a

direita bem aqui essa rotação direita vai fazer com que o 15 fique nessa posição o 17 seu filho da direita do 15 vai virar o filho à esquerda do 25 e depois da votação existem outras regras aqui por exemplo a regra da rotação simples à esquerda você vai ter um fator de balanceamento mais duas no nosso balanceado e o filho mais alto dele vai ter um fator que falou é mais um para saber se é simples você só vai ver se é o mesmo sinal por exemplo menos dois e o menos um à esquerda ou

mais dois com mais um a direita e o procedimento assimila você rotaciona nesse não mais dois e o 15 vai virar o pai do teste esse 13 teu filho à esquerda do 15 vai virar o fio e se vai virar o filho a direita do 10 ele vai ser ligado aqui e o 10 vai ser ligado por sua vez no 15 que seria essa aresta aqui as rotações duplas você vai fazer para seguinte opte você vai ter um novo fator de balanceamento menos dois pai de um lóculo para todos balanceamento mais um é um dos

casos Então você vai fazer uma rotação a esquerda nesse mais um que vai gerar essa configuração que é muito parecida com essa configuração que a gente já viu aqui então a regra será aplicada é a mesmo E no caso de termos um fator de balanceamento mais dois pais um fator de balanceamento menos um você vai fazer uma rotação à esquerda e num pra gerar essa configuração aqui e essa configuração é semelhante a essa configuração daqui então a regra parece é isso que eu tinha para colocar aqui nesse material de revisão espero ter conseguido cobrir aquilo

que vocês tinham mais dúvida dentro do material e agora é só assistir esse material várias vezes se você não tiver entendido de primeira e usar ele como guia para assistir às aulas novamente um forte abraço e qualquer dúvida pode postar no fórum ou tentar entrar em contato com os facilitadores que eles me passam as dúvidas de vocês até mais é