Balanceamento de árvore

Prévia do material em texto

Balanceamento de árvore
APRESENTAÇÃO
O uso de árvores como estrutura de dados requer alguns cuidados. Ao se usar uma árvore binári
a, pode acontecer que, à medida que os nós cresçam, o tempo computacional para encontrar alg
um nó aumente. A solução para esse problema computacional é a árvore criada em 1962, por Ad
elson, Velskii e Landis - a AVL - que é uma árvore balanceada.
Nesta Unidade de Aprendizagem, você vai compreender o que é essa árvore, que tipo de proble
ma ela soluciona e como é possível, através de rotações, balancear uma árvore.
Bons estudos.
Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:
Identificar as definições de árvores AVL.•
Reconhecer os conceitos de árvores AVL - rotação direita.•
Definir os conceitos de árvores AVL - rotação esquerda.•
DESAFIO
Sua equipe de desenvolvimento está trabalhando com a equipe de redes de computadores da em
presa em você trabalha. O problema apresentado é o seguinte: vocês precisam mapear hierarquic
amente todos os equipamentos de conexão entre as redes existentes na empresa, de tal forma que 
a rede fique balanceada.
Para o estudo em questão, Marcelo, que é o gerente de infraestrutura, definiu alguns conceitos in
erentes a essa rede: 
- Cada equipamento está ligado a um ou dois outros equipamentos. 
- Cada equipamento tem um número vindo de fábrica.
A rede balanceada tem o seguinte conceito: partindo-se do roteador principal, a diferença entre a 
quantidade de roteadores pelos quais se passa até chegar a um equipamento final da sub-rede da 
esquerda e da direita é de, no máximo, 1.
Você precisa usar seu conhecimento de desenvolvedor para definir uma estrutura que: guarde as 
informações dessa rede e auxilie Marcelo a analisar onde está o desbalanceamento da rede, se ex
istir, e como reorganizá-la.
INFOGRÁFICO
As rotações são maneiras de balancear árvores binárias de busca e de torná-las árvores AVL. De
ntre elas, existe a rotação simples, que pode ser feita para a direita e para a esquerda.
A rotação simples à direita acontece quando, ao inserir um nó, sua posição é à esquerda da subár
vore da esquerda. Já a rotação simples à esquerda deve ser realizada quando, na inserção de um 
nó, sua posição é à direita da subárvore da direita e isso gera um desbalanceamento.
CONTEÚDO DO LIVRO
Ao se inserir nós em uma árvore binária, pode ser que aconteça, de acordo com a ordem de inser
ção destes, que a árvore fique desbalanceada. Nesses casos, é preciso que seja dada atenção espe
cial focada ao balanceamento dessa árvore.
No capítulo Balanceamento de árvore, da obra Estrutura de dados, você vai estudar o processo 
para que se tenha uma árvore binária balanceada, ou seja, uma forma de se realizar balanceamen
to de árvores utilizando as rotações simples e duplas.
Boa leitura. 
ESTRUTURA 
DE DADOS
Marcela Santos
Balanceamento de árvore
Objetivos de aprendizagem
Ao final deste texto, você deve apresentar os seguintes aprendizados:
  Identificar as definições de árvores AVL.
  Reconhecer os conceitos de árvores AVL: rotação à direita.
  Definir os conceitos de árvores AVL: rotação à esquerda.
Introdução
O uso de árvores como estrutura de dados requer alguns cuidados. Ao usar 
uma árvore binária, pode acontecer de, à medida que os nós cresçam, o 
tempo computacional para encontrar algum nó aumente. A solução para 
esse problema computacional é a árvore criada em 1962, por Adelson, 
Velsky e Landis, chamada de árvore AVL, que é uma árvore balanceada.
Neste capítulo, você vai compreender o que é essa árvore, qual pro-
blema ela soluciona e como é possível, por meio de rotações, balancear 
uma árvore.
Definições de árvores AVL
Ao inserir nós em uma árvore binária, pode ser que aconteça, de acordo com 
a ordem de inserção dos nós, de a árvore fi car desbalanceada.
O que diz se uma árvore é balanceada ou não é a altura das subárvores à 
esquerda e à direita. Vamos tomar a seguinte sequência de números e formar, 
com eles, uma árvore binária: 1, 2, 3 e 4.
A imagem a seguir mostra a inserção de cada um dos nós.
1 1 1 1
2 2 2
4
3 3
A árvore resultante dessa inserção de nós é uma árvore desbalanceada e 
a altura da subárvore à direita é muito maior, nesse caso, que a da esquerda 
que nem existe. Mas por que ter uma árvore desbalanceada é um problema?
O problema acontece com relação ao custo computacional quando se deseja 
buscar um nó. Quanto mais nós, quando inseridos em uma árvore binária, 
maior a quantidade de níveis da árvore e mais custoso computacionalmente.
Em 1962, os soviéticos Adelson Velsky e Landis criaram o conceito de 
árvore AVL. Basicamente, essa árvore é uma árvore binária balanceada, 
sendo que a altura da subárvore à direita e à esquerda diferem, no máximo, 
em uma unidade.
Para que isso aconteça, a inserção de um nó na árvore acarreta a verificação 
do balanceamento e a tomada de decisão sobre como agir caso a árvore fique 
desbalanceada após essa inserção.
Para saber mais sobre árvores AVL, acesse o link abaixo 
ou código ao lado.
https://goo.gl/EbQkkf
Balanceamento de árvore2
Antes de entrarmos no processo de inserção em uma árvore AVL, vamos 
avaliar alguns conceitos importantes, como níveis dos nós de uma árvore, 
altura de um nó e fator de balanceamento (FB).
A
B C
D E
F NÍVEL 4
NÍVEL 3
NÍVEL 2
NÍVEL 1
De posse da árvore e com os níveis de cada nó, vamos calcular a altura de 
cada subárvore. A altura é dada pelo maior nível de cada subárvore, como, 
por exemplo, o nó D, cujo maior nível de nós da subárvore à esquerda é 1, 
portanto, a altura da subárvore à esquerda (AE) é 1, enquanto à direita (AD) 
é 0. Observe que quando avaliamos uma subárvore, tomamos o nó raiz e este 
passa a ter nível 1. Em destaque, você pode ver o AD e AE de cada subárvore 
do exemplo anterior.
3Balanceamento de árvore
A
CB
D E
F
AD = 1
AE = 2
AD = 1
AE = 3
AD = 0
AE = 0
AD = 0
AE = 0
AD = 0
AE = 1
AD = 0
AE = 0
Agora podemos calcular o FB, que é o conceito que vai nos guiar e res-
ponder as perguntas: 
  A árvore está balanceada?
  Como balancear a árvore?
O FB é calculado ao diminuir a altura da subárvore à esquerda pela altura 
da subárvore à direita. A imagem a seguir mostra o FB dos nós da árvore que 
estamos tomando como exemplo.
Balanceamento de árvore4
A
CB
D E
F
FB = 0
AD = 0
AE = 0
FB = 0
AD = 0
AE = 0
FB = 0
AD = 0
AE = 0
FB = 1
AD = 0
AE = 1
FB = 1
AD = 1
AE = 2
FB = 2
AD = 1
AE = 3
Uma árvore balanceada tem FB entre -1 e +1, dessa forma, na nossa árvore 
de exemplo, mais especificamente no nó A, o FB é igual a 2. Visualmente, 
é fácil de notar, pois existe uma diferença maior que 1 entre as alturas das 
subárvores.
Uma das vantagens da árvore AVL é o fato de ser possível que se faça o 
rebalanceamento local, ou seja, envolvendo somente os nós com FB fora do 
intervalo permitido. Para realizar esse rebalanceamento, existem os conceitos 
de rotação que serão vistos logo a seguir.
Uma forma de manter os nós de uma árvore AVL é adicionando a informa-
ção de altura em sua estrutura, as outras operações, exceto inserção e remoção, 
são semelhantes às implementadas para árvore binária.
A estrutura pode ser vista no código-fonte a seguir.
5Balanceamento de árvore
Além disso, algumas funções podem ser adicionadas: 
  altNo para calcular a altura do nó;
  fatorBalanceamento que calcula o FB de cada nó;
  Maior que retorna o maior valor entre dois números, o que ajudará na 
tomada de decisões quanto às rotações.
Conceitos de árvores AVL: rotações simples
Rotação à direita simples ou LL
As rotações devem ser feitas quando existe um nó que está com o FB fora do 
limite permitido, o que pode acontecer todas as vezes que um novo elemento 
é inserido na árvore, sendo assim, quando inserirmos um elemento, é preciso 
recalcular o FB.
Balanceamento de árvore6
A rotação simples à direita acontece quando, ao inserirmos um nó, sua 
posição é à esquerda da subárvore da esquerda. Como exemplo, imagineque 
tenhamos a árvore a seguir.
8
6
E que precisamos inserir o nó 5.
8
6
5
Nossa árvore ficou desbalanceada e o nó 5 foi inserido à esquerda da 
subárvore à esquerda. Precisamos fazer uma rotação simples à direita ou LL. 
Os passos para a realização dessa rotação são os seguintes:
  O filho da esquerda vira nova raiz.
  A raiz original se torna o filho à direita da nova raiz.
7Balanceamento de árvore
8
8
6
6
5
5
Agora, se o nó 6 tivesse um filho à esquerda, como seria o resultado da 
rotação simples à direita dessa árvore?
8
8
77
6
6
5
5
Assim, podemos resumir o algoritmo para rotação simples à direita da 
seguinte forma:
 O filho da esquerda vira nova raiz.
 A raiz original se torna o filho à direita da nova raiz.
 Se o nó que acabou de se tornar raiz tiver filho à direita, esse nó se 
tornará filho à esquerda da antiga raiz.
Balanceamento de árvore8
Você pode ver o código proposto para realização da rotação simples direita 
na imagem a seguir.
Rotação à esquerda simples ou RR
A rotação simples à esquerda deve ser realizada quando, ao inserirmos um 
nó, sua posição é à direita da subárvore da direita, o que gerou um desbalan-
ceamento. Como exemplo, imagine que tenhamos a árvore a seguir.
6
4
8
Essa árvore está desbalanceada, sendo assim, você pode observar que 
existe uma diagonal totalmente à direita. Para corrigi-la, é preciso fazer uma 
rotação simples à esquerda ou RR. Os passos para a realização dessa rotação 
são os seguintes:
9Balanceamento de árvore
  O filho da direita vira a nova raiz.
  A raiz original se torna o filho à esquerda da nova raiz.
4
4
6
6
8
8
Da mesma forma que no caso da rotação LL, pode acontecer de o filho 
à direita já ter um filho à esquerda. Sendo assim, como seria o resultado da 
rotação simples à esquerda dessa árvore?
O resumo para a rotação à esquerda de uma forma completa é:
  O filho da direita vira a nova raiz.
  A raiz original se torna filho da esquerda.
  Se o filho à direita, que é a nova raiz, tiver filho à esquerda, esse filho 
se torna um filho à direita da raiz original.
Vamos a um exemplo prático.
4
4
6
6
5 5
8
8
Árvore desbalanceada Árvore balanceada
Balanceamento de árvore10
A implementação da rotação simples à esquerda em linguagem C pode 
ser vista na imagem a seguir.
Conceitos de árvores AVL: rotações duplas
Rotação dupla à direita ou LR
A rotação dupla é utilizada quando o desbalanceamento da árvore ocorreu 
gerando um zigue-zague na estrutura da árvore. Há dois tipos de rotação dupla, 
agora vamos analisar a rotação dupla à direita ou a rotação LR.
15
12
8
11Balanceamento de árvore
Para balancearmos essa árvore, não basta uma rotação simples, então 
realizamos a rotação LR que tem os seguintes passos:
  Rotação à esquerda na subárvore à esquerda.
  Rotação à direita na subárvore que foi gerada da primeira rotação.
Vamos balancear a árvore anterior.
15 15
15
Rotação à esquerda Rotação à direita
12
12
12
8
8
8
Como a rotação dupla é feita utilizando os conceitos das rotações simples, a 
implementação em C é facilmente obtida ao utilizar as funções implementadas 
anteriormente.
Balanceamento de árvore12
Rotação dupla à esquerda ou RL
A rotação dupla acontece quando o novo nó que gera o desbalanceamento da 
árvore não é inserido na mesma direção duas vezes. Vamos a um exemplo: 
imagine que tenhamos a árvore a seguir e que queiramos inserir o nó 10.
8
19
Ao inserirmos o nó 10, essa árvore fica desbalanceada, como pode ser 
visto nesta imagem. 
8
19
10
Como pôde ser visto, o novo nó foi inserido na subárvore à esquerda da 
subárvore à direita. Assim, para que essa árvore seja balanceada, precisamos 
fazer a rotação dupla, a rotação dupla à esquerda ou a rotação RL. A rotação 
dupla à esquerda é composta de uma rotação simples à direita e depois uma 
rotação simples à esquerda.
13Balanceamento de árvore
8 8
8
19
19
10
10
10
Rotação à
Direita
Rotação à
Esquerda
19
A seguir, o código-fonte da implementação dessa rotação em linguagem C.
A essa altura, sabemos o porquê de realizar as rotações e quais as existentes, 
mas como saber qual escolher? Podemos escrever um pequeno algoritmo para 
nos ajudar a tomar essa decisão.
Imagine que você inseriu o nó B e o ancestral mais próximo que sofreu 
alteração de FB seja A. Dessa forma, você deve fazer a rotação:
  LL: B inserido na subárvore à esquerda da subárvore à esquerda de A.
  LR: B inserido na subárvore à direita da subárvore à esquerda de A.
  RR: b inserido na subárvore à direita da subárvore à direita de A.
  RL: B inserido na subárvore à esquerda da subárvore à direita de A.
Balanceamento de árvore14
Outra forma de avaliar qual rotação fazer é analisando os valores do FB, 
seja C o filho de A no qual ocorreu a inserção de B:
  LL (A = +2; C = +1).
  RR (A = -2; C = -1).
  LR (A = +2; C = -1).
  RL (A = -2; C = +1).
GRONER, L. Estruturas de dados e algoritmos em JavaScript. 1. ed. São Paulo: Novatec, 
2017. 304 p. (Coleção Conhecimento Condensado da Comunidade).
SZWARCFITER, J. L.; MARKENZON, L. Estruturas de dados e seus algoritmos. 3. ed. Rio de 
Janeiro: LTC, 2010. 318 p.
15Balanceamento de árvore
 
Encerra aqui o trecho do livro disponibilizado para 
esta Unidade de Aprendizagem. Na Biblioteca Virtual 
da Instituição, você encontra a obra na íntegra.
Conteúdo:
 
DICA DO PROFESSOR
Como podemos, a partir de uma árvore desbalanceada, ober uma árvore balanceada? Neste víde
o, partimos da inserção de elementos em uma árvore e chegamos a uma árvore AVL - uma árvor
e balanceada - utilizando, para isso, a rotação dupla à direita.
Aponte a câmera para o código e acesse o link do vídeo ou clique no código para acessar.
 
EXERCÍCIOS
1) Qual a diferença entre uma árvore AVL e uma árvore binária em busca? 
A) 
A árvore AVL é uma árvore binária de busca balanceada, cuja altura das subárvores se dife
re no máximo em 1.
B) 
São duas árvores completamente diferentes e que são representadas internamente no comp
utador de forma igualmente diferente.
C) 
São árvores iguais e que não possuem nenhuma diferença, além das nomenclaturas. As no
menclaturas são diferentes porque foram criadas por pesquisadores diferentes.
D) 
A árvore AVL pode armazenar somente letras e a árvore binária de busca, somente valores 
utilizando a base binária de numeração.
E) 
A árvore binária de busca é uma árvore AVL balanceada.
Inserindo os elementos 10, 3 e 2 em uma árvore binária, obtém-se a seguinte árvore de
sbalanceada:
2) 
https://fast.player.liquidplatform.com/pApiv2/embed/cee29914fad5b594d8f5918df1e801fd/c246d413aef213b5e9919098ab4e2455
A árvore AVL é uma árvore binária de busca balanceada em que, para cada nó, as alturas das subárvores diferem em 1, no máximo. Ela foi proposta em 1962, pelos matemáticos russos G.M. Adelson-Velskii e E.M. Landis, e o nome da árvore vem das iniciais dos seus nomes.
Em qual dos itens é posssível ver a rotação que foi feita e a árvore balanceada gerada 
a partir dessa rotação?
A) 
Rotação à direita.
Rotação à esquerda.
 
B) 
C) 
Rotação à direita. 
Rotação à esquerda. 
D) 
E) 
Rotação à direita. 
 
 
 
A árvore ficou desbalanceada com a inserção de um nó à esquerda da subárvore à esquerda, sendo preciso que se faça uma rotação à direita. Os passos para essa rotação são:
O filho da esquerda vira a nova raiz.
A raiz original se torna o filho à direita da nova raiz
3) Quando inserimos um nó à direita da subárvore direita de uma árvore AVL, e essa in
serção gera um desbalanceamento da árvore, qual a rotação que precisamos fazer pa
ra que a árvore fique balanceada novamente? 
A) 
Rotação simples à direita.
B) 
Rotação dupla direita.
C) 
Rotação simples à esquerda.
D) 
Rotação dupla esquerda.
E) 
Qualquer uma das rotações pode balancear uma árvore. 
4) A operação representada pelas 3 árvores abaixo é uma operação de rotação, de onde s
e inicia com uma árvore desbalanceada e se chega a uma árvore balanceada(da esque
rda para direita).
Qual o nome da rotação que foi realizada? 
A) 
Rotação simples à direita.
B) 
Rotação dupla direita.
Como a direção da subárvore e da inserção do nó é a mesma, precisamos fazer uma rotação simples. Nesse caso, é uma rotação simples à esquerda para arrumar o desbalanceamento à direita.
C) 
Rotação simples à esquerda.
D) 
Rotação dupla esquerda.
E) 
É impossível de se definir somente com as imagens; é preciso que o código-fonte seja anal
isado.
5) Uma rotação dupla é realizada, unindo duas rotações simples. Assim, uma rotação du
pla à direita é realizada da seguinte forma: 
A) 
duas operações de rotação simples à direita.
B) 
uma rotação simples à direita e uma rotação simples à esquerda.
C) 
duas operações de rotação simples à esquerda.
D) 
uma rotação simples à esquerda e uma rotação simples à direita.
E) 
nenhuma das opções anteriores; para se avaliar o que é uma rotação dupla à direita, precis
a-se avaliar a árvore que se está querendo balancear.
NA PRÁTICA
Como usar uma árvore AVL, ou o balanceamento de árvore, em um sistema de análise de dado
s?
Você está desenvolvendo um analisador de jogo de dados eletrônico. Sua gerente, Ivna, solicitou 
que você armazenasse os números sorteados na jogada de dados, pois ela suspeita que o jogo de 
dado eletrônico está viciado. Porém, Ivna fez algumas solicitações: ela pediu que você escolhess
e uma estrutura de dados que não apresentasse muito custo computacional no caso de ser necess
ária uma busca por determinado valor para, por exemplo, saber qual número foi mais sorteado.
 
A árvore desbalanceada (árvore mais à esquerda), está visualmente em ziguezague, o que elimina as rotações simples. Como o nó P, gerador do desbalanceamento, foi inserido à esquerda de uma subárvore à direita, a rotação dupla que deve ser feita é uma rotação dupla à esquerda.
 rotação dupla é utilizada quando o desbalanceamento da árvore ocorreu, gerando uma ziguezague na estrutura desta. Nesses casos, não basta uma rotação simples. A rotação dupla à direita tem os seguintes passos:
- Rotação à esquerda na subárvore à esquerda.
- Rotação à direita na subárvore que foi gerada a partir da primeira rotação.
SAIBA +
Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do professo
r:
Árvore AVL - definições
O que é uma árvore AVL, como é a estrutura de dados que a representa e seus principais algorit
mos?
Aponte a câmera para o código e acesse o link do vídeo ou clique no código para acessar.
Como podemos balancear um árvore?
Quais os tipos de rotação e como escolher entre os quatro: simples à direita, simples à esquerda, 
dupla esquerda e dupla a direita. Neste vídeo, você pode ver esses e mais tópicos relacionados à 
árvore AVL.
Aponte a câmera para o código e acesse o link do vídeo ou clique no código para acessar.
AVL tree - visualizador de algoritmo
Utilize esse visualizador para ir inserindo nós e vendo o comportamento de uma árvore AVL.
Aponte a câmera para o código e acesse o link do vídeo ou clique no código para acessar.
https://www.youtube.com/embed/4eO3UbTiRyo
https://www.youtube.com/embed/3zmjQlJhBLM
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html