Arvore AVL

Prévia do material em texto

ÁRVORE AVL
ÁRVORE AVL
� ÁRVORE BALANCEADA
� Uma árvore é dita balanceada quando as suas subárvores à 
esquerda e à direita possuem a mesma altura.
� Todos os links vazios estão no mesmo nível, ou seja, que a 
árvore está completa.árvore está completa.
� A árvore que não está balanceada, define-se como degenerada
ÁRVORE AVL
� Árvore balanceada
12
9 15
7 11 2013
ÁRVORE AVL
� Árvore binária incompleta balanceada
12
9 15
7 11 2013
25
ÁRVORE AVL
� Árvore degenerada
12
9 159 15
7
29
2013
25
ÁRVORE AVL
� Balanceamento Estático
� O balanceamento estático de uma árvore binária consiste em 
construir uma nova versão, reorganizando-a.
� Balanceamento Dinâmico
� Árvore AVL em homenagem aos matemáticos russos (Adelson-� Árvore AVL em homenagem aos matemáticos russos (Adelson-
Velskii e Landism -1962)
ÁRVORE AVL
� Uma árvore AVL é uma árvore binária de pesquisa onde a 
diferença em altura entre as subárvores esquerda e direita é no 
máximo 1 (positivo ou negativo).
� A essa diferença chamamos de “fator de balanceamento” de n 
(FatBal (n)).
� Essa informação deverá constar em cada nó de uma árvore 
balanceada. 
ÁRVORE AVL
� Assim, para cada nodo podemos definir um fator de 
balanceamento (FB), que vem a ser um número inteiro 
igual a:
� FB(nodo p) = altura(subárvore direita p) -
altura(subárvore esquerda p)altura(subárvore esquerda p)
� O Fator de uma folha é sempre Zero (0)
ÁRVORE AVL
� Exemplos de árvores AVL e árvores não-AVL.
� Os números nos nodos representam o FB para cada nodo.
� Para uma árvore ser AVL os fatores de balanço devem ser 
necessariamente -1, 0, ou 1.
ÁRVORE AVL
� Exemplo de árvore AVL
ÁRVORE AVL
� Exemplo de árvore não AVL
ÁRVORE AVL
� Inicialmente inserimos um novo nodo na árvore.
� A inserção deste novo nodo pode ou não violar a 
propriedade de balanceamento.
� Caso a inserção do novo nodo não viole a propriedade de 
balanceamento podemos então continuar inserindo balanceamento podemos então continuar inserindo 
novos nodos.
� Caso contrário precisamos nos preocupar em restaurar 
o balanço da árvore. A restauração deste balanço é 
efetuada através do que denominamos ROTAÇÕES na 
árvore.
ÁRVORE AVL
� Se quisermos manter a árvore balanceada a cada inserção, 
devemos ter um algoritmo que ajuste os fatores de 
balanceamento
� O algoritmo corrige a estrutura através de movimentação 
dos nós, ao que chamamos de “rotação”.dos nós, ao que chamamos de “rotação”.
ÁRVORE AVL
� Exemplo:
� Vamos considerar a seguinte árvore (os números ao lado dos nodos 
são o FB de cada nodo):
ÁRVORE AVL
� A árvore acima está balanceada, como podemos observar 
pelos FB de cada nodo.
� Os casos possíveis de desbalanceamento são 2. Veremos cada 
um deles.
ÁRVORE AVL
� TIPO 1 - ROTAÇÃO DUPLA
� Ao inserir o número 5 na árvore. Esta inserção produziria a seguinte 
árvore:
ÁRVORE AVL
� O nodo 8 fica com o FB -2 e tem um filho com FB +1. Neste 
caso o balanceamento é atingido com duas rotações, também 
denominada ROTAÇÃO DUPLA.
� Primeiro rotaciona-se o nodo com FB 1 para a esquerda.
ÁRVORE AVL
� A seguir rotaciona-se o nodo que tinha FB -2 na direção oposta 
(direita neste caso).
ÁRVORE AVL
A árvore fica:
� Os FB nos nodos voltaram a ficar dentro do esperado das árvores AVL.
� O caso simétrico ao explicado acima acontece com os sinais de FB trocados, ou seja, um nodo 
com FB +2 com um filho com FB -1. Também utilizariamos uma rotação dupla, mas nos 
sentidos contrários, ou seja, o nodo com FB -1 seria rotacionado para a direita e o nodo com 
FB +2 seria rotacionado para a esquerda.
ÁRVORE AVL
� Suponha que queremos inserir o nodo 3 na árvore inicial.
� A inserção produziria a seguinte árvore:
• A inserção do nodo 3 produziu um desbalanço no nodo 8 verificado pelo FB 
-2 neste nodo.
•Neste caso, como os sinais dos FB são os mesmos (nodo 8 com FB -2 e nodo 
4com FB -1) significa que precisamos fazer apenas uma ROTAÇÃO SIMPLES 
à direita no nodo com FB -2.
• No caso simétrico (nodo com FB 2) faríamos uma rotação simples à 
esquerda.
ÁRVORE AVL
� TIPO 2 –ROTAÇÃO SIMPLES
� Após a rotação simples a árvore ficaria:
Observe que os FB estão dentro do esperado para 
mantermos a propriedade de balanceamento de árvores 
AVL.
ÁRVORE AVL
� A descrição do algoritmo em pseudo-código para construção 
de uma árvore AVL:
� 1. Insira o novo nodo normalmente (ou seja, da mesma 
maneira que inserimos numa ABB);
� 2. Iniciando com o nodo pai do nodo recém-inserido, teste se � 2. Iniciando com o nodo pai do nodo recém-inserido, teste se 
a propriedade AVL é violada neste nodo, ou seja, teste se o 
FB deste nodo é maior do que abs(1). Temos aqui 2 
possibilidades:
ÁRVORE AVL
� 2.1 A condição AVL foi violada
� 2.1.1 Execute as operações de rotação conforme for o caso 
(Tipo 1 ou Tipo 2)
� 2.1.2 Volte ao passo 1
2.2 A condição AVL não foi violada.2.2 A condição AVL não foi violada.
Se o nodo recém-testado não tem pai, ou seja, é o 
nodo raiz da árvore, volte para inserir novo nodo (Passo 
1)
ÁRVORE AVL
� DICAS: ÁRVORES AVL
� 1. Para identificarmos quando uma rotação é simples ou 
dupla observamos os sinais de FatBal:
•se o sinal for igual, a rotação é simples.
•se o sinal for diferente a rotação é dupla.•se o sinal for diferente a rotação é dupla.
� 2. Se FB+ rotação para esquerda
� 3. Se FB- rotação para direita
ÁRVORE AVL
� Exercício 1:
� Considere a inserção dos seguintes valores (nesta ordem) em 
uma árvore AVL: 5,3,8,2,4,7,10,1,6,9,11. Para essas 
inserções nenhuma rotação é necessária. Desenhe a árvore 
AVL resultante e determine o fator de balanceamento de AVL resultante e determine o fator de balanceamento de 
cada nó.
5
Inicialmente a árvore esta vazia e inserimos o vértice 5, 
depois calculamos o fator de balanceamento. 
FB = altura direita da árvore – altura esquerda da árvore.
FB = 0-0 = 0
ÁRVORE AVL
Depois inserimos o próximo valor 3, e calculamos o fator de
Balanceamento para cada vértice. 
5
FB= 0-1 =-1
altura direita: 0 
3
FB= 0-0 =0
altura direita: 0 altura esquerda: 1 
Não faremos rotações porque os fatores de balanceamento são:
0 e -1. 
ÁRVORE AVL
� Inserimos o valor 8 e calculamos o fator de balanceamento para cada vértice
5
FB= 1-1 = 0
altura direita:1 altura esquerda: 1 
3
FB= 0-0 =0
altura direita:1 altura esquerda: 1 
8
FB= 0-0 =0
� Não será feita rotação porque a árvore está balanceada
ÁRVORE AVL
� Inserindo o valor 2, depois calculamos o fator de 
balanceamento para todos os vértices.
5
FB= 1-2 = -1
altura 
3
FB=0
altura 
esquerda: 1 
8
altura 
direita: 0
2
FB=0-1=-1
altura 
esquerda: 2 
altura 
direita: 1
FB=0
ÁRVORE AVL
� Vamos inserir o valor 4 e calculamos o fator de 
balanceamento para todos os vértices.
5
FB= 1-2 = -1
altura 
3
FB=0
altura 
esquerda: 1 
8
altura 
direita:12
FB=1-1=0
altura 
esquerda: 2 
altura 
direita: 1
FB=0
4
ÁRVORE AVL
� Vamos inserir o valor 7 e recalculamos o fator de 
balanceamento para cada vértice.
5
FB= 2-2 = 0
3
FB=0
altura 
esquerda: 1 
8
2
FB=0altura 
esquerda: 2 
altura 
direita: 2
FB=-1
4 7
FB=0 FB=0
ÁRVORE AVL
� Vamos inserir o valor 10 e recalcule o fator de balanceamento para cada vértice 
5
FB= 2-2 = 0
3
FB=0
8
2
FB=0altura 
esquerda: 2 
altura 
direita: 2
FB=0
4 7
FB=0 FB=0
10
FB=0
ÁRVORE AVL
� Vamos inserir o valor 1, e recalculamos fator de 
balanceamento para cada vértice
5
FB= 2-3 = -1
3
FB=-1
8
2
FB=1-2=-1altura 
esquerda: 3 
altura 
direita: 2
FB=0
4 7
FB=0 FB=0
10
FB=0
1
FB=0
ÁRVORE AVL
� Vamos inserir o valor 6 e recalcule o fator de balanceamento 
para cada vértice
5
FB= 3-3 = 0
3
FB=-1
8
2
FB=1-2=-1
altura 
esquerda: 3 
FB=1-2=-1
4 7
FB=0 FB=-1
10
FB=0
1
FB=0
6
FB=0
altura 
direita: 3
ÁRVORE AVL
� Vamos Inserir o valor 9 e recalcular o fator de balanceamento 
dos vértices
5
FB= 3-3 = 0
3
FB=-1
8
2
FB=1-2=-1
altura 
esquerda: 3 
FB=2-2=0
4 7
FB=0 FB=-1
10
FB=-1
1
FB=0
6
FB=0
altura 
direita: 3
9
FB=0
ÁRVORE AVL
� Inserindo o ultimo valor 11 e calculando o fator de 
balanceamento para cada vértice.
5
FB= 3-3 = 0
3
FB=-1
8
2
FB=1-2=-1
altura 
esquerda: 3 
FB=2-2=0
4 7
FB=0 FB=-1
10 FB=0
1
FB=0
6
FB=0
altura 
direita: 3
9
FB=0
11
FB=0
ÁRVORE AVL
� Exercício 2:Construir uma árvore AVL com os seguintes 
dados: 20, 10, 30, 25, 27.
10
FB= 0-0 = 0
Inserindo o valor 10
ÁRVORE AVL
� Inserindo o valor 20, e calculamos o fator de balanceamento 
para cada vértice
10
FB= 1-0 = 1
20
A árvore esta balanceada porque os fatores de balanceamento são : 0 e 1.
FB=0
ÁRVORE AVL
� Inserindo o valor 30. Após a inserção calcula-se o fator de 
balanceamento para cada nó.
10
FB= 2-0 =2 + 2
Sinais iguais
rotação simples
20
FB=1-0=1
30 FB=0
Há um desbalanceamento porque o fator de balanceamento sai do seguinte limite:
[-1, 0, 1]. FB= 2. Como o desequilíbrio é para a direita então será feito uma
rotação simples a direita.
+ 1
rotação simples
ÁRVORE AVL
� Após a rotação simples à esquerda recalcula o fator de 
balanceamento.
FB=0-0=0
FB=0-0 =0 
20
10
FB=0-0=0
30 FB=0
Os fatores de balanceamento agora são iguais a 0.A árvore esta balanceada.
ÁRVORE AVL
20
FB= 2-1 = 1
� Inserir o valo 25, e calculando fator de balanceamento dos 
vértices temos:
10 30FB=0
FB=0-1=-1
25
FB=0
A árvore permanece balanceada
ÁRVORE AVL
� Inserindo o valor 27, e calculando o fator de balanceamento 
para cada vértice. Encontramos um desbalanceamento com 
FB = -2 e 2.
20
FB= 3-1 = 2
10 30FB=0-0=0
FB=0-2=-2
25
FB=1
Analisando de baixo para cima,
encontramos o primeiro fator de
desbalanceamento em -2. Como
os fatores de desbalanceamento
possuem sinais trocados então há
uma rotação dupla. Como o
desbalanceamento é para à
esquerda então a rotação será
para a direita.27
FB=0
ÁRVORE AVL
� Na rotação dupla à esquerda, primeiro rotaciona-se à direita 
aonde há fator de balanceamento igual a 1
20
FB= 3-1 = 2
10 30FB=0-0=0
FB=0-2=-2
27
FB=1
Rotação á direita
25
FB=0
27
ÁRVORE AVL
� Após a rotação direita então é feita uma rotação à esquerda. 
No fator de balanceamento igual a 2.
20
FB= 3-1 = 2
10 30FB=0-0=0
FB=0-2=-2
27
FB=1
Rotação á esquerda
25
FB=0
30
ÁRVORE AVL
� Após a rotação direita então é feita uma rotação à esquerda. 
No fator de balanceamento igual a 2.
20
FB= 2-1 = 1
10 27
FB=0
FB=0-0=0
25
FB=0
Rotação dupla á esquerda
30
FB=0