Estruturas de Dados - Árvores AVL

Prévia do material em texto

ÁRVORES AVL
Rosaura E. S. da Silva
Estrutura de Dados
Árvores Balanceadas
z Uma árvore é dita balanceada quando as suas subárvores à
esquerda e à direita possuem a mesma altura.
z Todos os links vazios estão no mesmo nível, ou seja, que a árvore 
está completa.
z A árvore que não está balanceada, define-se como degenerada
Árvores Balanceadas
Balanceamento Estático
- O balanceamento estático de uma árvore binária consiste
em construir uma nova versão, reorganizando-a.
Balanceamento Dinâmico: AVL
{ Árvore AVL em homenagem aos matemáticos russos 
(Adelson-Velskii e Landism -1962)
{ 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
Árvores 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)
O Fator de uma folha é sempre Zero (0)
Árvores Balanceadas
z Exemplos de árvores AVL e árvores não-AVL.
z Os números nos nodos representam o FB para cada nodo.
z Para uma árvore ser AVL os fatores de balanço devem ser 
necessariamente -1, 0, ou 1.
Árvores AVL
Árvores Não AVL
Balanceamento de AVL
z Inicialmente inserimos um novo nodo na árvore.
z A inserção deste novo nodo pode ou não violar a propriedade de 
balanceamento.
z Caso a inserção do novo nodo não viole a propriedade de 
balanceamento podemos então continuar inserindo novos nodos.
z 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.
Árvores AVL
z Se quisermos manter a árvore balanceada a cada 
inserção, devemos ter um algoritmo que ajuste os fatores 
de balanceamento
z O algoritmo corrige a estrutura través de movimentação 
dos nós, ao que chamamos de “rotação”.
Árvores Balanceadas
z Exemplos
z Vamos considerar a seguinte árvore (os números ao lado dos nodos 
são o FB de cada nodo):
•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.
Tipo 1 – Rotação Dupla
z Ao inserir o número 5 na árvore. Esta inserção 
produziria a seguinte árvore:
•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.
Tipo 1 – Rotação Dupla
A seguir rotaciona-se o nodo que tinha FB -2 na direção oposta
(direita neste caso).
Tipo 1 – Rotação Dupla
•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.
Tipo 2 – Rotação Simples
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 4 com 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.
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.
A descrição do algoritmo em pseudo-código para a 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 
a
propriedade AVL é violada neste nodo, ou seja, teste se o FB 
deste
nodo é maior do que abs(1). Temos aqui 2 possibilidades:
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.
Se o nodo recém-testado não tem pai, ou seja, é o nodo raiz 
da
árvore, volte para inserir novo nodo (Passo 1)
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.
2. Se FB+ rotação para esquerda
3. Se FB- rotação para direita
Referências:
Bibliografia:
Luzzardi, Paulo Roberto Gomes - Estrutura da Dados. UCPel
Sites:
www.fw.uri.br/~elisa/estrutura/arvores_avl_b_2.pdf
Simulação:
http://www.site.uottawa.ca/~stan/csi2514/applets/avl/BT.html
	ÁRVORES AVL
	Árvores Balanceadas
	Árvores Balanceadas
	Árvores AVL
	Árvores Balanceadas
	Balanceamento de AVL
	Árvores AVL
	Árvores Balanceadas
	Tipo 1 – Rotação Dupla
	Tipo 1 – Rotação Dupla
	Tipo 1 – Rotação Dupla
	Tipo 2 – Rotação Simples
	Tipo 2 – Rotação Simples
	A descrição do algoritmo em pseudo-código para a construçãode uma árvore AVL:
	Dicas: Árvores AVL
	Referências: