aula06

Prévia do material em texto

6ºAula
ÁRVORES AVL
Objetivos de aprendizagem
Ao término desta aula, vocês serão capazes de: 
• compreender como funciona uma Árvore AVL;
• entender um processo de inserção de elementos em uma Árvore AVL
Olá,
Nesta aula, vamos prosseguir o estudo sobre as Árvores. 
Mostraremos um tipo de árvore binária, que tem uma disciplina 
de balanceamento ótimo para manter o processo de busca 
excelente em todos os nós da árvore. Trata-se das Árvores AVL, 
que veremos nesta aula.
Leiam atentamente esta aula e façam os exercícios. Se 
enfrentarem alguma dúvida, estaremos a sua disposição na área 
do aluno.
Bons estudos!
39
Estrutura de Dados II 38
1. 
Seções de estudo
O que é uma árvore AVL
2. Inserção em uma AVL
1 - O que é uma árvore AVL
Antes de definirmos o que é uma árvore AVL, temos que 
ressaltar um problema que pode ocorrer nas árvores. As 
árvores, na medida em que os dados são inseridos e removidos, 
podem se tornar desbalanceadas, ou seja, ter mais elementos 
de um lado da árvore em relação ao outro lado. 
A seguir mostraremos o exemplo de uma árvore binária 
desbalanceada. Vejam:
Uma árvore desbalanceada pode causar problemas de 
desempenho na busca, pois o processo de busca pode ser mais 
demorado de um lado. No exemplo, se quisermos procurar o 
elemento de número 70, teremos que percorrer vários nós em 
uma árvore, prejudicando o tempo de execução.
A figura a seguir mostra outra árvore, com os mesmos 
elementos que estão na figura anterior, mas dispostos de uma 
forma mais equilibrada e balanceada. Melhor assim, não é 
mesmo?
 Assim, devemos procurar uma forma de balancear 
a árvore, procurando manter um equilíbrio entre os 
elementos dela. Podemos adotar como primeira solução 
manter uma árvore ou uma quase completa, permitindo o 
preenchimento de um nível mais abaixo quando todos os 
espaços dos níveis anteriores estiverem completos. Caso 
contrário, temos que equilibrá-la.
O problema disso é o tempo de execução, que pode 
ser enorme, pois operações de movimentações de dados 
podem ser necessárias a cada nova inserção na árvore. 
Assim, chegamos ao dilema: não adotar alguma otimização 
qualquer, deixando as árvores desequilibradas, porém 
obtendo desempenho nas alterações ou adotar uma 
árvore completa, ganhando desempenho na busca, porém 
perdendo desempenho nas inserções e remoções.
Em 1962, dois pesquisadores da então União 
Soviética, Georgy Maximovich Adelson-Velsky e Evgenii 
Mikhailovich Landis, desenvolveram um meio-termo. 
Uma forma de equilibrar a árvore quando realmente é 
necessário. Assim, surgiu a Árvore AVL (AV de Adelson-
Velsky e L de Landis). 
Figura 4 - Georgy Maximovich Adelson-Velsky. Fonte: Disponível em: < http://www.
computerhistory.org/chess/stl-430b9bbe4e16c/ >. Acesso em: 16 set. 2018.
40
39
Figura 5 - Evgenii Mikhailovich Landis.Fonte: Disponível em: < https://commons.
wikimedia.org/wiki/ F i l e : % D 0 % 9 5 % D 0 % B 2 % D 0 % B 3 % D 0 % B 5 % D 0 % B D % D 0 % B 8 
p e g>. Acesso em: 16 set. 2018.
Uma árvore AVL segue as seguintes regras:
1. Uma árvore AVL é uma árvore de busca binária.
2. Uma árvore AVL nem sempre é uma árvore 
completa (mas toda árvore completa é uma AVL).
3. Todos os nós presentes em uma árvore AVL 
possuem um fator de balanceamento, que consiste 
na diferença das alturas entre a subárvore direita e a 
subárvore esquerda do seu nó.
4. Todos os nós presentes em uma árvore AVL devem 
ter um fator de balanceamento menor igual a 1. Ou 
seja, a diferença das alturas da subárvore direita e 
esquerda do nó deve ser menor igual a 1.
5. Se em um caso de inserção ou remoção, algum nó 
passar a ter o seu fator de balanceamento maior que 
1 (ou seja, a diferença das alturas da subárvore direita 
e esquerda do nó passar de 1) será necessário um 
rebalanceamento, ou seja, um reordenamento dos 
nós para que a propriedade principal de uma AVL 
se mantenha.
eles. Fonte: MENA-CHALCO, 2014.
Como você viu nas propriedades mostradas, um dado 
muito importante é o fator de balanceamento. Esse fator 
veremos a seguir:
1.1 - Fator de balanceamento
Para decidir se deve ser feito ou não um balanceamento 
na árvore, cada nó da árvore AVL possui um fator de 
balanceamento, que consiste na diferença da altura entre a 
subárvore esquerda com a subárvore direita do nó.
 Supondo que o valor da altura da subárvore esquerda 
do nó seja chamado de HE e o valor da altura (número de 
níveis que existem em uma árvore) da subárvore direita do nó 
seja chamado de HD. O fator de balanceamento é dado pela 
seguinte fórmula:
FB(No) = HE - HD
Como o valor desse fator não pode ser maior igual a dois, 
a faixa de valores aceito para um padrão de balanceamento 
é -1, 0 e +1. Cada valor nos diz alguma coisa a respeito da 
árvore, vejamos:
• Se o fator de balanceamento for 0, a altura das duas 
subárvores são iguais.
• Se o fator de balanceamento for +1, significa que a 
subárvore esquerda é maior.
• Se o fator de balanceamento for -1, significa que a 
subárvore direita é maior.
respectivo fator de balanceamento. Fonte: MENA-CHALCO, 2014.
Com isso em mente, agora, vamos para próxima seção 
ver como funciona o processo de inserção em uma AVL.
2 - Inserção em uma AVL
Nesta seção, vamos abordar como funciona o processo 
de inserção de elementos em uma AVL. Esse processo segue 
os seguintes passos lógicos:
1. Busca o elemento para verificar se foi inserido.
2. Caso não tenha encontrado, inserimos o nó na 
árvore, da mesma forma que explicamos com as 
árvores de busca binária comum (veja a aula 05 para 
saber mais detalhes desse processo).
3. Ajusta o fator de balanceamento em todas os nós 
da árvore.
4. Caso tenha algum nó com fator de balanceamento 
-2 ou 2, balanceamos a árvore.
Os três primeiros passos são simples. A busca e a 
inserção, que são as mesmas da árvore de busca binária, foram 
abordadas nas aulas 04 e 05 desta disciplina. O processo de 
atualização do fator de balanceamento consiste em atualizar 
nós ancestrais do novo nó o valor deste fator, de forma a 
refletir a nova estrutura da árvore.
Caso algum nó ancestral passe a ter o valor do fator de 
41
Estrutura de Dados II 40
balanceamento -2 ou 2, temos a necessidade de realizar o 
balanceamento da árvore. Esse balanceamento consiste em 
rearranjar os nós, de forma que a árvore AVL volte a ter a 
sua condição fundamental: A diferença da altura entre as duas 
subárvores, de qualquer nó da árvore, não deve passar de 1.
Para fazer esse rearranjamento fazemos algumas 
operações que são denominadas de rotações, pois estamos 
“girando” a ordem dos nós da árvore. Em uma árvore AVL 
podemos aplicar quatro tipos de rotações:
• Rotação à esquerda.
• Rotação dupla esquerda.
• Rotação à direita.
• Rotação dupla direita.
Vamos agora explicar o em que consiste essas operações.
Rotação à esquerda
Consiste em girar os nós da árvore para a esquerda. 
Considere a seguinte árvore, onde A é a sua raiz, B é o seu 
filho direito e C o seu neto (filho direito de B). Como ela 
está desregulada precisamos regular. A rotação a esquerda 
funciona da seguinte maneira:
• B passa a ser a nova raiz, rebaixando A para ser o seu 
filho esquerdo.
• A herda a subárvore esquerda de B, passando a ser 
o seu pai.
A imagem a seguir mostra o resultado dessa rotação:
Vamos agora mostrar mais uma rotação.
Rotação à direita
A rotação à direita é similar a rotação à esquerda, com 
a diferença de que invertemos a ordem de rotação para a 
direita. Assim, supondo uma árvore onde A é a sua raiz, B é 
o seu filho esquerdo e C o filho esquerdo de B, faremos os 
seguintes passos para fazer o balanceamento da árvore:
• B passa a ser a nova raiz e A é rebaixada à condição 
de filho direito de A;
• C passa a ser o novo pai da subárvore direita de B;
• C continua sendo o filho esquerdo de B.
Mas, existem situações em que uma rotação simples não 
resolve. Vamos abordar isso a seguir. Vejam:
Rotação dupla esquerda
Para abordarmos essa modalidade de rotação, vamos 
para um exemplo: suponhamos uma árvore dispostada 
seguinte forma:
Tentamos fazer uma rotação à esquerda, mas não resolve:
Figura 11 - Árvore após uma tentativa de balanceamento.Fonte: Acervo Pessoal.
42
41
Então, o que aconteceu? A explicação é que o filho 
direito de A tem um fator de balanceamento negativo, 
prejudicando o nosso balanceamento. Assim, a situação 
dessa árvore não é a ideal para executar a rotação à esquerda. 
Precisamos fazer alguma coisa para que seja possível a 
rotação à esquerda.
Vamos tentar uma coisa: Isolamos a subárvore direita 
de A e fazemos uma rotação à direita entre os nós B e C.
Figura 12 - Rotação dos nós B e C. Fonte: Acervo Pessoal.
Agora, podemos ver que estamos em uma situação 
similar a aquela árvore que mostramos no exemplo de 
rotação à esquerda. Assim, fazemos a rotação à esquerda. 
Como podemos ver, a operação vai dar certo e a àrvore 
voltará ao seu equilíbrio. 
Acervo Pessoal.
Rotação dupla direita
A rotação dupla direita é similar a rotação dupla 
esquerda. Ela é usada em casos em que a rotação à direita 
não resolve por si só. A imagem a seguir, mostra uma árvore 
desbalanceada. Tentamos fazer a rotação à direita, mas ela 
não resolve. Vejam:
Assim, fazemos uma rotação à esquerda para corrigir o 
filho esquerdo da raiz. Fazendo isso, faremos uma rotação à 
direita na raiz. Agora o problema está resolvido.
no momento (iii). Fonte: Acervo Pessoal.
43
Estrutura de Dados II 42
Bem, já sabemos os tipos de rotações. Mas em quais 
situações aplicamos essas rotações?
Para isso, precisamos saber de algumas convenções:
• Na AVL temos um nó inserido chamado de q.
• Se a árvore deixou de ser balanceada temos um nó 
p, que é o nó mais próximo das folhas da árvore, 
que deixou de ser balanceada.
• Desse nó p, temos duas estatísticas, sendo HE(p), 
que é a altura da subárvore esquerda de p e HD(p), 
que é a altura da subárvore direita de p.
• A diferença em módulo das alturas das duas 
subárvores será sempre 2, devido a natureza da 
AVL.
Das estatísticas HE(p) e HD(p), temos dois casos que 
veremos a seguir.
Caso 1: HE(p) > HD(p)
Nesse caso, a subárvore esquerda é maior que a 
subárvore direita. Precisamos então, colocar nós na subárvore 
direita para equilibrar. Mas, precisamos saber se uma rotação 
simples resolve. Para isso, vemos um filho esquerdo u, que é 
diferente do nó inserido q. Desse nó u, verificamos as alturas 
das subárvores esquerda e direita, gerando os números HE(u) 
e HE(p).
Comparamos esses dois valores. Se HE(u) > HD(u) 
significa que a subárvore esquerda de u é maior, e deduzimos 
que o novo nó pertence a subárvore esquerda de u. Nesse 
caso, uma rotação à direita simples resolve.
Mas, se HD(u) > HE(u) significa que a subárvore direita 
de u é maior, e o novo nó q é descendente de v, que é o 
filho direito de u. Assim, uma rotação simples não resolveria. 
Portanto, teremos que fazer uma rotação dupla direita (em 
relação a raiz p) para balancear a árvore.
Caso 2: HD(p) > HE(p)
Nesse caso, a subárvore direita é maior que a subárvore 
esquerda. Assim, temos que colocar nós na subárvore 
esquerda para retomarmos o equilíbrio da árvore. Da mesma 
forma que no caso 1, procuramos um filho direito z, que é 
diferente de q.
Com o nó z coletado verificamos a altura das duas 
subárvores, gerando as estatísticas HE(z) (altura esquerda) 
e HD(z) (altura direita). Com isso, comparamos esses dois 
números.
Se HD(z) > HE(z) deduzimos que a altura da subárvore 
direita de z é maior que a subárvore esquerda de z. Nesse 
caso, deduzimos que q pertence a subárvore direita de z (T3). 
Com isso, deduzimos que uma rotação simples à esquerda 
em relação a raiz p resolve.
Mas, se HE(z) > HD(z) deduzimos que a altura da 
subárvore esquerda de z é maior que a subárvore direita 
de z. Assim, deduzimos que z possui um filho esquerdo 
y, que por sua vez é pai de q. Como a subárvore esquerda 
de z é maior, precisamos regular ela para fazer a rotação à 
esquerda. Portanto, fazemos uma rotação dupla à esquerda 
para resolver o problema.
 
Com isso, encerramos a nossa aula. Esperamos que tenha 
sido proveitoso para vocês. Na próxima aula, discorreremos 
sobre árvores B. Até lá!
Retomando a aula
Chegamos ao m da nossa se ta aula. Vamos 
relembrar o que estudamos?
44
43
1 - O que é uma árvore AVL
Nesta seção, vimos que uma árvore AVL é uma árvore 
binária, onde todos os nós presentes em uma árvore AVL 
devem ter um fator de balanceamento menor igual a 1. 
Ou seja, a diferença das alturas das subárvores direita e 
esquerda do nó deve ser menor igual a 1. E, se em um 
caso de inserção ou remoção, algum nó passar a ter o seu 
fator de balanceamento maior que 1 será necessário um 
rebalanceamento, ou seja, um reordenamento dos nós para 
que a propriedade principal de uma AVL se mantenha.
2 - Inserção em uma AVL
Nesta seção, aprendemos como se faz uma inserção 
em uma árvore AVL. Vimos os tipos de rotações que são 
feitas para equilibrar uma árvore AVL. São elas: Rotação 
à Esquerda, Rotação Dupla Esquerda, Rotação à Direita 
e Rotação Dupla Direita. Também aprendemos em quais 
situações devemos aplicar uma rotação ou outra.
CORMEN, Thomas H.; et. al.. Algoritmos: teoria e 
prática. Rio de Janeiro: Campus, 2012.
KNUTH, Donald Ervin. The art of computer programming. 
3. ed. Amsterdam: Addison-Wesley, 1998.
SZWARCFITER, Jayme Luiz; MARKENZON, 
Lilian. Estruturas de dados e seus algoritmos. 2. ed. Rio de Janeiro: 
LTC, 1994.
TENENBAUM, Aaron M.; AUGENSTEIN, Moshe 
J.; LANGSAN, Yedidyah. et al. Estruturas de dados usando 
C. São Paulo: Pearson Makron Books; São Paulo: Makron 
Books do Brasil; São Paulo: McGraw-Hill, 2013.
ZIVIANI, Nivio. Projeto de algoritmos: com 
implementação em PASCAL e C. 3. ed. São Paulo: Cengage 
Learning, 2011.
Vale a pena ler
BARANAUSKAS. José Augusto. Árvores AVL Árvores 
AVL. USP, s.d. Disponível em: <http://dcm.ffclrp.usp.
br/~augusto/teaching/aedi/AED-I-Arvores-AVL.pdf>. 
Acesso em: 17 set. 2018.
Vale a pena acessar
ROMAN, Norton T. Estrutura de Dados - Aula 21 - 
Árvores AVL. Univesp, 2017. Disponível em: < https://
www.youtube.com/watch?v=YkF76cOgtMQ>. Acesso 
em: 19 set. 2018. 
Vale a pena assistir
Vale a pena
HARGROVE, John. The AVL Tree Rotations Tutorial. 
2007. Disponível em: <https://www.cise.ufl.edu/~nemo/
cop3530/AVL-Tree-Rotations.pdf>. Acesso em: 19 set. 2018. 
MENA-CHALCO, Jesús P. Árvores Adelson-Velskii e 
Landis. UFABC, 2014. Disponível em: <http://professor.
ufabc.edu.br/~jesus.mena/courses/mc3305-2q-2015/
AED2-10.pdf >. Acesso em: 17 set. 2018.
SOUZA, Jairo Francisco de. Árvores AVL. UFJF, 
2009. Disponível em: <http://www.ufjf.br/jairo_souza/
files/2009/12/5-Indexa%C3%A7%C3%A3o-Arvore-AVL.
pdf>. Acesso em: 17 set. 2018.
GALLES, David. AVL Tree Visualization (Simulador 
de Árvore AVL). USF, s.d. Disponível em: <https://www.
cs.usfca.edu/~galles/visualization/AVLtree.html>. Acesso 
em: 15 set. 2018. 
Minhas anotações
45