Aula1 Árvore AVL Introdução e Inserção

Prévia do material em texto

AEDs II - Aula 01
Árvores Balanceadas - AVL
Parte I
Profa. Laura Silva de Assis
Engenharia de Computação
4o Peŕıodo
CEFET/RJ - Centro Federal de Educação Tecnológica Celso Suckow da Fonseca
Campus Petrópolis
1
Sumário
1 Árvores balanceadas
2 Referências
2
Árvores balanceadas Introdução
2
Árvores balanceadas Introdução
—————————————————————————-
Árvores binárias de busca
As árvores binárias de busca são, em alguns casos, pouco recomendáveis para
as operações básicas (inserção, remoção e busca).
Árvores binárias de busca degeneradas tornam as operações básicas lentas
O(n).
Árvore binária completamente balanceada ocorre quando a árvore está
completa ou quase completa (o ńıvel n-1 completo).
1
1
1 1
6
1
1
1
1 1
1
1 1
3
Árvores balanceadas Introdução
Árvores binárias de busca
Uma árvore binária completa leva um tempo na ordem de O(log n) para
operações de inserção, remoção e pesquisa. Very good!!! :-).
Após uma inserção ou remoção a árvore pode deixar de ser completa.
A solução seria aplicar um algoritmo que tornasse a árvore novamente
completa, porém o custo para realizar esta operação poderia ser de O(n).
4
2
1
0
1
1
1
1
1
1 1
1
1 1
4
Árvores balanceadas Introdução
Árvores balanceadas
A operação de busca certamente é uma das mais frequentemente realizadas
quando utilizamos árvores.
Um aspecto fundamental do estudo de árvores de busca é, naturalmente, o
custo de acesso a uma chave desejada.
Em árvores binárias de busca, o custo de uma pesquisa pode ser O(n)
(degenerada).
Se a probabilidade de acesso é a mesma, é interessante manter o custo de
acesso na mesma ordem de grandeza de um árvore ótima O(log n).
5
Árvores balanceadas Introdução
Árvores balanceadas
Para alcançar essa complexidade a estrutura deve ser modificada
periodicamente de forma a se moldar aos novos dados.
O custo dessas alterações deve se manter em O(log n).
Uma estrutura que opera com essas caracteŕısticas é chamada de balanceada.
6
Árvores balanceadas Introdução
Conceito de balanceamento
As árvores completas são as que minimizam o número de comparações
efetuadas, no pior caso, para uma busca com chaves com mesma
probabilidade de ocorrência.
Para aplicações dinâmicas o uso de árvores completas é desaconselhável.
7
Árvores balanceadas Introdução
Conceito de balanceamento
Exemplo:
8
Árvores balanceadas Introdução
Conceito de balanceamento
Observando as figuras nota-se que todos os nós internos se tornaram nós
folhas e vice-versa.
Para realizar essa transformação utilizando a representação de árvores binária
é necessário percorrer todos os nós da árvore.
O algoritmo de restabelecimento da árvore binária requer pelo menos Ω(n)
passos.
Por esse motivo árvores completas e a busca binária não são recomendadas
para estruturas dinâmicas.
9
Árvores balanceadas Introdução
Conceito de balanceamento
Uma alternativa é utilizarmos um tipo de árvore para a qual a busca, no pior
caso, não seja necessariamente tão pequena quanto o ḿınimo de passos
usados pela árvore completa (1 + blog nc).
Porém deseja-se que a altura dessa árvore seja da mesma ordem de grandeza
que uma completa com o mesmo número de nós (O(log n)).
É desejável que essa propriedade se extenda a todas as subárvores, ou seja
cada subárvore com n nós deve ter altura igual a O(log n).
Uma árvore que satisfaça essa condição é denominada árvore balanceada.
10
Árvores balanceadas Introdução
Conceito de balanceamento
A idéia é que embora a altura da árvore balanceada seja maior que a ḿınima
(1 + blog nc), ainda assim não ultrapasse O(log n).
Como a forma de uma árvore balanceada é menos ŕıgida que de uma
completa torna-se, em prinćıpio, mais fácil o seu rebalanceamento.
Temos árvores binárias que satisfazem as condições de balanceamento e que
após modificações empregam operações de rebalanceamento que requerem
apenas O(log n) passos.
11
Árvores balanceadas Árvores AVL
Árvores AVL
Adelson-Velskii e Landis em 1962, apresentaram uma árvore de busca binária
que é balanceada com respeito a altura das subárvores.
Uma caracteŕıstica importante deste tipo de árvore é que uma busca é
realizada em O(log n) se a árvore possui n nós.
12
Árvores balanceadas Árvores AVL
Árvores AVL
Uma árvore binária T é denominada AVL quando para qualquer nó v ∈ T , as
alturas de suas duas subárvores (esquerda e direita) diferem em módulo de
até 1 unidade.
Dizemos, nesse caso, que v é um nó balanceado e caso contrário,
desbalanceado.
Se uma árvore binária possui algum nó desbalanceado então essa árvore está
desbalanceada.
Naturalmente toda árvore completa é AVL, mas a rećıproca nem sempre é
verdadeira.
13
Árvores balanceadas Balanceamento
Árvores AVL - balanceamento
O balanceamento de um nó é definido como a altura de sua subárvore
esquerda menos a altura de sua subárvore direita.
Cada nó numa árvore binária balanceada (AVL) tem balanceamento de 1, −1
ou 0.
Se o valor do balanceamento de um nó for diferente de 1, −1 ou 0, essa
árvore não é balanceada, portanto não é AVL.
14
Árvores balanceadas Balanceamento
Árvores AVL - balanceamento
Nós balanceados: São aqueles onde os valores de FB são -1, 0 ou 1.
FB(v):
+1: subárvore esquerda maior que direita.
0: subárvore esquerda igual a direita.
-1: subárvore esquerda menor que direita.
15
Árvores balanceadas Balanceamento
Árvores AVL - balanceamento
Nós desbalanceados: São aqueles onde os valores de FB são diferentes de
-1, 0 ou 1.
FB(v):
> 1: subárvore esquerda está desbalanceando o nó v .
< -1: subárvore direita está desbalanceando o nó v .
16
Árvores balanceadas Balanceamento
Árvores AVL- balanceamento
Definição formal
Uma árvore binária vazia é sempre balanceada por altura.
Se T não é vazia e Te e Td são suas subárvores da esquerda e direita, então
T é balanceada por altura se:
Te e Td são balanceadas por altura.
|he(v)− hd(v)| ≤ 1, onde he e hd são as alturas de Te e Td respectivamente.
17
Árvores balanceadas Balanceamento
Árvores AVL- balanceamento
Definição formal
Fator de balanceamento (FB): he − hd .
Propriedade AVL: |he(v)− hd(v)| ≤ 1.
A definição de árvore binária balanceada por altura requer que toda subárvore
seja balanceada por altura.
18
Árvores balanceadas Balanceamento
Árvores AVL - balanceamento
Calcule o FB de cada nó
19
Árvores balanceadas Balanceamento
Árvores AVL - balanceamento
Exemplo AVL
20
Árvores balanceadas Balanceamento
Árvores AVL - balanceamento
Calcule o FB de cada nó
21
Árvores balanceadas Balanceamento
Árvores AVL - balanceamento
Exemplo Não AVL
22
Árvores balanceadas Balanceamento
Árvore AVL
Estrutura
s t r u c t noAVL{
i n t i n f o ;
i n t f b ; // f a t o r de ba lanceamento
s t r u c t noAVL ∗ p a i ;
s t r u c t noAVL ∗ esq ;
s t r u c t noAVL ∗ d i r ;
} ;
23
Árvores balanceadas Balanceamento
Árvores AVL
Exemplo:
O desbalanceamento ocorre quando:
1 O nó v inserido é um descendente esquerdo do nó x que tinha FB(x) = 1.
2 O nó v inserido é um descendente direito do nó x que tinha FB(x) = −1.
24
Árvores balanceadas Balanceamento
Árvores AVL - balanceamento
Exemplo: Inserções balanceadas e não balanceadas
25
Árvores balanceadas Balanceamento
Árvores AVL - balanceamento
Manutenção do balanceamento
Para manter uma árvore balanceada, é necessário fazer uma transformação
na árvore tal que:
1 O percurso em ordem da árvore transformada seja o mesmo da árvore original,
isto é, a árvore transformada continue sendo uma árvore de busca binária.
2 A árvore transformada fique balanceada.
26
Árvores balanceadas Balanceamento
Árvores AVL - balanceamento
Manutenção do balanceamento
A transformação a ser feita naárvore, tal que ela se mantenha balanceada é
chamada de rotação.
A rotação poderá ser feita à esquerda ou à direita, dependerá do
desbalanceamento que tivermos de solucionar.
A rotação deve respeitar as regras 1 e 2 da transformação.
Dependendo do tipo de desbalanceamento, apenas uma rotação não será
suficiente para tornar a árvore balanceada novamente.
27
Árvores balanceadas Inserção
Inserção em árvores AVL
Sempre ocorre nas folhas.
Pode ocasionar:
O aumento da altura da subárvore onde o nó foi inserido.
A alteração dos fatores de balanceamento dos nós daquela subárvore.
28
Árvores balanceadas Inserção
Inserção em árvores AVL
Seja T uma árvore AVL na qual serão realizadas inclusões de nós.
Para que T se mantenha como AVL é preciso realizar uma transformação na
árvore mantendo todos os nós balanceados.
Ideia: verificar após cada inserção se algum nó v ficou desbalanceado.
Se |he(v)− hd(v)| > 1 para algum nó v ∈ T , deve-se aplicar transformações
apropriadas para balancear esse nó.
29
Árvores balanceadas Inserção
Inserção em árvores AVL
Passos:
1 Inserir uma chave em árvores AVL é idêntico a inserção em uma árvore
binária comum.
2 Verificar se existe algum nó desbalanceado na árvore.
3 Se existir, torná-lo balanceado com a aplicação da rotação apropriada.
30
Árvores balanceadas Inserção
Inserção em árvores AVL
Cálculo do balanceamento de um nó após uma operação
Atualização do FB.
31
Árvores balanceadas Inserção
Inserção em árvores AVL
Rotação: Operação que altera o balanceamento de uma árvore T , mantendo
a seqüência de percurso em-ordem.
O rebalanceamento é realizado através de rotações no primeiro ancestral de v
cujo fator de balanceamento torna-se, em módulo, > 1.
32
Árvores balanceadas Inserção
Inserção em árvores AVL
Seja D o ancestral de v , cujo FB > 1 após a inclusão de v :
1 Caso RR v é inserido na subárvore da esquerda do filho esquerdo de D.
2 Caso LL v é inserido na subárvore da direita do filho direito de D.
3 Caso LR v é inserido na subárvore da direita do filho esquerdo de D.
4 Caso RL v é inserido na subárvore da esquerda do filho direito de D.
33
Árvores balanceadas Inserção
Inserção em árvores AVL
Exemplo: Casos RR, LL, RL e LR
34
Árvores balanceadas Inserção
Inserção em árvores AVL
Exemplo: inserção e desbalanceamento: RR
Considerando o nó que ficou desbalanceado (D) após a Inserção de uma
chave:
Guarde a subárvore da esquerda (aux = D → esq).
A subárvore esquerda de D recebe a subárvore da direita de aux .
A subárvore direita de aux recebe D.
Verifique o balanceamento.
35
Árvores balanceadas Inserção
Inserção em árvores AVL
Exemplo: inserção e desbalanceamento: RR
36
Árvores balanceadas Inserção
Inserção em árvores AVL
Exemplo: inserção e desbalanceamento: LL (simétrico a RR)
Considerando o nó que ficou desbalanceado (D) após a Inserção de uma
chave:
Guarde a subárvore da direita (aux = D → dir).
A subárvore direita de D recebe a subárvore da esquerda de aux .
A subárvore esquerda de aux recebe D.
Verifique o balanceamento.
37
Árvores balanceadas Inserção
Inserção em árvores AVL
Exemplo: inserção e desbalanceamento: LL (simétrico a RR)
38
Árvores balanceadas Inserção
Inserção em árvores AVL
Exemplo: inserção e desbalanceamento: RL
Considerando o nó que ficou desbalanceado (D) após a Inserção de uma
chave:
Efetua-se uma rotação RR na subárvore direita do nó desbalanceado
(D → dir).
Realiza-se uma rotação LL no nó desbalanceado (D).
39
Árvores balanceadas Inserção
Inserção em árvores AVL
Exemplo: inserção e desbalanceamento: RL (passo 1)
Efetua-se uma rotação RR na subárvore direita do nó desbalanceado
(D → dir).
40
Árvores balanceadas Inserção
Inserção em árvores AVL
Exemplo: inserção e desbalanceamento: RL (passo 2)
Realiza-se uma rotação LL no nó desbalanceado (D).
41
Árvores balanceadas Inserção
Inserção em árvores AVL
Exemplo: inserção e desbalanceamento: LR (simétrica à RL)
Considerando o nó que ficou desbalanceado (D) após a Inserção de uma
chave:
Efetua-se uma rotação LL na subárvore esquerda do nó desbalanceado
(D → esq).
Realiza-se uma rotação RR no nó desbalanceado (D).
42
Árvores balanceadas Inserção
Inserção em árvores AVL
Exemplo: inserção e desbalanceamento: LR (passo 1)
Efetua-se uma rotação LL na subárvore esquerda do nó desbalanceado
(D → esq).
43
Árvores balanceadas Inserção
Inserção em árvores AVL
Exemplo: inserção e desbalanceamento: LR (passo 2)
Realiza-se uma rotação RR no nó desbalanceado (D).
44
Árvores balanceadas Inserção
Inserção em árvores AVL
Generalizando
Considerando o nó inserido v .
Somente subárvores que contém v aumentam sua altura.
Os nós que ficaram desbalanceados são todos ancestrais de v .
Não se pode esquecer de atualizar os nós pais dos nós que sofreram
modificações.
45
Árvores balanceadas Inserção
Inserção em árvores AVL
Passos a serem seguidos:
E f e t u a r a i n s e r ç ão ( i g u a l a ABB) .
A j s u t a r os f a t o r e s de ba lanceamento .
V e r i f i c a r s e a á r v o r e permanece AVL .
Se a á r v o r e não e s t i v e r mais ba lanceada , c o r r i g i r a e s t r u t u r a a t r a v é s de r o t a
ç õ e s .
46
Árvores balanceadas Inserção
Inserção em árvores AVL
Pseudocódigo das rotações
v o i d Balanceamento ( noAVL ∗no ) {
i f ( no−>f b = = 2) {
i f ( no−>esq−>f b = = −1)
LL ( no−>esq ) ;
RR( no ) ;
}
e l s e i f ( no−>f b = = −2){
i f ( no−>d i r−>f b = = 1)
RR( no−>d i r ) ;
LL ( no ) ;
}
}
v o i d RR( noAVL ∗d ) {
noAVL ∗aux ;
aux = d−>esq ;
aux−>d i r−>p a i = d ;
d−>esq = aux−>d i r ;
aux−>d i r = d ;
aux−>p a i = d−>p a i ;
d−>p a i = aux ;
d = aux ;
}
v o i d LL ( noAVL ∗d ) {
noAVL ∗aux ;
aux = d−>d i r ;
aux−>esq−>p a i = d ;
d−>d i r = aux−>esq ;
aux−>esq = d ;
aux−>p a i = d−>p a i ;
d−>p a i = aux ;
d = aux ;
}
v o i d RL( noAVL ∗d ) {
RR( d−>d i r ) ;
LL ( d ) ;
}
v o i d LR( noAVL ∗d ) {
LL ( d−>esq ) ;
RR( d ) ;
}
47
Referências
Referências
1 Algoritms: teoria e prática. Cormen, T. H.. et al. Rio de Janeiro: Campus,
2002
2 Estruturas de Dados e seus Algoritmos. Szwarcfiter, J. L. e Markenzon, L.
3a. Edição. LTC, 2013.
	Árvores balanceadas
	Introdução
	Árvores AVL
	Balanceamento
	Inserção
	Referências