[Música] Olá pessoal bem-vindos ao curso de estrutura de dados meu nome é norto esse curso também ministrado pelo Professor Luciano A aula de hoje a gente vai tratar de árvores avl bom até agora a gente tava brincando com árvore binária e árvore an Ária e tudo mais vamos voltar à árvore binária de busca certo nós vimos que o quê a ordem de inserção dos elementos na árvore vai vai determinar a forma dela ela pode ficar bonitinha ou virar uma lista ligada Claro tô pegando exemplos mais extremos mas ainda assim pode acontecer certo e o que
é mais importante isso aqui era diferença entre ela se comportar como numa busca binária ou numa busca sequencial ou seja uma busca rápida e uma busca lenta e nós queríamos isso certo então balanceamento é muito importante mas muito importante nisso só que um balanceamento perfeito ele é computacionalmente caro e aí nós vamos à máxima certo o o bom é inimigo do ótimo e vice-versa o ótimo é inimigo do bom por que que eu preciso do perfeito quando eu posso ter um bom Balan finamento certo então o que que eu vou fazer uma alternativa é nada
e aí veio o teorema Dirty Harry você está com sorte hoje você está se sentindo com sorte hum não sei ou você afroa ali não quero o ótimo e vamos para o bom ou seja tudo bem tudo bem tá desbalanceado um pouquinho não tem problema certo que que isso significa a gente já vai ver certo e que algoritmo é feito para isso nós temos o de Adson V kandas ou seja avl são as árvores avl que eu já tinha falado em aula anterior já tinha só citado né Tudo bem então o que que é uma
uma árvore avl ela é uma árvore de busca binária só que balanceada com relação à altura da suas subárvores certo o que que isso significa significa que na avl você verifica a altura das subárvores da esquerda e da direita de Cada nó e essa diferença não pode ser maior do que mais ou menos um como mais ou menos um se você vai a altura de uma menos a altura da outra ou dá zero ou dá um ou dá men-1 conforme a ordem que você subtraiu não pode o módulo não pode passar de um não pode
ser dois essa é uma árvore avl certo essa diferença a essa diferença a dá o nome de fator de balanceamento do nó certo então você pode ver é a altura da árvore esquerda menos a altura da árvore direita Lembrando que a altura de um de um nó é a é o comprimento do maior caminho dele a uma folha certo bom Como eu disse o valor fator de balanceamento ele é calculado a cada nó Cada nó você vai ver certo e para cada nó a diferença de altura entre a subárvore da esquerda e da direita não
pode passar desse mais ou menos um certo um detalhe que eu não mencionei é que a altura de uma árvore vazia é men1 a altura de uma árvore só com a raiz é zero ela é uma folha certo uma á vazia altura é men1 com isso a cada nó eu tenho que armazenar uma de duas informações ou eu guardo o fator de balanceamento isso nós vamos ver quando a gente ver a implementação dessa árvore ou alternativamente a altura do nó você não guarda os dois pode até guardar se quiser mas não precisa um dos dois
se tem que guardar certo então vamos brincar aqui Essas são árvores avl ou não vamos ver a primeira bom aqui eu marquei a altura de cada um dos Nós esse aqui está balanceado esses estão obviamente balanceados não tem nada embaixo Mas esse daqui tá balanceado vamos ver a A Árvore esquerda subárvore esquerda altura da subárvore esquerda menos a da direita é 0 menos 0 dá zer então ele está esse daqui tá balanceado vamos ver a altura da subárvore da esquerda é 1 a da direita é zero 1 Men 0 é 1 tá balanceado Isso é
uma avl e essa daqui vamos ver aqui zero com zero esse aqui tá balanceado zer quanto vai aqui não existe aqui lembre uma árvore vazia men1 z0 com men1 se faz dier esse menos aqui ele vira mais um tá balanceado esse aqui 1 Men 1 dá z0 tá toda balanceada essa também é uma velha vamos trazer essa para cá agora aqui essa aqui eu já vi que é uma Vel e essa Qual que é a diferença entre elas ó só incluí esse 18 Vamos ver aqui nós já vimos esse pedaço tava balanceado e aqui z0
com men1 a diferença dá 1 tá balanceado e aqui 1 com os1 dá no 1 - 1 - 1 dá 2 e faz o contrário -1 -1 - 2 Dan no aqui tá desbalanceado ou seja não é uma uma árvore evl porque o 23 está desbalanceado Olha só que coisa nesse caso específico frisando a inserção de um único elemento foi suficiente para fazer com que ela perdesse o balanceamento dela ela perdesse o equilíbrio ela deixou de ser avl só por causa desse sujeito aqui certo uma inserção pode fazer com que o fator de balanceamento de
um nó Vire mais ou menos do por pode fazer Porque dependendo de onde inserir Não mexe em nada mas dependendo de onde inserir pode fazer sim ou ele tava balanceado certo balanceado significa que ele tava no máximo um se eu inserir ele pode ter ficado dois esse aqui é um problema só que tem um detalhe interessante veja o desbalanceamento quando eu inseri aqui certo ele só ocorreu nesse pedaço aqui Aqui tá preservado porque eu não V mexi nada lá então basicamente o que que acontece somente os nós no caminho do ponto de inserção até a
raiz é que podem ter sofrido o o o desbalanceamento por quê porque eles podem ter mudado sua altura aqui nesse caso esse aqui com certeza mudou altura mas se ele tivesse um outro filho aqui inserir esse aqui do lado não teria mudado em nada sua altura e nada teria mudado certo então todo mundo do do ponto de inserção até a raiz Inclusive a raiz pode ter mudado sua altura então o que que eu faço após a inserção eu volto até a raiz nó por nó atualizando as alturas é isso que eu faço se um se
um novo fator de balanceamento para algum desses nós no caminho for 2 ou os2 eu ajusto a árvore como rotacionando em torno do nó desbalanceado e esse foi o truque que esses caras fizeram como que eu rotaciono vamos lá nós temos dois tipos de rotação ou a esquerda a esquerda significa o quê ó tá aqui eu giro para cá veja que aqui é o pai do x quando eu giro esse aqui o o y é que passa a ser o pai do X certo se o y é o pai do X o Beta que era
filho do Y passa a ser filho do X eu basicamente rotacione assim essa é a esquerda e a direita à direita é outra coisa eu pego aqui rotaciono aí esse sobe e o filho dele porque esse aqui passa a ser filho desse e o filho dele é adotado por esse aqui então essa rotação esquerda e rotação à direita certo então vamos olhar aqui num exemplo aqui o ponto de desequilíbrio era esse nó aqui o fator de balanceamento dele era dois então o que que eu vou fazer rotaciono o nó com o filho dele no caminho
até onde hve a inserção e girei Ó daqui eu puxei para cá e Eis que o 20 veio para cá o 23 caiu como filho da direita o 18 Manteve aqui e ficou a Vl Como assim ó 0 zer dá zer o um dá zero todo mundo ficou balanceado ficou bonito essa rotação certo vamos ver isso aqui de maneira mais geral vamos dizer eu ter essa árvore aqui é uma árvore avl certo aqui eu tenho subárvore de altura h se essas subárvores são de altura h o nó pai delas é de altura h + 1
aqui é uma subárvore de altura h esse aqui poderia ser h + 1 se não houvesse essa aqui que h + 1 então ele H + 2 lembre-se que é a altura o caminho mais longo Então beleza o que que pode acontecer se eu inserir um elemento em alfa bom se eu insiro um elemento em alfa eu posso aumentar essa altura o que aumentaria aqui e obviamente aumentaria aqui veja na cadeia toda aqui eu aumentei a altura posso porque não necessariamente Depende de onde dependendo de onde eu inseri ele simplesmente choveu no molhado já tinha
um do lado e não não mexu na altura Ótimo então e aqui como é que ficou tá balanceado ó aqui h + 1 - H dá 1 H + 2 - H dá no dá do não está balanceado Criei um ponto de desbalance quebrei o balanceamento em X então o que que eu vou fazer faço a rotação à direita pego ali e quando eu faço isso Ó eu simplesmente girei aqui esse passou a ser filho desse e esse pai desse pronto as alturas era H aqui h+ 1 h h aqui ficou h + 1 h
+ 1 aqui H + 2 dá zer e zero ou seja nessa brincadeira a árvore se Manteve balanceado certo a gente pode dizer que pensar que ergueu a parte que tinha ficado maior bloquei ficou maior eu ergui ela um pouco para manter o equilíbrio então inserções na parte mais externa da árvore você resolve com com rotações simples nós vimos uma aqui qual que é a parte mais externa da árvore na subárvore esquerda do filho à esquerda do nó desbalanceado sempre tomando em conta o nó Balanceado como a raiz da da coisa porque ele é quase
que literalmente a raiz do nosso problema certo ou aqui na subárvore direita do filho direito desse nó essas aqui você resolve com uma rotação à esquerda ou Ah é à direita perdão ou a esquerda conforme for certo mas e quando a inserção for na parte mais interna ou seja aqui na subárvore direita do filo esquerdo ou aqui na subárvore esquerda do Fio direito Pois é o que que acontece nessa hora Hum vamos testar vamos ver vamos voltar a nossa ave Elzinha lá que eu tava lá né o que que acontece eu coloco aqui Note que
é um daqueles nossos problemáticos na parte interna certo tomando-se o o a raiz lá como base cria aí o que que vai acontecer o que aconteceu foi que eu Possivelmente de novo é possivelmente aumentei essa altura que aumentei aqui aumentei aqui e criei esse desbalanceamento aqui quebrei o balanceamento em x Ah nós vimos o quê quebrou o balanceamento aí rotaciona onde aqui não esse cara não tem nada a inserção foi aqui rotaciona assim então vamos rotacionar certo tá ali rotaciona pra direita e t rotacione Nossa agora resolveu não dá uma olhada h+ 1 Men H
dá 1 Então esse aqui tá chique ó mas ele tá vermelho ah pintei errado né não é porque ele era aquele eu só rotacione calma aí e aqui D nos rapaz ó H - h+ 2 vira -2 o que eu fiz simplesmente foi só o ponto de de de de desequilíbrio para cá antes era x agora y o que eu faço ó rotaci na esquerda mas daí eu devolvo pro x eu fico assim não não vai dar certo não vai dar certo nesse caso aqui o que que eu posso fazer vamos olhar a estrutura do
Beta mais com mais calma MMO foi com mais calma foi aqui que eu inseri a coisa então vamos olhar ele tem uma raiz e tem duas subárvores potencialmente certo se a altura dele antes era h + 1 essas subárvores dele ou tem altura h ou h - 1 ou as duas t h ou uma delas tem H -1 Ah e se as duas não podem ter h -1 não porque se as duas t h -1 ele seria h não seria h + 1 uma delas pelo menos tem H então eu sei isso sobre elas certo
que que eu vou fazer em vez de fazer aquela rotação lá em cima rotaciona aqui à esquerda tá vendo eu pego aqui esse cara e giro para cá mesma coisa esse vem para cá esse vira filho desse e esse aqui que era filho desse é dado pelo y e fica assim rotacione e as alturas aqui era H ou h - 1 com H tudo bem aqui é h + 1 aqui era H ou H -1 mas essa domina H + 2 h + 3 não mudei nada não não não tirei o o o o o
desbalanceamento sabe não devolvi o balanceamento mas calma não terminei também girei aqui pra esquerda agora eu giro aquele ali pra direita giro PR lá Pronto agora olha a mágica acontecendo ó H então aqui é h+ 1 aqui é maior é h h+ 1 olha h+ 2 certo a diferença entre entre esses aqui ou é zero ou é um ou é zer ou é um então esses dois estão balanceados e esse aqui é zero esse aqui tá balanceado virou uma avl então com duas rotações vemos ela PR avl certo então as as quando as inserções são
nessa parte mais externa da árvore aí quando isso acontece a rotação simples funciona seja pra esquerda ou pra direita Depende de onde você inseriu quando ela na parte mais interna assim aí você precisa de duas duas rotações seja esquerda direita ou direita esquerda nca é direita direita de esquerda esquerda esquerdao direito ou ou direito esquerdao são as rotações duplas certo então para resumir aqui como que vai funcionar a gente vai fazer uma rotação à esquerda se o nó for inserido na subárvore direita do filho à direita então aqui o nó sub árvore direita do filho
à direita que eu faço essa rotação devolvi o equilíbrio vou fazer uma rotação à direita se o nó for inserido na subárvore ES Esquerda do filho à esquerda Então tá aqui o filho à esquerda inseri o cara aqui que eu faço quebrei o o o equilíbrio aqui devolvo o equilíbrio Só se eu quebrei né faz a rotação por favor fique bem claro certo terminei o equilíbrio devolvo assim e quando o nó for inserido nas partes mais centrais bom se ele for inserido no filho à direita da subárvore no filho à direita da da da desculpe
no no filho à direita da subárvore da esquerda que que eu faço eu faço uma rotação à esquerda traz subindo esse cara aqui que tá sendo problemático subo e uma rotação à direita com isso eu devolvo o equilíbrio certo então se ele foi inserido aqui gira aqui nesse daqui e gira aqui nesse daqui esse o que aconteceu foi que ele foi inserido na sub no como filho ah da esquerda do do da raiz da subárvore da direita teu Neto à esquerda do filho da direita faz a rotação direita e esquerda pega esse aqui devolve o
c para cá e pega esses dois devolve para cá é assim que você trata da avl certo aí vocês podem est se perguntando e o código para isso tudo aqui certamente não é tão simples mas também não é tão complicado quanto possa aparecer mas também não cabe agora na próxima aula nós vamos ver o código para essa árvore avl e é importante que vocês tenham entendido quando usar essa rotação até a próxima C [Música]