Curso de Programação C | O que é uma Arvore AVL - Árvore Binária de Busca Balanceada? | aula 301

o Olá vamos dar continuidade ao nosso curso de programação com linguagem C depois então de árvores binárias igual algoritmo de ruckman Vamos iniciar agora o aprendizado sobre árvores balanceadas vamos ver nessa aula O que é uma árvore balanceada E por que que a gente precisa das Árvores balanceadas talvez você tiver alguma de Poxa mais Qual o problema de uma árvore vinagre diante mão eu já adianto para você que normalmente uma árvore balanceada Ou pelo menos a árvore balanceada que nós vamos ver nessa aula também é uma árvore binária ou seja continua válido aquela regra de

que se o elemento a ser inserido por menor ele vai para subir Arlei esquerda que o elemento a ser inserido por maior ele vai então para subir a árvore a direita Ok mas então vamos entender Qual o problema com a árvore binária Por que que a gente precisa de outra árvore ou de uma árvore modificada chamada de árvore balanceada o grande problema é que na maioria das vezes árvore binária é eficiente porém Pode ser que Em algumas situações a gente tenha uma árvore binária a hora de degenerada ou uma árvore binária desbalanceada Você pode encontrar

os dois nomes na literatura e os dois estão corretos Ok tanto faz uma árvore degenerada ou uma árvore desbalanceada E aí vamos entender o que seria então uma árvore binária degenerada nós temos aqui um exemplo olha só uma árvore binária degenerada perceba que o que nós temos aqui é muito similar a uma lista encadeada a uma fila encadeada ou também algum vetor se eu quiser por exemplo Pesquisar nessa árvore binária perceba que a gente tem aqui uma árvore milagre se eu quiser pesquisar por exemplo se o elemento 500 está na nossa árvore binária olha só

é a raiz Não não é o que eu estou procurando é maior sim então eu vou para direita é um 500 não 500 é maior assim eu vou para direita perceba que para descobrir que o 500 não está na nossa árvore binária eu preciso percorrer toda a minha árvore até chegar aqui e verificar tem filho direita não não tem então eu posso afirmar que o 500 não está na o cenário perceba aqui se a gente cria uma árvore binária degenerada todos os processos de inserção remoção busca e consequentemente toda operação de a gente vai fazer

na nossa árvore ela se torna muito lenta porque basicamente o que nós temos aqui é uma lista encadeada ou um vetor e nós já vimos lá no início do curso de uma estrutura de dados do tipo vetor não é eficiente principalmente se você precisa ficar realizando busca percorrendo o retorno do início ao fim procurando por elementos então uma árvore balanceada é a árvore resultante de uma árvore e degenerada da gente vai realizar algumas operações nessa árvore para fazer com que uma árvore degenerada como essa daqui se torna então uma árvore balanceada consequentemente Então a gente

vai estar melhorando o custo de inserção de deleção e principalmente de busca na nossa árvore vinagre Então nós vamos conhecer nessa aula a árvore avl que é uma árvore binária de busca balanceada porém ela a única existe também a árvore vermelho e preto também conhecida como rubro-negro são exatamente as mesmas é exatamente a mesma árvore então você pode encontrar na literatura na internet tanto como árvore vermelho-preto como rubro-negro ou nos materiais em inglês árvore redblack tem também a árvore dois três quatro para árvore a a e essas duas que eu nem conhecia eu pesquisando materiais

sobre árvores balanceadas eu encontrei esses dois exemplos também então perceba que tem uma diversidade bem grandes de árvores balanceadas a partir de agora então a gente vai focar o nosso estudo na árvore avl hv ela foi proposta inicialmente em 1962 então perceba que assim como a Computação em diversos algoritmos ela é relativamente nova e porque a Vl essa abreviação vem das Letras iniciais dos nomes dos pesquisadores e propuseram essa ideia Adelson velski e lanches então a ver e ele e o interessante das Árvores balanceadas que serve para qualquer árvore balanceada não apenas Av l-1 árvore

balanceada você consegue realizar operações como inserção remoção e busca tem o de log de n onde n é o número de elementos que você tem na árvore Então ela se torna extremamente eficiente tem Em contrapartida uma árvore não balanceada Se você pegar no pior caso o custo dessas operações vai ser o Diene ou seja como Eu mencionei é muito semelhante a uma lista encadeada ou no vetor talvez você vai precisar percorrer a sua estrutura completa do início ao fim para descobrir que o elemento que você procura não está lá agora vamos começar a entender então

o que que essa ideia de balanceamento nós temos aqui um exemplo de uma árvore balanceada e Aqui nós temos o exemplo de uma árvore e desbalanceado então o tempo balanceado pode ser entendido como sinônimo de equilibrado perceba que essa árvore ela está equilibrada tem a mesma quantidade de filhos aqui a esquerda EA direita Enquanto essa árvore é que não mas muita cá é a ideia de balanceamento ela não está diretamente ligada a quantidade de filhos mas ao fator de balanceamento de cada nova E aí já já a gente vai ver o que que é esse

fator de balanceamento o objetivo é manter a subir árvores tanto esquerda quanto direita com a menor diferença possível E aí nós vamos ver que essa menor diferença possível é um um ou Menudo E aí nós vamos ver o porquê deste valor Como Eu mencionei nós temos então agora nas árvores balanceadas O que é chamado de fator de balanceamento e a esse fator de balanceamento o que vai dizer para você se você precisa ou não Balancear a sua árvore todo modo a nossa árvore A partir de agora possui um conceito chamado de fator de balanceamento e

eu Vou abreviar esse fator de balanceamento como fbo-14 balanceamento ele é calculado por meio da subtração entre a altura da subárvore esquerda e altura da subárvore direita então é aquilo que Eu mencionei anteriormente a é diretamente ligado a quantidade de nós mas a altura da sub-árvores Ok e aquilo que nós temos é realmente uma fórmula Olha só o fator de balanceamento é igual a altura da subárvore esquerda - altura da subárvore direita perceba que a nossa fórmula tem uma subtração então pode ser que a gente tem um fator de balanceamento negativo Imagine que eu tenho

a por exemplo altura da subárvore esquerda dois e altura da subárvore direita três perceba aqui 2 - 3 da menos um a gente tem um fator de balanceamento menos um e tá tudo bem não tem nenhum problema com isso o nosso fator de balanceamento pode ser zelo um ou menos um ele não pode ser maior do que mais maior 21 ou menor do que menos uns se isso acontecer se eles chegarem dois ou menos dois significa que a gente precisa Balancear a nossa árvore e aí a gente vai dar então como fazer esse balanceamento existem

quatro possibilidades 4 situações diferentes que podem ocorrer eu precisava anunciar nossa árvore e cada situação ela precisa ser tratada de uma forma específica esse fator de balanceamento Como Eu mencionei um ou menos um o fator de balanceamento acima de um o abaixo de menos um significa que a árvore está desde balanceada nesse caso nós vamos fazer algumas operações chamadas de rotações então a gente pode rotacionar nossa árvore para esquerda ou para direita e o objetivo de fazer isso novamente é equilibrar é rebalancear a nossa árvore vinagre nós vamos ver agora então as quatro possibilidades que

existem para gente rebalancear a nossa árvore binária a primeira situação que a gente vai ver é a rotação a esquerda e já já você vai entender porque a esquerda Olha só lembra nossa árvore Inicial lá no exemplo que eu disse que ela está desbalanceada perceba nós vamos agora calcular que no nosso fator de balanceamento Olha só perceba que ela está toda esticadinha para a direita é como se fosse um retorno de três posições ou uma lista encadeada com três elementos Então olha só para esse nor altura 01 o aumento Del Este nó altura um fator

de balanceamento - porquê - um Olha só para quem acompanha o curso aqui no canal já deve ter visto lá nas águas sob a árvore binária e tem uma aula lá mostrando como calcular a altura de uma árvore binária então eu não vou repetir aqui para ela não ficar muito extensa Se você não se recorda como calcula a altura de uma árvore binária eu vou deixar o link para essa aula aqui na descrição do vídeo e nos cards aqui acima consegue lá como faz isso Ok vamos ver então um fator de balanceamento precinorm lembra da

Fórmula na altura da sub-árvore a esquerda menos a altura da subárvore direita Olha só qual que é essa altura aqui menos um altura dessa Tube árvore não tem ninguém Qual que é a altura da árvore aqui 0 - 1 - 0 nós temos então menos um o fator de balanceamento de se não é menos um perceba que já atingiu o valor máximo aceitável Quando a gente chegar na raiz a altura da nossa rua é dois perceba que nós temos duas pontes Dois caminhos e o fator de balanceamento e olha só altura da subárvore esquerda ela

não existe então altura menos um altura da sub-árvore a direita é a altura de sinal aqui altura um E aí olha só lembra que tem um menos na Fórmula - 1 - 1 nós temos menos dois nesse caso aqui olha só nós temos uma árvore desbalanceado é que precisa ser balanceada E aí por que que essa situação é uma situação plástica ela é chamada de rotação a esquerda porque a ideia é exatamente fazer isso fazer uma rotação para esquerda ou o nó 10 aqui ele vai descer e ele vai se tornar filho do 25 então

Perceba o 10 ele é pai do 25 ele vai descer e ele vai ser pendurado aqui ele vai se tornar filho no 25 então perceba que a gente realmente faz uma manipulação com os nós da nossa árvore ao fazer isso 25 vai se tornar Raíssa então percebo que nós temos aqui aí realmente a ideia de uma rotação porém essa rotação é feita com a manipulação de pontos e perceba que tudo que é ponteiro a nossa raíz um ponteiro filho e escrever um ponteiro filho a direita um ponteiro Então o que a gente vai ter que

alterar o filho à esquerda do 25 vai receber um ponteiro para o Raí e ainda que caso perceba que o ponteiro para subir a árvore a direita vai ficar nula nesse caso perceba nós saímos de uma árvore degenerada ou Deus balanceada para uma árvore balanceada é assim então é a primeira situação rotação à esquerda a gente vai aplicar rotação esquerda perceba Quando a gente tiver que um fator de balanceamento menos dois ou seja negativo mas na hora de implementação a gente vai ver na hora de implementar a gente vai ver direitinho o que que a

gente verifica para descobrir que nesse caso aqui a gente faz uma rotação a esquerda Ok a nossa próxima rotação é o oposto uma rotação direita perceba a gente também pode ter uma sub-árvore desse tipo aqui olha só se a gente avaliar aqui o fator de balanceamento da nossa raíz lembra o fator de balanceamento é a altura da subárvore esquerda mim a Navegar para direita e aí olha por quê que o fatura que fica positivo altura da subárvore esquerda é um Então a gente tem um menos altura da subárvore direita altura da subárvore direita menos um

Então o que a gente tem aqui é no menos menos um lembra da regrinha de sinal na matemática ela também se aplica aqui menos com menos vai dar mais um mais um dois nós temos então o nosso fator de balanceamento dois e nesse caso como você já deve ter imaginado a gente vai fazer uma rotação para direita ou seja os 50 vai descer e vai se tornar filho no 35 E aí a gente chega então nesta versão aqui perceba que o 20 ele não é mexido em nenhum momento ele permanece à esquerda do 35 o

nosso 35 ele é elevado à condição de raiz da nossa árvore e os 50 que era pai do 35 agora ele se torna filho do 35 E aí nós temos novamente uma árvore balanceada essas duas situações são as situações mais simples a esquerda EA direita Ourém mas elas não resolvem todas as situações porque na situação anterior à esquerda perceba que a nossa árvore ela tende sempre para a direita e agora na rotação direita perceba que a nossa árvore está aprendendo sempre para a esquerda mas isso nem sempre vai acontecer eu poderia ter um nó aqui

ao invés do novinho que eu poderia ter aqui um a 40 perceba aqui nessa situação eu não posso usar nem a rotação a direita e na rotação esquerda porque é uma situação diferente e nós vamos ver outras duas situações agora um pouquinho mais complicada porém essas duas situações vão utilizar votação a direita EA esquerda então a base do balanceamento a base da ideia para manter nossa árvore balanceada são as rotações à direita e à esquerda a partir dessas duas votações a gente vai fazer mais duas um pouquinho mais complicada Ok vamos entrar um a próxima

nós temos aqui agora uma rotação direita esquerda na literatura e na internet normalmente você vai encontrar essa rotação com o nome de rotação dupla o ou rotação dupla à direita e já já você vai entender o porquê olha só a nossa árvore aqui 100 200 150 perceba a gente não tem mais uma árvore toda para a direita ou toda para esquerda Então olha só o nosso fator de balanceamento à altura dessa sub-árvore - 1 - altura dessa subir a rua e altura 1 -1 -1 -2 então novamente nós temos aqui uma árvore Deus balanceada porém

a gente não consegue Balancear essa árvore com um único passo uma única rotação Então olha o que que a gente vai fazer primeiro nós vamos fixar neste Enoque e nós vamos fazer uma rotação a direita porque a direita perceba que o filho desse nós tá esquerda Então a gente vai rotacionar para direita apenas esta sub-árvore qualquer ideia trazer o 50 150 aqui pra cima e o 200 vaguear filho do 150 porque olha só quando a gente faz essa rotação a direita perceba agora a árvore num modelo que nós já vimos uma árvore pendendo completamente para

direita agora eu posso simplesmente aplicar na nossa raíz uma rotação para a esquerda por isso que eu coloquei aqui rotação direita e esquerda a gente faz nesse nós nessa plug árvore uma rotação à direita vamos obter essa sub-árvore aqui e agora aqui na raiz da nossa árvore perceba raiz é um nó que tem o fator de balanceamento 2 ou menos dois a gente vai agora fazer uma rotação para esquerda ao fazer essa rotação para esquerda aqui na nossa raíz nós vamos obter essa árvore aqui Percebo o sangue vai descer e vai se tornar filho do

150 nesse caso aqui a nossa raíz agora eu 150 com o 200 a direita e os em à esquerda dos 150 e a nossa última Possibilidade é a rotação esquerda direita que é muito similar perceba enquanto nós tiramos aqui direita e esquerda agora nós temos esquerda direita 200 aí e sem e a direita o 150 perceba que são todas árvores binárias de multa válidas Ok o sem ele é menor do que o 200 então ele está a esquerda um 150 ele é maior do que o sem então ele está direita mas ele é menor do

que o 200 então ele está a esquerda 1200 novamente a gente calcular que o fator de balanceamento olha só a altura da nossa sub-árvore esquerda 1 - altura da subárvore direita - 1 - menos um cordão o mais um dois então novamente a gente precisa rebalancear essa árvore que a gente vai fazer isso olha só uma rotação esquerda neste Nokia e perceba é um filho a esquerda da Nossa Raíssa Por que que a gente vai rotacionar ele é a mesma ideia da votação anterior os 150 vai subir e o sangue vai descer a gente vai

ter agora uma forma tradicional o primeiro modelo que nós 1200 150 e 100 ao observamos essa árvore aqui basta agora fazer uma outra rotação a direita e aí a gente vai obter a nossa árvore completamente balanceada perceba ao fazer essa rotação para direita o 200 vai descer e o 150 vai ter vai se tornar a nova raiz na nossa árvore e aí a gente novamente atingir o estado balanceado da nossa árvore milagre Assim como Eu mencionei ele perceba que as votações para a esquerda EA direita são a base do balanceamento da nossa árvore vinagre por

meio dessas votações da esquerda e à direita a gente consegue fazer rotações duplas uma esquerdo uma direita e uma outra rotação dupla à direita e à esquerda e à então a gente consegue então Balancear qualquer situação ou qualquer estado da nossa árvore vinagre se ficou qualquer dúvida já sabe né Posta aí nos comentários que eu terei o maior prazer em ajudar e deixa o celular aqui nessa aula vai se inscreva no canal se você não é inscrito ainda e eu te convido a conhecer o clube dos membros do canal clica no botão azul abaixo que

você vai ter todas as informações que você precisa do mais nos vemos na próxima aula com a implementação de uma árvore binária um balanceado a nossa árvore avl nos vemos lá