O Que é Árvore AVL, Propriedades da Árvore AVL e Por que AVL é Balanceada | Estrutura de Dados #19

Olá pessoal eu sou o Alisson e esse é o canal programação dinâmica no vídeo de hoje a gente vai começar os nossos estudos sobre a árvore avl que é um tipo de estrutura de dados Auto balanceado então no vídeo anterior a gente viu que que são árvores balanceadas e como que esse conceito é importante para que a gente possa garantir que a gente vai fazer operações eficientes de busca inserção e emoção dentro de uma árvore e agora a gente vai ver o nosso primeiro exemplo de uma estrutura de dados que tem uma propriedade e uma

forma de funcionamento que vai garantir esse balanceamento e consequentemente as operações eficientes então indo direto ao ponto o que é uma árvore avl uma árvore avl é uma árvore binária e Mais especificamente uma árvore binária de busca então na prática a gente vai se preocupar em organizar os elementos dentro dessa árvore de maneira que assobiava e esquerda né de 19 contém elementos menores do que eu e a direita os elementos que são maiores é aquela vai ser uma árvore binária de busca mais especializada porque não vai ter a seguinte propriedade era todo nó aí dentro

da árvore avl a diferença da altura entre a subir água e a esquerda e a subir a árvore a direita daquele nós vai ser no máximo ou seja ou assobiava esquerda EA direita tem exatamente a mesma altura aí a diferença é zero ou uma delas vai ter altura maior que a outra e essa altura tem que ser igual toda a outra mais um no máximo por exemplo se a gente fizer alguma árvore que é composta por um único nó a gente tem uma árvore avl por quê Porque a subir a mão esquerda vazia um ponto

alto re zero assobiavam e a direita é vazio tem alto reserva também a diferença entre essas alturas é zero e é menor ou igual a um certo e começa aqui a único nosso em nossa árvore então todos os nós da árvore tensa propriedade então é uma árvore avl aí e continuar estendendo essa árvore colocando por exemplo mais um Nozinho aqui embaixo isso aqui ele continua sendo uma árvore avl porque se a gente olhar para esse nós aqui em cima a raiz a gente tem que a subir a árvore a esquerda tem altura zero EA sob

a árvore a direita é composta por esse único Nozinho aqui que então tem altura um E aí é diferença de altura entre assobiava e esquerda e à direita da raiz vai ser de um E aí você passa para olhar o próximo nós porque tem que ser Válido para todos os nós na árvore então eu para esse outro noc.ai ficar no caso anterior né em que a esquerda EA direita são vazios e a diferença zero que é menor igual a um Então essa aqui também uma árvore avl e válida mas a gente seria mais um nome

desse jeito aqui ó e daí a gente não vai ter uma árvore avl válida porque olhando aqui para raiz diretamente a gente vê que a subir a árvore a esquerda continua tendo altura zero porque a vazia certo mas assobiavam e a direita agora tem altura dois e a diferença então entre as alturas dessas duas sub-árvores vai ser dois que a maior do que um então a gente não tem uma árvore avl válida mas perceba que é possível fazer uma árvore avl válida com três nós né a quantidade de nós que a gente tem aqui se

a gente tivesse inserido de outra maneira né se estivesse inserido e sinnott que veio aqui para baixo por exemplo aqui a esquerda e a velha vai dar uma propriedade interessante que no seu funcionamento ela vai realizar algumas rotações para que ela permaneça garantida essa propriedade em todos os seus nós Ela poderia por exemplo rotacionar aqui a esquerda de maneira que este no aqui e a nova raiz então a gente poderia ficar com uma nova configuração dessa maneira em que aqui é direita veio esse Noah a antiga raiz passou aqui para esquerda e a gente tem

que esse Nozinho aqui que a gente já tinha comentado viu a nova raiz tá vendo e agora a gente tem uma árvore e a VR com três nossos quando esta propriedade é válida para um nó a gente diz que esse nós tá regulado ou seja os nossos regulado são aqueles nós vamos quase a diferença entre a altura da sub-árvore e a esquerda EA direita é no máximo um e quando todos os nós da árvore são regulados a árvore é a Vl então não tem mistério eu sei que para muita gente essa é uma parte do

curso que começa a ficar mais densa não é um pouco mais complicada mas eu tô aqui quebrando e reforçando esses conselhos para você para mostrar que não eu não tô complicação assim tá você tem que pegar a ideia Geral do conceito e absorver né aqui o interior Isaque Eu dentro de você então a ideia geral a gente já repetiu algumas vezes viu no quadro e depois a gente vai ser capaz de fazer uma implementação que respeita essa propriedade esse nome é Adriele vem do sobrenome dos autores que não são três pessoas apesar de ter três

letras tá o ave é uma pessoa só Adelson besc e Wesley é holandes então eles são autores soviéticos que publicaram um artigo em 1962 que eu tenho aqui a tradução peguei aqui para a gente dar uma olhadinha um algoritmo para a organização da informação Então tá aqui o Adelson besc e o lands tô descendo aqui no artigo a gente tem um exemplo de uma árvore Zinho um pouquinho maior do que a gente desenhou e que respeita as propriedades né então aqui vai conversar justamente aqui nessa figurinha ela não respeita essa propriedade de ter todos os

nós É mas aqui na Bíblia a gente tem né basicamente a mesma quantidade de nós que teria na água e a só que eles estão dispostos de uma maneira que a altura da árvore e diminui justamente porque aqui na beira gente tem uma árvore avl Então porque tá pegando aqui a raiz a esquerda a gente tem um dois três quatro cinco de altura certo olhando para essa folha mais profunda aqui e é direito a gente vai ter um dois três quatro e eu tem que ser vaga do Prado todos os outros nossos essa diferença entre

as alturas da sub-árvores a esquerda EA direita é chamado de fator de balanço então numa árvore avl a gente tem que o modo do fator de balanço ele é menor igual a 1 para finalizar essa primeira parte dos nossos estudos sobre a árvore avl Vamos provar que ela é de fato uma árvore balanceado então a gente viu no vídeo tá de rosto mais balanceado aquela árvore cuja altura é proporcional ao logaritmo da quantidade de elementos que tem aí na árvore né então ao hoje é o grande e o ambiente então a gente quer mostrar que

o fato de ter essa propriedade de que todos os nós são regulados implicam em que a água EA Vl tem que ser balanceado então uma forma de estabelecer uma relação entre a altura EA quantidade de elementos que estavam em nessa árvore a gente pensar qual que seria a altura máxima e uma árvore com n elementos poderia ter e uma outra maneira da gente vê se resultado que vai ser mais fácil a gente elaborar o nosso raciocínio é a gente pensar que na verdade ainda tem uma altura fixa e a gente quer encontrar qual que seria

um mínimo número de elementos ali naquela árvore para atingir essa altura e como é que a gente resolve isso então vamos começar a pensando que a gente tem uma árvore gente vai representar aqui por esse te e que ela tem uma altura h que essa nossa altura fixa tá então aqui tá a raiz da nossa árvore ó e aqui a esquerda vai ter assobiava e esquerda e enquanto a direita a gente vai ter assobiado e a direita dela tá bom Então essa é a nossa árvore que tem altura h e tem uma quantidade mínima de

elementos Zener e a sacada que a gente tem que ter aqui é perceber que a gente pode fazer uma construção recursiva dessa árvore porque repara só se aqui a gente tem a quantidade mínima de elementos para ter essa altura h então aqui a esquerda aí sistema subir a árvore com a quantidade mínima de elemento para ter também essa altura que assobiava e esquerda tem a gente não sabe ainda qual é e aqui é direita da mesma maneira a gente tem também a gostar de mim uma de elementos para ter alto É com que a árvore

é direita tem e que altura são essas né Então essas alturas não podem ser H porque a gente acabou de remover aqui o elemento da raiz então tem que ser no máximo h -1 e não pode ser H menos um dos dois lados né porque se as duas vocês duas subir a vão estiverem a altura em resumo não tem que não tá lidando com o número mínimo de elementos né já que elas poderiam ter uma diferença eu poderia ter uma conta menos um EA outra com H - 2 e ainda tá aí a respeitando a

propriedade da árvore avl então pra gente ter esse caso de elementos mínimos a gente vai ter justamente essa diferença uma delas vai ter altura h -1 e a outra vai ter altura h - 2 e elas são as mínimas que tem essa altura Então vamos dizer por exemplo que aqui a direita a gente tem a árvore mínima para h -1 e aqui a esquerda a gente tem a árvore mínima para H - 2 e assim sem nenhuma perda de generalidade né poderia ser h -1 a esquerda E H - 2 a direita tanto faz tá

mas a gente escolheu aquilo essa convenção então a gente sabe que essa quantidade de elementos que tem na água em PH a gente vai representar aqui com essa notação do módulo né Então essa aqui é a quantidade O que tem na árvore PH ela tem que ser igual a quantidade de alimentos que têm nessa árvore PH menos um mas a quantidade de alimentos que tem na árvore th - 2 que são as árvores com a menor quantidade de alimentos que têm essas alturas h -1 e h - 2 respectivamente e a gente não pode esquecer

de somar um no final que é esse único elemento aqui né a raiz da árvore quem está usando para ligar ao assobiado esquerda de subir ao e a direita th - 2 t h -1 então era só a gente consegue montar aqui uma pequena tabela da relação entre a altura com o tamanho da árvore né quantidade mínima de elementos para alcançar essa altura Então olha só o 0 e 1 foram triviais né os casos que a gente olho valores são bem óbvios E os outros casos a gente foi somando os dois casos anteriores como tá

aqui na expressão PH menos um mas th - 2 mais um certo então só o mais velho mais um a gente chega no dois depois dois mais um mais um ano chegou no quatro e quatro mais 2 mais 17 e assim vai tá assim sucessivamente então isso aqui tem uma associação bem natural com aquela sequência de Fibonacci né para quem já estudou um pouco de matemática é bem provável que você atende do contato com a sequência de Fibonacci ate que aquela sequência Justamente que é o próximo elemento né vai ser igual a soma dos dois

anteriores e ela começa a ver com 01 e assim vai só que a gente percebe é que esse fato é um faz com que essa nova sequência de tamanhos das Árvores ela seja maior do que a sequência de Fibonacci da gente pode escrever isso dessa maneira aqui ó que o tamanho da árvore pagar vai ser maior ou igual né a sequência de Fibonacci e eu botei aqui o maior ou igual porque ele tem esses casos em que elas são exatamente iguais né Eu e no comecinho e porque as observação lá nos ajuda é o nos

ajuda é a forma dos termos da sequência de Fibonacci ela já é bem conhecida se você resolver aquela forma de recorrência da sequência você vai chegar numa fórmula fechada que tem essa cara que é um sobre Raj cinco que multiplica um mais aí de 5 sobre 2 né eu levado ao índice eu e do termo da sequência - 1 - Red 5 sobre 2 também levado a e ciência então é uma casa bem feia mas que por incrível que pareça você vai dar um meu inteiro ali né então tem várias coisas em que esse número

aparece nas questões de proporção áudio não é algo que a gente vai entrar em detalhes aqui mas pode ser um exercício se você gosta da parte de matemática você estudar Como que você encontra fórmulas fechadas para reconhecer né se é possível ou não enfim como se consegue extrair informações de fórmulas de recorrência E no caso de fibonattis é bem relevante saber esse resultado aqui tá então a gente sabe que se o fio monat o HS no termo né eu tenho que representa a altura h vai ser igual a isso aqui o tamanho da nossa árvore

Ou seja a quantidade mínima de elementos que a gente vai colocar ali para atingir essa altura h ela tem que ser maior ou igual a esse termo aqui e aí a gente começa a fazer algumas análises em torno disso então a primeira é observar que esse termo aqui ele vai ser sempre menor ou igual a 1 porque porque como sh e já é maior do que um né aí já sabe que pôr para hz H1 é trivial aqui então está interessado em a gás maiores do que um Então como ele é a maior do que

um e esse termo aqui em módulo ele vai estar entre 0 e 1 a gente sabe que quando eu levar eu e aí se H seja qual for o h vai estar sempre ali entre 0 e 1 então como isso aqui vai ser no máximo um a gente fica na seguinte inequação então o tamanho da nossa árvore o th ali ele vai ser maior que ou igual a é um sobre raiz de 5 x esse primeiro termo aqui de um mais raiz de 5 sobre 2 elevado a h e tudo isso menos um Então se

esse tamanho era maior do que esse essa expressão aqui em que esse lado eu tô subtraindo uma coisa menor do que um né e multiplicando por uma outra menor do que um tão no final tudo é menor do que um se eu substituir por um quer dizer que eu tô tornando esse lado aqui ainda menor então é verdade QTH né o tamanho da nossa árvore que tem que ser maior do que todo esse lado quando o substituto do aquela parte por um pé acho que ela tá ficando ainda menor do que eu já tinha aqui

e o legal de tudo isso é que agora a gente vai conseguir encaixar o Oriente eo monte de finalmente Então senti passar esse menos um para o outro lado né A gente vai ficar com TN mais um tem que ser maior ou igual a 1 sobre a em cinco vezes é essa coisa aqui né uma Jardim 5 sobre 2 elevado H E aí para sempre ficar nossa escrita gente vai fazer o seguinte a gente vai chamar esse termo aqui nesse um mas aí de cinco sobre dois a gente vai chamar ele de Ah tá então

só uma a gente tem que sobre dois a gente vai ter a elevado a galinha índio aplicar um log na base ar dos dois lados da nossa inequação tá só que olha só desse lado você fica com o Gui na basear de que no próprio a elevado h e vezes esse um sobre as de cinco ali né então aqui está bem perto do resultado que a gente quer mas a gente conseguir e escrever isso utilizando algumas propriedades do logaritmo Então olha só pressionado direito aqui que a gente vai fazer pegar o lado esquerdo né então

ao invés de escrever como uma equação de maior igual vamos escrever como menor ou igual né trocando do lado é a melhor coisa que a gente percebe ali é que dá para você parar esse ar elevado H do 1 sobre raiz de 5 Então esse um sobre raios de cinco eu e é na verdade uma divisão por raiz de 5 né E a gente tem a propriedade do logaritmo que quando você tem a divisão você pode subtrair o algarismo do que tiver dividindo Então você tem aqui o logaritmo na base ar de raiz de 5

bom então isso aqui vai ser menor ou igual ao que a gente tem havido outro lado né o Aguiar de ter n + 1 e a gente vai pai quando a gente tem um número potenciação dentro do logaritmo eu e saio multiplicando o óleo certo então a gente vai ter aqui embaixo H vezes o óleo de asa basear que o homem de qualquer número na base dele mesmo vai ser igual a um Então a gente tem simplesmente a crack e agora isolando-o HQ desse lado a gente sabe que o hagah tem que ser no máximo

né E vai ser menor ou igual ao og a de TN mais um mais ou Aguiar de raiz de 5 então agora a gente lembra daquele conhecimento que eu te ensinei no vídeo sobre complexidade de algoritmos sobre a notação do a grande porque é uma notação que não se preocupa com constantes nem aditivos nem multiplicativos né que importa para a gente é a ordem de grandeza do crescimento dessa função então aqui a gente tem uma o tio né Isso aqui é constante a gente pode eliminar esse log de raiz de 5 na base ar tão

irrelevante para a gente e aqui a gente tem o resultado que a gente queria de ter uma altura que seja proporcional à quantidade de elementos que está ali na árvore né então o ano que a gente tá utilizando de uma base estranha né logo na base ar e Esse a é uma Jorge 5 sobre 2 mas a mudança de base logaritmo ele apenas uma multiplicação lá e como constante multiplicativo não importam para notação do a grande a gente chega o resultado de que H É de fato o grande do log de n em que n

é a quantidade de elementos que tiver ali na árvore está sendo representado aqui para gente porque esse é o módulo de TN né que a gente tá olhando ali para quantidade mínima de elemento que a gente conseguiria colocar numa árvore avl uma altura fixa H Então essa é uma parte que dá um pouquinho de trabalho né mas também não é muito complicado bom e o que colocar aqui porque eu sei que tem pessoas que estão estudando esses assuntos na faculdade né e é importante interessante você aprender essa base matemática também como está fazendo aí uma

ciência da computação engenharia de computação ou esses cursos mais voltados para a inteligência artificial se Acende dados Então é isso Pessoal esse vídeo ficando por aqui espero que você tenha entendido a ideia por trás de uma árvore avl e Como que essa propriedade de ter todos os nossos regulados implicam em árvore ser balanceado no próximo vídeo a gente vai olhar mais alguns detalhes de como que a gente pode inserir elementos ali na árvore e mantenha sempre essa propriedade Então a gente vai olhar um pouco com essa parte de rotação que eu comentei bem rapidamente aqui

nesse vídeo e também vamos fazer a implementação em código se você gostou do vídeo Não esqueça de deixar o seu like nem se inscrever aqui no canal para dar aquele apoio ao nosso trabalho muito obrigado e até a próxima