Olá pessoal na aula de hoje nós vamos estudar a árvore avl A árvore avl é uma árvore binária que vai seguir as mesmas regras paraa inserção busca e remoção de elementos que nós já vimos mas adicionar essas regras também métodos para se manter o equilíbrio da ar as iniciais avl vem dos seus criadores Adelson vsk e landes a gente começa observando um fato que as operações básicas de uma árvore binária tais como busca inserção remoção e outras levam um um tempo proporcional ao número de níveis da árvore binária de busca isso quer dizer que a continuidade de operações para uma busca uma inserção ou uma remoção no pior caso depende de quantos níveis existem nessa ár feita essa observação a gente conclui que é importante manter a árvore sempre com a menor quantidade de níveis possível para que as operações básicas de busca inserção remoção e outras não custem tanto tempo por exemplo Imaginem a inserção dos números em sequência 1 2 3 4 5 6 até ao 9 Considerando o nosso algoritmo de inserção que nós Já estudamos e conhecemos se nós inserimos primeiro o número um em seguinda o número dois ele é maior do que o número um portanto vai à direita o número três é maior que o número um e maior que o número dois portanto vai à direita também e o número quatro é maior que o número um número dois número três e vai à direita deste assim sucessivamente formando uma árvore extremamente desequilibrado onde nós temos todos nós sempre como filhos à direita neste caso para n elementos essa árvore teria n níveis isso resulta numa péssima distribuição idealmente Nós gostaríamos que estes nós à medida que fossem sendo inseridos fossem sendo rearranjados de forma a manter esta árvore de maneira equilibrada ou seja mantendo mais ou menos a mesma quantidade de níveis na subárvore da direita e na subárvore da esquerda e assim sucessivamente para todas as subárvores por exemplo neste outro arranjo Aqui nós temos os mesmos elementos mas apenas quatro níveis a questão é como fazer para garantir este equilíbrio e a resposta vai estar nas chamadas rotações a gente pode então dividir nosso problema em duas partes A primeira é como detectar esse desequilíbrio e a segunda é uma vez detectado esse desequilíbrio como corrigir esse desequilíbrio vamos começar tentando entender como é que a gente faz para detectar o desequilíbrio o equilíbrio de uma árvore binária de busca é medido subtraindo o número de níveis na subárvore da esquerda do número de níveis na subárvore da direita vamos ver um exemplo aqui eu tô desenhando uma árvore qualquer e a gente pode então observar cada um dos nós e contar quantos níveis existem à esquerda e à direita e subtrair esse número fazendo isso nós vamos ver que por exemplo aqui nós temos zero nesse outro nó nós não temos filho à direita portanto contamos só os os níveis à esquerda que são dois então menos do neste outro nó Aqui nós temos um nível à esquerda e dois à direita portanto O resultado é um e nos ós folha sempre zero né aqui novamente nenhum à esquerda e apenas um à direita portanto um na folha zero outro na folha zero também aqui um nível à direita e outro à esquerda cancelando no outro O resultado é zero e por fim esse nó folha zero também Observe que essa propriedade que dá o equilíbrio da árvore binária de busca é calculada para Cada nó porque cada nó é por sua vez a raiz de uma subárvore e o nó raiz dessa subárvore é esse que eu destaco aqui em amarelo que tem um fator de Equilíbrio menos do Então esse desequilíbrio é uma propriedade deste nó por consequência esse mesmo desequilíbrio também é uma propriedade desta subárvore que tem a raiz neste nó Então essa subárvore em rosa pode-se dizer que está desequilibrada a gente vai dizer que uma subárvore está desequilibrada apenas quando este número for maior do que um ou menor do que men-1 nós vamos tolerar números de Equilíbrio De zero obviamente de um nível ou de menos um nível isso é porque nós podemos ter um número ímpar de nós ou seja em alguns casos Não teremos como fazer a A Árvore ter um equilíbrio completamente nulo Então vamos tolerar aí pelo menos um ou menos um também qualquer número menor do que menos um ou maior do que um será considerado então um desequilíbrio uma vez detectado esse desequilíbrio a gente tem que entender como fazer para corrigir esse desequilíbrio o equilíbrio da árvore é corrigido através das chamadas rotações existem basicamente quatro tipos básicos de rotações na realidade nós temos então dois tipos primitivos de rotações que é a rotação à esquerda e a rotação à direita e mais outros dois tipos compostos de rotação que é a rotação dupla esquerda e a rotação dupla à direita vamos começar então tentando dar uma olhada na rotação esquerda a rotação à esquerda consiste em Como o próprio nome sugere mover os nós que estão na subárvore da direita para a esquerda fazendo com que o filho da direita se torne a nova raiz conforme essa animação então olhando mais de perto né O que a gente tá fazendo aqui é o seguinte primeiro o filho da direita vira a nova raiz em seguida a raiz original vira o filho da esquerda da nova raiz aqui é um caso particular onde o filho da direita já tem um filho da esquerda quando ele se tornar a nova ris O que que a gente faz com esse filho da esquerda que eu marquei aqui como o filho X perceba que qualquer elemento na subárvore da direita ele é sempre maior do que a raiz original ou seja o X por estar naquela posição ele é maior do que a raiz original Então esse filho da direita do nó que era filho da esquerda como ele era parte da subárvore da direita da antiga raiz ele passa a ser o filho da direita deste mesmo nó que agora não é mais raiz ele passa a ser então o filho da direita do filho da esquerda da nova raiz então retomando o filho da direita vira a nova raiz o filho da esquerda do filho da direita vira o filho da direita do filho da esquerda e a raiz original vira o filho da esquerda da nova raiz então se nós temos uma configuração deste tipo onde nós temos os nós a b e d formando uma diagonal e o nós C ali como aquele filho da esquerda do filho da direita primeiro B é a nova raiz em seguida o filho da esquerda de B vira o filho da direita de a que era a antiga Raiz e por fim a vira filho da direita de b a rotação à direita vai funcionar de uma forma análoga Então já seguindo essa mesma lógica agora nós temos uma diagonal pro outro lado né o filho da esquerda vira a nova raiz ou seja neste caso aqui B é a nova raiz aí o filho da direita de B vira o filho da esquerda de quem era a antiga Raiz e não vai ser mais né de c e por fim C vira filho da direita da nova raiz que é b nós já vimos então agora a rotação à esquerda e a rotação à direita Então vamos tentar entender agora essas rotações compostas são as rotações duplas né rotação dupla à esquerda e rotação dupla à direita considere por exemplo a seguinte situação nós temos aqui três nós o nó a com um filho à direita que é o nó c e este filho por sua vez tem um filho à esquerda que é nó B se a gente experimentar corrigir esse desequilíbrio do nó a com uma rotação à esquerda o que que acontece a gente vai observar que o resultado é c é a nova raiz a é agora o filho a esquerda de C e B é o filho da direita de a ou seja nós não resolvemos O desequilíbrio mantemos a árvore ainda desequilibrada para detectar esse tipo de caso particular onde a rotação simples não resolve basta olhar o desequilíbrio da subárvore de onde a nova raiz vai vir neste caso Aqui nós temos um desequilíbrio Positivo na raiz original mas na subárvore da direita onde nós temos o que vai ser a nova raiz nós percebemos um desequilíbrio negativo então o desequilíbrio Positivo na raiz original e desequilíbrio negativo na subárvore da direita onde nós teria a nova raiz indica que uma rotação simples não resolve o problema a solução aqui é primeiro fazer uma rotação à direita Na sobre árvore da direita em seguida então uma rotação à esquerda na árvore original ou seja o primeiro passo aqui destaca em verde né a gente mantém a raiz original e a gente faz uma rotação à direita Na subárvore da direita e por fim então podemos fazer a rotação à esquerda na árvore original Isso é uma rotação dupla à esquerda a rotação dupla à direita vai ser muito similar neste caso nós temos aí os nós c a b onde c é a raiz a é o filho da esquerda agora e B é o filho da direita do filho da esquerda então a gente começa com uma rotação à esquerda na subárvore da esquerda em seguida uma rotação à direita na árvore original então agora nós vimos a rotação dupla esquerda e a rotação dupla à direita também a questão agora é como a gente faz para decidir qual rotação devemos realizar a gente vai seguir os seguintes passos a gente vai começar calculando aquele fator de Equilíbrio que aqui eu coloco uma variável representada pela letra q onde q igual R que é o número de níveis à direita menos L que é o número de níveis à esquerda em seguida a gente verifica se esse fator de Equilíbrio está no intervalo -1 e 1 se q for -1 ou 0 ou 1 a árvore estará equilibrada não nada a ser feito já se q for maior que um neste caso a gente vai ter duas possibilidades primeiro né se a subárvore da direita tem q menor que zero ou seja o q é negativo na subárvore da direita então nós precisamos fazer uma rotação dupla esquerda ou seja uma rotação à direita Na subárvore da direita seguida de uma rotação à esquerda na árvore principal senão então que da subárvore da direita ele é ou nulo ou positivo neste caso uma simples rotação à esquerda base já se q não é é maior que 1 se q for menor do que -1 neste caso então nós teremos de forma análoga também duas possibilidades a gente vai examinar dessa vez a subárvore da esquerda Então se na subárvore da esquerda nós temos o q positivo fazemos então uma rotação dupla à direita já se o q for nulo ou negativo basta uma rotação simples à direita bom a gente encerra por aqui então essa aula sobre a árvore avl até a próxima