Estruturas de Dados - Árvores (Continuação)

E aí [Música] os carros algumas na hora de hoje nós vamos retomar os nossos estudos de árvore binária de busca implementação em ser mais na aula de hoje nós vamos seguir este roteiro primeiramente duas começar com alguns detalhes de implementação onde eu falarei especificamente sobre a remoção de um nó da árvore e depois eu vou ensinar como a gente utiliza essa classe Que Nós criamos nessas duas últimas aulas Bom primeiramente sobre detalhes de implementação a primeira coisa que nós devemos lembrar aqui e aqui esta aula de hoje na verdade ela é a segunda aula de

um bloco de duas aulas hoje na primeira aula eu já falei sobre a estrutura de um nó já falei sobre a estrutura do tipo abstrato de dados os métodos que vamos implementar já falei também sobre o método de busca e também já falei sobre o método de inserção agora que que eu vou fazer é falar sobre o método de remoção de um nó ou aborista de remoção de um nó eu dividir em duas funções primeiramente delícia aluno e depois o de leite node no deles aluno que a gente vai fazer o deles aluno vai ser

um método que vai navegar pela Árvore até encontrar o nosso ter excluído usuário que quer remover um novo é passar apenas a chave O que é um valor inteiro e daí eu tenho que procurar o primeiramente o nó da árvore e achando esse nó da árvore eu invoco ter each node que é quem vai realmente fazer essa remoção o pão de leite noite é um método que receberá por parâmetro o nó a ser excluído tá basicamente a raiz do nó nós temos por ele vai ser o nó a raiz quando ele passar por de leite

e tratar a três casos No primeiro caso nós vamos verificar se a ser excluído é uma folha no segundo caso nós iremos verificar se o nó tem exatamente um filho e não quer ser o caso nós vamos verificar se o nó tem dois filhos nesse último caso a implementação Que Nós faremos vai ser os seguintes se o nosso tem dois filhos nós vamos substituir o conteúdo pelo conteúdo do sucessor lógico isso só para relembrar o Que Nós aprendemos na aula teórica na aula teórica eu falei que haviam duas opções ou a gente usava sucessor lógico

ou predecessor lógico no nosso caso aqui nós vamos usar o sucessor lógico nesta implementação e vamos falar primeiramente sobre o método de Elite aluno que é o método que vai fazer a busca pelo nosso nós queremos de mover no de Elite aluno nós já sabemos por parâmetro a chave que queremos remover Então existe assim int aluno aqui e nós Também passamos por parâmetro a árvore um de pode estar esse elemento que nós queremos envolver então a busca vai ser feita dentro dessa árvore aqui nós primeiramente que essa árvore ela é um ponteiro mas o ponteiro

está sendo passado por referência por conta desse e Comercial aqui por quê Porque a gente vai utilizar uma ideia um pouco semelhante com aquela que nós utilizamos no insert aluno qual era a ideia do instante alumínio vamos supor que aqui eu já cheguei no 25 e eu quero e eu quero inserir o 23 e esse 25 aqui já aponta para tudo Tá se eu quero exterior 23 então na última chamada recursiva eu vou e daqui é nulo tá na última chamada recursiva eu encontrava nulo aqui e eu dizia olha como é nulo eu sei que

eu tenho que a procurar uma região de memória em algum lugar e colocar o 23 eu fazia isso entre a tanto assim né que fazer com que o 23 ficasse ligado na árvore se eu tivesse passado esse último ponteiro da última chamada recursiva como vapor valor eu não conseguiria colocar esse 23 na árvore Mas como eu passei por referência Então eu peguei o parâmetro e veio por referência e fiz ele apontar por 23 como era por referência tudo que eu fiz com parâmetros sejam mudei um local para gente apontar ele apontava para no agora que

aponta para uma região de memória como ele era o referência isso ele surta efeito também no nosso já estava na árvore que era o ponteiro Esquerda do 95 diz que já estava na água então ao fazer isso nessa função eu consegui e na memória e colocar na árvore bom então para fazer as coisas com uma ideia bem parecida aqui Eu também passo esse ponteiro para a árvore como referência isso vou você vai entender já já quando eu apresentar o código mas vamos primeiro para o deles aluno no de leite alonga o que que eu faço

se o aluno que eu quero remover tiver uma chave menor do que a chave que está na raiz dessa árvore aqui então eu sei que eu tenho que na verdade é procurar na subir árvore da esquerda se ele tem uma chave maior do que essa chave que é o nó raiz então eu sei que eu tenho que procurar na subir árvore da direita e essa árvore ou o novo aí dele me dar essa indicação se eu encontrei aluno é igual a atriz aluno.net série A ou seja esse inteiro aqui ele tem um r a igual

ao aluno que é a raiz da árvore entrou sei que eu tenho que invocar imediatamente hotelite Note que vai fazer a deslocação dessa região de memória e vai reestruturar o seminário discute então agora nós vamos ver o método de Elite node é e no método de leite noite eu tenho que tratar basicamente três casos quando não tem nenhum filho quando tem apenas um filho e quando tem dois filhos nesses códigos aqui eu estou estou tratando o primeiro segundo caso vamos anotar esse caso aqui eu tenho um determinado Nokia Eu quero remover e esse esse nó

ele pode ter nulo um filho e ou ele pode ter no outro filho vamos tentar primeiro esse caso aqui vamos olhar o código esse aluno data eu não vou falar ainda dele porque ele vai ser usado no caso três que que eu vou precisar nesses casos um idoso Primeiramente um ponteiro temporário porque é um ponteiro temporário porque eu vou substituir esse nó por exemplo por um nosso vídeo E aí depois de substituir esse nó pelo nosso filho eu vou ter que deslocar essa região de memória Então esse ponteiro temporário ele vai ficar apontando para região

de memória onde posteriormente eu irei this E aí e vamos ver esse primeiro esse aqui nesse primeiro e se eu verifico se nutre a esquerda = nulo seria ou esse caso aqui ou caso entre os dois filhos são lindos vamos pensar nesse caso primeiramente se o tri esquerda é nulo eu simplesmente pego o nosso filho e substitui ele inteiramente no lugar do meu pai isso é suficiente porque porque isso seria o caso dois e depois eu diz a Locke esse nome só que você deve pensar tá macio caso um no caso um eu teria esse

nós contando para nulo e também apontando para nulo isso também funcionaria porque porque eu só preciso desalocar esse nós aquele tem telefone então o que que essa linha de código está fazendo na verdade é obtendo s nulo aqui e colocando esse número aqui no lugar do meu pai o que é a mesma coisa de deslocar Então essa linha de código aqui ela trata tanto cá o quanto um dos itens do caso 2 e ao final Claro a gente desaloca a memória depois de fazer essa substituição aqui de ponteiros a gente desde a Ok essa região

de memória para não aver vasamento e supondo que a gente tem um nó e esse nós tem um filho a esquerda se ele tem um filho a esquerda e não tem um filho a direita Isso quer dizer o que que ele só tem um único filho o que que eu preciso fazer eu simplesmente vou pegar esse note está bem aqui substituir ele no lugar do pai pra colocar ele no lugar do pai e depois desalocar essa região de memória no interior do pai é justamente isso que eu estou fazendo aqui eu estou dizendo three é

igual a true esquerda E depois eu estou dizendo tempo de lítio tempo e PT E lembrando que o tempo é PT é alguém que está apontando para o nó raiz justamente para não perder esse ponteiro para poder deslocar essa região de memória então isso daqui trata o caso um e o caso dois e daí você deve se perguntar o É mas isso funciona isso altera realmente a estrutura da árvore eu vou dizer sim isso Altera a estrutura da árvore porque porque 3 Esse é um ponteiro que foi passado por referência tudo o que eu faço

nesse ponteiro aqui no seguinte sentido fazer porque esse conteúdo aponte para o outro lugar vai surtir efeito fora desse método então quando eu digo three igual atriz direita e o ponteiro foi passado por referência por causa desse e Comercial aqui então eu sei que essa alteração que eu fiz aqui ela também vai ocorrer fora do dele de noite então é chave entender porque eu fiz essa passagem de parâmetro aqui por referência então garanto que vocês estão me acompanhando nesse nesse sentido e agora vamos tentar verificar a próxima parte do nó a próxima parte do método

de remoção do algoritmo de remoção na próxima parte eu vou precisar do sucessor lógico porque porque é o caso entre um determinado nosso tem dois filhos para obter o sucessor Lógico eu falei para vocês na aula teórica eu procuro na unidade direita quem é o elemento mais acho que então supondo que esse é o loc Eu quero remover ele tem a árvore a direita eu quero sucessor lógico então eu vou para a árvore da direita então percorro snor e daí eu sigo direto pela esquerda até não poder mais então eu vou em todas as esquerdas

até encontrar um Lulu se eu encontrei um nulo significa que esse noc antes do nulo é o sucessor lógico Vamos ver isso dentro do pódio o código que recebe o sucessor primeiramente ele recebeu o trem que é o norte será removido segundo o que que ele vai fazer ele vai navegar para aferir da direita e depois e para abrir a direita ele vai percorrer para a esquerda até não poder mais então esse uai ela que está dizendo Enquanto houver filho na esquerda vá para esquerda até não poder mais se ele sair desse laço significa Olha

eu cheguei no nó uso os filhos da esquerda é nulo essa Justamente a definição do meu sucessor lógico e o que que eu faço aqui eu gravo o conteúdo é desse nó que é o sucessor lógico nessa variável deita eu não posso nenhuma mudança de ponteiro aqui eu simplesmente grava conteúdo do sucessor lógico daqui você vai se perguntar agora mas eu tô gravando realmente o conteúdo vou dizer assim você está gravando o conteúdo porque porque se deita aqui é uma variável que veio por referência Então essa modificação que você está fazendo dizendo texto é igual

aluno 3 aluno ou seja o conteúdo dele conteúdo desse desse nó Então isso que você está fazendo aqui vai aparecer também fora da função por conta da passagem de parâmetro pro referência bom então vamos ver fora desse método como esse Jet sucessor é usar esse gato sensor é usado da seguinte forma three é o nosso nós queremos remover então quando eu dou Guedes sucessor three eu consigo obter o conteúdo do noc vai substituir o true então É como se eu tivesse dizendo esse aqui é o tri eu pedi o sucessor e ele achou sucessor 25

e me devolveu um conteúdo que seria um 25 e o que é que eu faço substituto conteúdo que é o 25 aqui no nosso eu vou remover então ele vai ficar nessa forma que vai ter 25 em dois lugares tanto Num Lock no de agora. Nesse Nokia quero ser sua lógico o tanto nutre quanto no sucessor isso não pode qual dos dois atendo que remover eu tenho que remover esse daqui tá então o que é que eu faço para remover esse daqui eu e volto de Elite aluno novamente só que agora especificamente na árvore da

direita passando o RH que eu quero remover que vai ser 25 daí você vai ter a seguinte dúvida ué mas eu comecei com de Elite do aluno que invocou de leite noite e agora vou invocar não de leite node ou de livros aluno isso não vai entrar em Loop Infinito aí eu vou dizer não não vai entrar em Loop Infinito porque porque quando você invocar esse de Elite aluno você vai cair ou no caso um ou no caso dois e tanto quanto um tanto Num caso quanto no caso dois basicamente todo o algoritmo vai acabar

naquela chamada recursiva não vai mais ter novas chamadas recursivas Então porque eu tô dizendo que vai ser no caso no caso dois Porque eu sei que o filho da esquerda 15 aqui ele é nulo por quê Porque se não fosse nula então ele não seria o sucessor lógico porque O citológico é o mais à esquerda então não deveria ter outro à esquerda aqui então sei que ou ele tem um filho aqui ou ele não tem esse filho aqui em ambos os casos que que eu vou fazer eu vou remover imediatamente assinou e colocar o filho

no lugar então não vai mais ter novas chamadas é importante saber porque ele não vai entrar em Loop Infinito também então tem uma olhada reveja o vídeo se não conseguiram entender e aqui está o código completo O que nós estávamos estudando agora a pouco são essas três linhas de código aqui onde true é a árvore que vem o por parâmetro em outras palavras o Nokia Eu quero remover deita é onde eu coloquei o conteúdo do sucessor lógico então eu coloquei o conteúdo do sucessor lógico aqui na variável deita justamente para substituir na variável no conteúdo

de True só que agora ficaram dois ela é nós com o mesmo conteúdo e o que é que eu faço eu apago esse conteúdo te na árvore da direita bom então essa aqui é a ideia vamos fazer agora uma aplicação dessa estrutura nós vamos inserir alguns elementos em uma search string que seria essa classe que nós geramos para criar um objeto e feito isso nós vamos Verificar como se remove e como se faz as impressões na saída padrão árvore que eu vou utilizar vai ser essa obra aqui tá eu vou inserir esses elementos primeiro 20

depois dos 18 primeiros 20 hoje alimento é Pedro 18 para os elementos e Raul depois do 58 cujo nome é Paulo que o conteúdo de pau o set que é um carros e assim por diante como eu faço isso primeiramente eu declarei essa trick é essa classe que nós acabamos de implementar e eu vou inserir nela oito alunos primeiramente eu coloquei todos os reais Não Há rei e todos os nomes em um segundo a rei e aqui eu vou criar um terceiro Array e esse terceiro Array esquecer e ele vai conter todos os alunos que

tem esse r a o primeiro a guiar com o primeiro nome segundo R aqui no segundo nome e assim por diante E se eu faço nessas linhas de código bem aqui eu declaro um objeto aluno com essa linha aqui aluno r a e o nome isso e Sra e eu ia mesmo nome e depois eu adiciono esse aluno tanto no Array quanto na minha árvore binária de busca eu não precisava colocar realmente dentro de um Array eu só não quero perder esses elementos por quê Porque depois eu quero poder remover esses elementos sem ter que

de cabeça saber quais eram os reais desses alunos Então estou gravando todos os reais todos os alunos dentro desse vetor 1 o sapo e feito aquilo que é que eu posso fazer depois de inserir esses elementos Napoli binária de busca eu já posso pegar o meu objeto e dizer olha imprimo aqui em pré-ordem Depois eu digo olha imprimir aqui em ordem e depois de Imprima em pó sorte na impressão em pré-ordem que que ele vai fazer ele vai visitar primeiro a raiz daqui é pré Aí depois ele vai visitar a esquerda como ele vai visitar

raíz ele vai pegar o ouvinte e o Pedro e colocar o Pedro na saída padrão então ficou Pedro depois ele vai para a esquerda veio o Raul depois ele vai para a esquerda veio o Carlos depois ele vai para a direita aqui do Raul onde tinha o Lucas e daí ele já terminou toda essa ramificação para onde ele vai agora ele vai para cá o lado direito de Pedro ele vai pegar o pau depois ele vai a Maria depois da Samantha e por fim o disse isso no pré-ordem e não é ordem ele vai primeiro

para a esquerda então ele iria começar aqui do nosso raiz mas não imprimiria o Pedro porque porque em ordem ele só vai imprimir o Pedro você vai visitar o Pedro depois de visitar a árvore das que tá então ele vai visitar por das criança tem o Raul mas o Raul não será impresso por quê Porque ele vai visitar primeiro a árvore da esquerda que tem o Carlos O Carlos não tem agulha na esquerda então ele vai imprimir o carros e depois de imprimir o Carlos Aí sim ele pode imprimir o Raul por quê Porque em

ordem depois ele vai para o Lucas que é na atualidade direita desse dessa pequena sub-árvore bem aqui feito isso como ele já acabou toda árvore da esquerda aí sim ele pode imprimir o raiz que seria o Pedro E daí ele passa para abrir a direita e na árvore da direita ele não imprimir e mediatamente o Paulo porque porque ele seria para a esquerda não imprimiria Maria porque ele seguiria para a esquerda onde encontrarei a Samanta depois ele voltaria para Maria já que em ordem e depois ele seguiria Promises e depois de terminar Nunes ele vai

perceber Olha já terminei toda essa árvore aqui já posso imprimir o palco esse seria um em ordem é uma continuação desse código que que foi feito foi feito a remoção do no Raiz que ela de Elite aluno é o primeiro elemento do meu Beetle tão que eram na raiz então para remover o Pedro o que que ele fez ele foi na árvore da esquerda bem aqui e encontrou Quem era na verdade direita desculpe encontrou quem era o elemento mais à esquerda e percebeu que era a Samanta Então ele pegou a Samanta que era o conteúdo

e colocou exatamente no lugar de Pedro e depois ele veio nessa árvore aqui apagou essa manta então a única modificação aqui é que aqui apareceu a Samantha e daí a gente pode perceber que a Samanta virou a raiz porque porque no caminhamento pré-ordem ela foi o primeiro as empresas E isso está de acordo então com a nossa intuição é só que eu gostaria de falar por hoje nós demos a implementação do código de Elite aluno em detalhes feita em ser mais se não entendeu alguma coisa da aula de hoje eu recomendo que assista aula novamente

caso contrário já pode seguir para a próxima ao um forte abraço e até a próxima a E aí [Música]