*Estruturas de Dados - Árvores AVL

Olá caros alunos sejam bem-vindos a mais uma aula da nossa disciplina de estruturas de dados hoje nós vamos falar sobre árvores ave na hora de hoje eu vou seguir este rodeio primeiramente eu vou falar sobre alguns conceitos básicos de árvores avl depois eu falarei um pouco sobre implementação da estrutura do nó mudanças no tipo abstrato de dados em relação as árvores vistas em aulas anteriores em alguns detalhes de implementação e os algoritmos de busca inserção e remoção vistos na aula passada no pior caso o número de comparações é proporcional à altura da árvore as buscas

então exceção e remoção também são eficientes em árvores quando elas estão balanceadas em árvores degenerados como essa árvore que eu estou mostrando aqui as operações deixam de ser eficientes porque por exemplo se eu quero encontrar 19 29 eu vou ter que varrer todos os elementos desta minha árvore até encontrar o elemento 29 isso aqui não é melhor do que uma busca sequencial qualquer dentro de um vetor por exemplo Então como árvores degenerados nós perdemos aquilo que nós queremos quando criamos a as árvores binárias de buscas que seriam busca de sensações e remoções feitas de maneira

eficiente então quê que nós temos que fazer nós temos que dar um jeito de manter essa árvore balanceada e na hora de hoje nós vamos verificar uma dessas maneiras pelo menos uma dessas maneiras em que nós chamamos essa árvore de árvore a ver para entender a árvore avl Mas precisamos entender primeiramente o que que é o fator de balanceamento um fator de balanceamento é diferença de altura entre a subir árvores da direita e subir árvores da esquerda de umdeterminado nó bom então em árvores avl se você faz essa diferença de altura então o fator de

balanceamento ele deve ficar entre menos um em outras palavras o fator de balanceamento de todos os vértices em uma árvore avl deve ser ou menos 1 ou 0 ou mais um infrações e remoções a priori em árvores avl elas iniciam com os algoritmos vistos em aula são passadas para ver binária de busca entretanto se algum 9 olar a propriedade do fator de balanceamento qual a propriedade essa daqui após uma inserção ou remoção então uma rotação deve ser feita Isso quer dizer o que então que nós começamos os códigos da mesma maneira que fizemos em aulas

passadas e ficamos monitorando os fatores de balanceamento após cada inserção e após cada a remoção para saber se a a propriedade de árvore avl foi violada ou não vamos entender melhor o que é um fator XIII é com esse slide aqui vamos pegar esse nó aqui que é uma folha o milhão uma folha então a subir a corrida da direita que a lula EA sob a árvore da esquerda que é no elas possuem o mesmo tamanho se elas possuem o mesmo tamanho o fator de balanceamento que a diferença entre os tamanhos dela é zero essa

árvore aqui talvez seja um pouquinho mais interessante essa sub-árvore aqui do nosso 30 a gente tem essa a sob a árvore da direita e a subir a árvore das da esquerda uma tanto uma conta outra elas possuem o mesmo tamanho como elas possuem o mesmo tamanho fator de balanceamento é a diferença de tamanho então fator de balanceamento Aqui é zero eu vou obter agora um nó esse Noque se não aquele tempo a torre de balanceamento mais um vamos entender porque eles têm ele tem essa subir agora' aqui da direita cuja altura é um e ele

tem essa subir abra aqui da esquerda por cuja altura é zero como na direita altura é uma e na esquerda 10 então o fator de balanceamento dele é a altura da direita que é um menos altura da direita que zela que significa igual a mais um tão isso significa o fator de balanceamento para nós termos uma árvore avl nós temos que uma litoral fator de balanceamento de todos os nós dentro dessa árvore e monitorando o fator de balanceamento de todos os nós dessa árvore nós veremos Qual o nó viola o fator de balanceamento toda vez

que nós fazemos uma inserção vamos supor que nós temos uma árvore avl Ou seja todos os fatores de balanceamento são mais 10 ou menos um toda vez que nós fazemos uma infecção por exemplo o fator de balanceamento de alguns vértice alguns nós vai mudar como acabei de fazer uma exceção e antes era uma árvore avl eu sei que se mudar ele não vai mudar por exemplo fator de balanceamento de mais um um dos Nós e o mais quanto se mudar o fator de balanceamento para algo que viole a árvore avl é sinal de que mudou

de mais um por exemplo para mais dois ou de menos um para menos dois eu tenho tenho que me preocupar após uma infecção em verificar se aparece o mais dois ou menos dois e fazer algumas rotações no caso de terem Aparecido por exemplo aqui eu tenho essa árvore aqui vamos supor que ela apareceu após uma infecção não tem aqui a b c e d são árvores por exemplo que são subir árvores possuem a mesma altura Então se elas são subir árvores que possuem a mesma altura a subtração do lado direito que seria essa sob a

árvore de altura h com lado esquerdo que seria essa subir a árvore aqui que tem altura 2 + H daria menos dois então esse novo 25 viola as regras de uma árvore A velha que que eu preciso fazer para ajustar essa a e eu faço que nós tomamos de rotação que que é uma rotação a rotação ela é uma operação local e vai fazer com que eu faço algumas modificações dessa árvore nesse caso aqui do 25 Como é menos dois eu vou dizer para vocês que vou fazer uma rotação para a direita então aqui essa

cor verde significa unlock vou fazer anotação a rotação para direita o que que é essa rotação para direita essa rotação vai fazer com que o 15 Vire a raiz da árvore dessa alma dessa sub-árvore aqui e 19 25 Veri filho do nosso 15 então eu rodei aqui para a direita tem essa sensação de rotação isso fez com que o nosso 15 subs então no lado direito do nosso 15 ficou que antes eram na raiz o 25 entretanto na quinta anteriormente aqui já tinha um filho a direita que era o b o que que eu faço

com esse filho a direita ele vai virar o filho à esquerda do que antes a raiz que é 19 25 então é interessante olhar para essa figura aqui e e ficar satisfeito com o que aconteceu com essa Rotação o 25 ele passou a seu filho a direita do 15 e o que antes era filho a direita do 15 e passou a seu filho a esquerda do 25 esse outro caso aqui é simétrico Entretanto é para o outro lado é para esquerda nesse caso eu tenho lado esquerdo alguém com uma altura h e do lado direito

alguém como altura 2 + H fazendo com que o fator de balanceamento de se nós ficasse mais dois o que que eu preciso fazer então aqui uma rotação para a esquerda aqui nesse nós então vou fazer uma votação para esse lado percebam que a regra é a mesma do caso anterior só que agora parece teta o 15 aquele vai vir a raiz da árvore e o 10 que antes era raiz dessa sub-árvore ele vai virar o filho à esquerda do 15 então ele vai aparecer aqui só que anteriormente o 15 ele já tinha a esquerda

daqui é você que que eu vou fazer com esses e ele vai virar o filho a direita do desce E então percebo é parecido com o anterior só que para o outro lado e esse nosso caso aqui a gente viu que o fator de balanceamento era menos dois e por que eu fiz uma rotação para a direita nesse caso só para entender a regra eu fiz uma rotação para a direita porque o filho mais alto de sinnott que viola a propriedade avl ele era menos um como eu sei quem é o filho mais autora se

o fator de balanceamento ela menos dois eu sei que o filho mais alto tá do lado esquerdo dele porque porque o fator de balanceamento significa o lado direito ao produzir lado direito menos altura do lado esquerdo então quando é menos 2 e o filho mais alto é menos um eu já sei existe uma regra rotação é para direito quando o patrão se o balanceamento do Norte viu a regra é mais dois eu tenho pode agora por filho mais alto ele vai estar do lado direito porque porque o fator de balanceamento é positivo ele é mais

dois então e o filho se o seu Nokia viola a regra tem 14 balanceamento + 2 e o filho mais alto tem 14 balanceamento + 1 e está abaixo uma rotação para a esquerda só que existem alguns outros casos como esse caso bem aqui onde o fator de balanceamento é menos 2 e o filho mais alto tem fator de balanceamento mais um esse caso aqui ele não é tão simples como caso anterior eu não vou conseguir resolver esse problema com apenas uma rotação eu vou precisar de duas votações em sequência a primeira rotação vai ser

uma rotação para a esquerda nesse nosso filho mais alto então nesse noc eu vou rodar para a esquerda isso significa aqui ó 15 ele vai virar pai de sinnott que eu estou rodando que é o desce então 15 ele vai virar Popeye o 10 vai virar o filho à esquerda do 15 só que não tem aumento 15 já tinha um filho a esquerda que era essa subir árvores e que que eu faço com ela ela vai virar filha a direita da sub-árvore 10 que anteriormente se ela raiz dessa subir África e daí você vai dizer

ué mas isso não resolveu o problema do balanceamento que a menos 29 25 você quer me ensino 25 eu vou dizer tudo bem Eu não resolver esse problema mas eu já gerei um caso aqui que é igual ao caso que eu já sei resolver que era esse caso aqui em cima então eu sei que basta aqui uma rotação para direita esse caso aquele assimétrico ali só é ao contrário de para o outro lado eu não vou explicar esse caso mas dei uma olhada nele e verifiquem se vocês entendem o que aconteceu aqui uma rotação para

a direita e depois Eu precisaria de uma votação para a esquerda no nó 10 interessante ver a regra toda aqui nessa tabela quando nós falamos e até mais dois e o filho mais alto é mais um eu sei que a rotação é simples a esquerda quando não é mais dois e o filho mais alto é menos um eu sei que eu vou precisar de uma rotação dupla com filho para direito e pai para a esquerda isso está de acordo com os lados anterior o sinal desbalanceada menos dois e o filho é mais ou seja se

os nós desde balanceados e o filho mais alto tem sinais diferentes eu sei que vai precisar de uma dupla sendo que nesse caso é uma dupla com filho para a esquerda e pai para a direita e vamos ver isso daqui um exemplo vamos supor que Eles teriam 9/24 aonde seria o novo 24 o fator de balanceamento dele é zero porque só tem ele se eu exterior nós 18 eu vou ter que olhar o fator de balanceamento de todo mundo todo mundo nessa no caminho do Raiz até hoje eu coloquei um 18 então ele vai vir

a 0 e esse daqui vai virar por exemplo menos um como ele é menos um ele tá dentro das propriedades uma agulha velha então eu sei que eu não vou fazer rotação Se eu colocar o nosso sete vai cair nesse caso aqui onde o 24 ficou com o fator de balanceamento menos dois eu sei que eu vou ter que fazer uma volta votação Qual é a regra a regra do simples a direita porque o fator de balanceamento dele é menos 2 e o filho mais alto tem o mesmo sinal então fazendo uma rotação simples a

direita o 18 vai ver a mais da árvore o 24 vai virar a filha do 18 supondo que um seria agora nossa hein o fator de balanceamento zero se inseriu nov28 aqui ele vai ter fator de balanceamento 10 o 24 vai ter 14 balanceamento + 1 e 18 mais um todo mundo está ok aqui eu não preciso fazer rotação se eu inseri o 32 vem aqui eu vou ter dois nós um fator de balanceamento + 2 qual é o que eu vou rodar fazer a votação vai ser aquele que está mais próximo da folha que

é esse mais dois aqui fazendo a rotação agora para a esquerda desse nó eu vou fazer com que o 28 ver e pai dele e ele viria o filho à esquerda do 28 nesse caso aqui o exterior 26 inserindo 26 o 18 vai ser um nó de um nova mais dois nós falta de balanceamento + 2 o filho dele mais alto tem 14 balanceamento menos um o que que eu sei que eu tenho que fazer aqui uma rotação para direita onde eu 24 vai virar pai do 28 seguida de uma rotação para esquerda o ônibus

e o e você vai virar o pai do 18 e essa árvore aqui ela está completamente balanceado ou seja todo mundo está com fator de balanceamento 0 - 1 ou mais a estrutura do Nokia implementa essa obra velho o que que ele precisa no norte vai precisar apenas um inteiro que vai me dizer o fator de balanceamento Lembrando que eu vou precisar monitorar o fator de balanceamento de todos os nossos Oi e um Tipo abstrato de dados qual vai ser a mudança que eu vou fazer bem a mudança que eu vou fazer as seguintes Eu

não vou mexer no litro e ver aluno eu só vou mexer no instante aluna do de Elite aluno que que eu preciso fazer na verdade eu preciso toda vez que inserir um nó numa árvore eu preciso verificar se a tela árvore cresceu ou não então quando eu ensino eu verifico árvore cresceu porque porque se árvore cresceu ou seja aumentou de altura eu sei que eu tenho que mudar o fator de balanceamento se ela foi a árvore diminuiu eu tenho que verificar se ela é menor para mudar também o fator de balanceamento quem disse a árvore

cresceu ou não a própria chamada recursiva eu passo para essa chamada recursiva aqui por referência Como eu posso ver no próximo slide a passagem de parâmetro do estator e do exterior Apple referência porque porque a um seria um nó eu aviso Quem fez a chamada recursiva se o nosso cresceu ou não Bom dia que eu também preciso de alguns métodos para dizer para fazer a rotação para a esquerda direita uma rotação dupla para escrever direito e uma rotação dupla vamos ver isso aqui nos próximos nos próximos slides de história de implementação vamos estudar a implementação

de alguns métodos eu vou falar apenas sobre a lógica implementada não vou falar assim ah por Dinha o que importa na aula de hoje é mais a lógica do que a implementação ou é 13 tem não teve a implementação mudada o de Elite e tem uma estante e tem teve a implementação mudada eu vou falar apenas do instante e tem não esse aluno desculpem vamos ver o inspetor de aluno ele agora tem essa variável Store que eu tenho que avisar quem me chamou de que a árvore cresceu ou não no caso base aqui são esse

a se eu e seu tio uma árvore vazia e agora é um seria um nome essa árvore significa que altura mudou então vou colocar esse e é igual ao outro dizendo Agora eu tenho uma árvore um pouco mais alta antes ela era vazia e agora ela tem algum pelo menos um nó e o resto é igual que a gente viu anteriormente a lembrando como eu coloquei o fator B porque eu coloquei o fator B = 0 porque na iniciação nós venceremos na folha como é uma folha eu sei que uma folha tem fator de balanceamento

zero eu sei duas coisas quando ele ser uma folha que a árvore cresceu e um fator de balanceamento é zero e o que que eu preciso fazer nas outras chamadas nas outras chamadas do método insert aluno basicamente se não cheguei numa folha eu tenho que continuar fazendo chamadas recursivas por exemplo nesse caso o aluno que eu quero inserir Ele tem R a menor do que o aluno do nó onde eu estou então eu sei que eu tenho que olhar na árvore da esquerda para colocar o aluno lá essa chamada recursiva vai ver vai me dizer

se abre aumentou o tamanho ou não nessa escola e o que é que eu faço sabendo isso se aumentou de tamanho eu sei olha aumentou de tamanho do meu lado esquerdo então o h que é maior do meu lado esquerdo como HQ é maior do meu lado esquerdo eu sei que o fator de balanceamento desse nó diminuiu ou seja será zero ele virou menos um será menos um ele ver ou menos dois tá então sempre atualizar o fator de balanceamento se eu mandei aí se ação ter sido feita do lado direito por exemplo e o

nó era maior eu mandei ele para o lado direito e aumentou eu sei que eu tenho que implementar o fator de balanceamento Ou seja eu mandei isso aí do lado de cá e a chamada recursiva medicina aumentou o tamanho Então se era mais um eu vou colocar agora que é mais dois se era a 0 virou mais um será menos um virou zero Então essa ideia do Store o perform mutations ele vai fazer com que eu implement a tabela que eu mostrei para vocês nos slides anteriores mais adiante eu mostro ele eu vou mostrar agora

a rotação pelo menos essa eu notei isso época que eu vou mostrar para vocês tá então eu tenho assinou aqui eu digo Olha eu quero rotacionar esse entre aqui vamos dizer que ele é o true para a esquerda o que que eu preciso fazer para rotacionar o primeiro salvo um ponteiro para esse nó aqui é o loc vai vir a raiz e depois eu digo Olha esse 10 aqui O que é a direita desse 10 aqui ou seja esse link aqui ele não vai mais apontar por 15 ele vai contar para a esquerda do 15

então é a seguinte assar esta ainda vai vir para cá é isso que eu tô dizendo nessa linha de código aqui tu ia direito é igual a p esquerda e daí eu digo P esquerda ou seja quem vai ficar esquerda desse nó é a raiz ou seja o piso uma jogadinha aqui que fez com que o 15 virasse pai do desce e depois eu digo agora raiz vai virar o p então eu vou atualizar o ponteiro que veio por referência por outros White é simétrico a esse caso aqui recomendo que vocês tenham uma olhada nele

o roteirista leve pendrive simplesmente vai evocar o texto é e o rotate right em sequência por exemplo aqui o texto leve e depois o texto hits no nó apropriado I will perform importei se eu tinha mencionado em slides anteriores e que é que ele vai fazer ele vai implementar essa tabela que eu estou mostrando aqui para vocês por exemplo sem fator é menos 2 e o filho é menos um ele vai dizer que eu tenho que fazer uma rotação para direita e a gente olha para tabela e ver olhar o nosso anunciado era menos dois

e o filho era menos um então a votação era realmente para a direita ele também vai fazer os ajustes após a rotação dos fatores de policiamento é isso que eu tinha para falar na aula de hoje eu espero que vocês tenham entendido é mais importante entender o conceito do que entender a implementação nessa aula de hoje mas se não entenderam alguma coisa recomendo ver o vídeo novamente um forte abraço e até a próxima tchau E aí E aí