Aula3 ED2 - AVL

Prévia do material em texto

Árvores Balanceadas
Prof: Ekler Paulino de Mattos
ekler.mattos@gmail.com
CPCX/UFMS
© Ekler Paulino de Mattos 
editado por Glasielly Demori
1
Árvores Balanceadas
Introdução
• Um aspecto fundamental do estudo de árvores de busca é o custo
de acesso a uma chave desejada.
• Objetivo: para minimizar esse custo, foram desenvolvidas as
árvores binárias de busca.
• Entretanto, ambas se restringem a aplicações estáticas:
• Após um certo número de inserções e remoções, as árvores
deixam de ser ótimas.
© Ekler Paulino de Mattos 2
Árvores Balanceadas
Ideia:
• manter o custo de acesso na mesma ordem de grandeza de uma
árvore ótima, ou seja, O(log n).
• Este custo deve se manter ao longo de toda utilização da estrutura,
inclusive após inclusões e remoções.
Solução:
• A estrutura da árvore deve ser alterada de forma a ser moldar aos
novos dados.
© Ekler Paulino de Mattos 3
Árvores Balanceadas
• O custo dessas alterações, contudo, se mantém em
O(log n).
• Uma estrutura que opera com essas características é
denominada balanceada.
© Ekler Paulino de Mattos 4
O Conceito de Balanceamento
Introdução
• Árvores completas: minimizam o número de comparações
efetuadas no pior caso.
• Para aplicações dinâmicas o uso de árvores completas é, em geral,
desaconselhável.
• Conforme inclusões e exclusões a árvore pode assumir uma forma
pouco recomendável para o problema de busca.
• Pode degenerar-se em uma lista.
© Ekler Paulino de Mattos
Todas as subárvores
vazias são filhas de nós 
do último ou penúltimo 
nível
5
O Conceito de Balanceamento
• Exemplo: Árvore binária degenerada:
DOM
QUA
QUI
SAB
SEG
SEX
TER
© Ekler Paulino de Mattos 6
O Conceito de Balanceamento
• Aplicar um algoritmo que torne a árvore novamente
completa tão logo tal característica fosse perdida após
uma inclusão ou exclusão.
• Dificuldade:
– Efetuar essa operação com o número menor que
(n), no pior caso.
© Ekler Paulino de Mattos 7
O Conceito de Balanceamento
• Exemplo: Árvore Balanceada:
• Subárvores vazia possuem o mesmo nível.
SAB
QUA
DOM QUI
SEX
SEG TER
© Ekler Paulino de Mattos 8
O Conceito de Balanceamento
• Exemplos:
• Só uma uma inclusão sem o aumento de altura da árvore.
© Ekler Paulino de Mattos 9
O Conceito de Balanceamento
• Exemplos:
• Se for incluído o elemento zero (0), a árvore deixará de ser
completa.
© Ekler Paulino de Mattos 10
O Conceito de Balanceamento
© Ekler Paulino de Mattos 11
O Conceito de Balanceamento
© Ekler Paulino de Mattos 12
O Conceito de Balanceamento
Ideia:
• Exigir que a altura dessa nova árvore seja da mesma ordem de
grandeza de uma completa, com o mesmo número de nós.
• Ou seja, com altura igual a O(log n).
• Esta propriedade deve se estender a todas as subárvores. Cada
subárvore que contém m nós deve conter altura de O(log m).
• Uma árvore que satisfaça esta condição é dita balanceada.
• Utilizar árvores com altura que não ultrapasse O(log n).
© Ekler Paulino de Mattos 13
Árvores AVL
• Adelson-Velskii e Landis (1962): introduziram um conceito menos
rigoroso de árvore balanceada.
• Regra:
• Fator de balanceamento: Cada nó n, as alturas das subárvores
à esquerda e à direita diferem no máximo de uma unidade.
• Ou seja…
𝑫 𝑬
© Ekler Paulino de Mattos 14
Árvores AVL
Regra:
• Se o balanço de um nó v variar em mais de uma unidade é dita que
a árvore está desbalanceada:
• Para esquerda se < -1.
• Para a direita se > +1.
• Após alguma inserção ou remoção que desbalanceie a árvore,
utiliza-se operações de custo O(1) chamadas rotações.
© Ekler Paulino de Mattos 15
Árvores AVL
• Exemplo:
• Quais destas duas árvores é AVL?
a) b)
© Ekler Paulino de Mattos 16
Árvores AVL
• Exemplo:
a) b)
𝒉𝑫 𝒗 − 𝒉𝑬 𝒗 = 
2 – 0 = 2
Desbalanceada em v.
© Ekler Paulino de Mattos 17
Rotação em Árvores AVL
• Operações em uma Árvores AVL
– Inserção.
– Remoção.
• Em toda operação de inserção e remoção é necessário verificar se a árvore
AVL está balanceada. (Cálculo da altura de todos os nós).
• Caso a árvore esteja desbalanceada, é necessário realizar operações de 
balaceamento.
© Ekler Paulino de Mattos 18
Rotação em Árvores AVL
Operações de Balaceamento:
 Rotação Simples à Direita (RSD).
 Rotação Simples à Esquerda (RSE).
 Rotação Dupla à Direita (RDD).
 Rotação Dupla à Esquerda (RDE).
© Ekler Paulino de Mattos 19
Rotação em Árvores AVL
Rotação Simples à Direita
© Ekler Paulino de Mattos 20
Rotação em Árvores AVL
ℎா: altura das subárvores esquerda.
ℎ஽: altura das subárvores direita.
• Rotação Simples à Direita
ா ஽
– a possui filho esquerdo b.
ா ஽
– Em b, T1 possui o filho esquerdo c.
e
c
© Ekler Paulino de Mattos 21
Rotação em Árvores AVL
Rotação Simples à Direita
Em outras palavras…
c
c
© Ekler Paulino de Mattos 22
Rotação em Árvores AVL
Rotação Simples à Direita
Exemplo:
Inserindo os números: 50, 30, 10
Em outras palavras…
© Ekler Paulino de Mattos 23
Rotação em Árvores AVL
Rotação Simples à Direita
Exemplo:
A ordem de entrada dos dados (decrescente), faz
com que a árvore resultante quebre o
balanceamento, onde dada uma raiz r, a quebra do
balanceamento tem como características:
• Todos os nós da sub-árvore de r em que ocorreu
a quebra do balanceamento são menores que r;
e para uma raiz arbitrária ra dentro dessa sub-
árvore, vale a relação recursiva desta mesma
propriedade para ra;
• Em outras palavras: Dado uma raiz r, o filho de r
sempre será menor que r;
• Logo, temos uma árvore inclinada para a
esquerda.
© Ekler Paulino de Mattos 24
r
Rotação em Árvores AVL
Rotação Simples à Direita
Exemplo:
© Ekler Paulino de Mattos 25
r r
Rotação em Árvores AVL
Rotação Simples à Direita
Exemplo:
• O nó intermediário(30) é menor
que seu pai(50), porém, é maior
que seu filho(10).
• Logo o nó intermediário(30) deve
ser escolhido para ser a raiz da
árvore resultante.
• O nó corrente(50) tem que cair
para a direita, ou seja, ser
rotacionado para direita.
© Ekler Paulino de Mattos 26
r r
© Ekler Paulino de Mattos 27
Rotação em Árvores AVL
Rotação Simples à Direita
• Filho esquerdo torna-se raiz
• Se esse filho esquerdo já tem um filho direito então,
• Esse filho direito torna-se filho esquerdo da raiz original.
• Raiz original torna-se filho direito da nova raiz.
© Ekler Paulino de Mattos 27
c
Rotação em Árvores AVL
Rotação Simples à Esquerda
© Ekler Paulino de Mattos 28
Rotação em Árvores AVL
ℎா: altura das subárvores esquerda.
ℎ஽: altura das subárvores direita.
• Rotação Simples à Esquerda
ா ஽
– a possui filho direito b.
ா ஽
– Em b, T3 possui o filho direito c.
e
c
© Ekler Paulino de Mattos 29
Rotação em Árvores AVL
Rotação Simples à Esquerda
Em outras palavras…
c
c
© Ekler Paulino de Mattos 30
Rotação em Árvores AVL
Rotação Simples à Esquerda
Exemplo:
Inserindo os números: 10, 30, 50
© Ekler Paulino de Mattos 31
r
Rotação em Árvores AVL
Rotação Simples à Esquerda
Exemplo:
Inserindo os números: 10, 30, 50
A ordem de entrada dos dados (crescente), faz
com que a árvore resultante quebre o
balanceamento, onde dada uma raiz r, a quebra
do balanceamento tem como características:
• Todos os nós da subárvore de r em que
ocorreu a quebra do balanceamento são
maiores que r; e para uma raiz arbitrária ra
dentro dessa subárvore, vale a relação
recursiva desta mesma propriedade para ra;
• Em outras palavras: Dado uma raiz r, o filho
de r sempre será maior que r;
• Logo, temos uma árvore inclinada para a
direita.
r
© Ekler Paulinode Mattos 32
Rotação em Árvores AVL
Rotação Simples à Esquerda
Exemplo:
© Ekler Paulino de Mattos 33
r r
Rotação em Árvores AVL
Rotação Simples à Esquerda
Exemplo:
• O nó intermediário(30) é maior que
seu pai(10), porém, é menor que
seu filho(50).
• Logo o nó intermediário(30) deve
ser escolhido para ser a raiz da
árvore resultante.
• O nó corrente(10) tem que cair
para a esquerda, ou seja, ser
rotacionado para esquerda.
© Ekler Paulino de Mattos 34
r r
© Ekler Paulino de Mattos 35© Ekler Paulino de Mattos 35
Rotação em Árvores AVL
Rotação Simples à Esquerda
• Filho direito torna-se raiz
• Se esse filho direito já tem um filho esquerdo então,
• Esse filho esquerdo ftorna-se filho direito da raiz original.
• Raiz original torna-se filho esquerdo da nova raiz.
© Ekler Paulino de Mattos 35
c
Rotação em Árvores AVL
Rotação Dupla à Direita
© Ekler Paulino de Mattos 36
Rotação em Árvores AVL
ℎா: altura das subárvores esquerda.
ℎ஽: altura das subárvores direita.
• Rotação Dupla à Direita
ா ஽
– a possui filho esquerdo b.
ா ஽
– b possui filho direito c.
e
© Ekler Paulino de Mattos 37
Rotação em Árvores AVL
• Rotação Dupla à Direita
• Em outras palavras…
© Ekler Paulino de Mattos 38
Rotação em Árvores AVL
Rotação Dupla à Direita
Exemplo:
Inserir os números: 50, 10 , 30
© Ekler Paulino de Mattos 39
r
Rotação em Árvores AVL
Rotação Dupla à Direita
Exemplo:
Inserir os números: 50, 10 , 30
Nesse caso, a ordem de entrada dos dados, faz
com que a árvore resultante quebre o
balanceamento, onde dada uma raiz r, a quebra
do balanceamento tem como características:
• Dada uma raiz r, o filho de r no qual a árvore
quebrou o balanceamento é menor que r; e
considerando o filho de r. uma raiz rs, o filho
de rs no qual a árvore quebrou o
balanceamento é maior do que rs;
• A chave é inserida na subárvore esquerda de
r, mas pesa a direita.
r
rs
© Ekler Paulino de Mattos 40
Rotação em Árvores AVL
Rotação Dupla à Direita
Exemplo:
Inserir os números: 50, 10 , 30
© Ekler Paulino de Mattos 41
r r r
Rotação em Árvores AVL
Rotação Dupla à Direita
Exemplo:
• O nó intermediário(10) é menor que seu pai(50), e é menor que seu filho(30).
• Logo o nó intermediário(10) deve ser trocado com o seu filho(30), por uma
rotação à esquerda, caindo no 2º caso;
• Então aplica-se uma rotação à direta.
© Ekler Paulino de Mattos 42
r r r
© Ekler Paulino de Mattos 43© Ekler Paulino de Mattos 43© Ekler Paulino de Mattos 43
Rotação em Árvores AVL
Rotação Dupla à Direita
• Rotação simples à esquerda na subárvore da esquerda;
• Rotação simples à direita na árvore original.
© Ekler Paulino de Mattos 43
Rotação em Árvores AVL
Rotação Dupla à Esquerda
© Ekler Paulino de Mattos 44
Rotação em Árvores AVL
ℎா: altura das subárvores esquerda.
ℎ஽: altura das subárvores direita.
• Rotação Dupla à Esquerda
ா ஽
– a possui filho direito b.
ா ஽
– b possui filho esquerdo c.
e
© Ekler Paulino de Mattos 45
Rotação em Árvores AVL
• Rotação Dupla à Esquerda
• Em outras palavras…
© Ekler Paulino de Mattos 46
Rotação em Árvores AVL
Rotação Dupla à Esquerda
Exemplo:
Inserir os números: 10 ,50, 30
© Ekler Paulino de Mattos 47
r
Rotação em Árvores AVL
Rotação Dupla à Esquerda
Exemplo:
Inserir os números: 10 ,50, 30
A ordem de entrada dos dados, faz com que a
Árvore resultante quebre o balanceamento,
onde dada uma raiz r, a quebra do
balanceamento tem como características:
• Dada uma raiz r, o filho de r no qual a árvore
quebrou o balanceamento é maior que r; e
considerando o filho de r uma raiz rs, o filho
de rs no qual a árvore quebrou o
balanceamento é menor do que rs;
• A chave é inserida na subárvore direita da
raiz r, mas pesa a esquerda.
r
rs
© Ekler Paulino de Mattos 48
Rotação em Árvores AVL
Rotação Dupla à Esquerda
Exemplo:
Inserir os números: 10 ,50, 30
© Ekler Paulino de Mattos 49
r rr
Rotação em Árvores AVL
Rotação Dupla à Esquerda
Exemplo:
• O nó intermediário(50) é maior que seu pai(10), e é maior que seu filho(30).
• Logo o nó intermediário(50) deve ser trocado com o seu filho(30), por uma rotação à
direita, caindo no 2º caso;
• Então aplica-se uma rotação à esquerda.
© Ekler Paulino de Mattos 50
r r r
© Ekler Paulino de Mattos 51© Ekler Paulino de Mattos 51© Ekler Paulino de Mattos 51© Ekler Paulino de Mattos 51
Rotação em Árvores AVL
Rotação Dupla à Esquerda
• Rotação simples à direita na subárvore da direita;
• Rotação simples à esquerda na árvore original.
© Ekler Paulino de Mattos 51
© Ekler Paulino de Mattos 52© Ekler Paulino de Mattos 52© Ekler Paulino de Mattos 52© Ekler Paulino de Mattos 52© Ekler Paulino de Mattos 52
Inserção AVL
© Ekler Paulino de Mattos 52
© Ekler Paulino de Mattos 53© Ekler Paulino de Mattos 53© Ekler Paulino de Mattos 53© Ekler Paulino de Mattos 53© Ekler Paulino de Mattos 53
Inserção AVL
© Ekler Paulino de Mattos 53
© Ekler Paulino de Mattos 54© Ekler Paulino de Mattos 54© Ekler Paulino de Mattos 54© Ekler Paulino de Mattos 54© Ekler Paulino de Mattos 54
Inserção AVL
© Ekler Paulino de Mattos 54