Árvores AVL

Prévia do material em texto

Estrutura de Dados II
ÁRVORES AVL
PROF. MSC. ROMUERE SILVA 1
Introdução
AVL = (Adelson-Velskii e Landis, 1962);
Conhecida também como Árvore Binária Balanceada;
É aquela na qual as alturas das sub-árvores da esquerda e da direita de qualquer nó diferem de 
no máximo 1 (um);
Essa diferença é chamada fator de balanceamento do nodo. Logo, numa AVL o fator de 
balanceamento de qualquer só pode ser -1, 0 ou 1.
Se o valor do balanceamento do nó for diferente de 1, -1 e 0, essa árvore não é AVL.
PROF. MSC. ROMUERE SILVA 2
Struct para AVL
struct avl{
int FB;
struct avl *esq, *dir;
int info;
};
typedef struct avl AVL;
PROF. MSC. ROMUERE SILVA 3
Fator de Balanceamento
FB(N) = Altura(sub-árvore da esquerda) – Altura(sub-árvore da direita)
◦ Se FB (N) = 0, as duas sub-árvores têm a mesma altura;
◦ Se FB (N) > 0, a sub-árvore direita é mais alta que a esquerda;
◦ Se FB(N) < 0, a sub-árvore esquerda é mais alta que a direita.
Em uma AVL, |FB(N)| ≤ 1 para todos os nodos
PROF. MSC. ROMUERE SILVA 4
Exemplo
PROF. MSC. ROMUERE SILVA 5
Fator de Balanceamento e Altura
int FB (AVL* p)
{
if (p == NULL)
return 0;
return (Altura(p.esq) - Altura(pRaiz.dir));
}
PROF. MSC. ROMUERE SILVA 6
int Altura(AVL* p){
int iEsq, iDir;
if (p == NULL)
return 0;
iEsq = Altura(p.esq);
iDir = Altura(p.dir);
if ( iEsq > iDir )
return iEsq + 1;
else
return iDir + 1;
}
AVL
Se a probabilidade de pesquisar um dado for a mesma para todos os dados, uma árvore binária 
balanceada determinará a busca mais eficiente;
Mas os algoritmos de inserção e remoção já vistos até agora não garantem que essa árvore 
permanecerá balanceada.
PROF. MSC. ROMUERE SILVA 7
AVL
PROF. MSC. ROMUERE SILVA 8
B
U
B
U U U
U U
Inserção numa árvore AVL
A inserção de um novo nodo é feita exatamente como numa árvore de pesquisa convencional.
Para manter uma árvore balanceada, é necessário fazer uma transformação na árvore tal que:
◦ O percurso em ordem da árvore transformada seja o mesmo da árvore original (isto é, a árvore 
transformada continue sendo um árvore de busca binária);
◦ A árvore transformada fique balanceada.
Se esta inserção implicar em |FB| > 1 para algum(s) ancestral(ais) do nodo inserido, o 
desequilíbrio é corrigido através de rotação de nós.
A rotação poderá ser feita à esquerda ou à direita dependendo do desbalanceamento que tiver 
que ser solucionado.
Dependendo do desbalanceamento a ser solucionado, apenas uma rotação não será suficiente 
para resolvê-lo.
PROF. MSC. ROMUERE SILVA 9
Rotação Simples
Dado um nó A, podemos ter o Nó raiz com FB 2 ou –2 com um filho (na direção de onde houve a 
inserção) com FB 1 ou –1 com o mesmo sinal, neste caso a solução é uma rotação simples.
Rotação à direita:
◦ FB do pai e do filho possuem sinal negativo (-2 e -1);
Rotação à esquerda:
◦ FB do pai e do filho possuem sinal positivo (2 e 1).
PROF. MSC. ROMUERE SILVA 10
Rotação Simples
Rotação à Direita:
Rotação à Esquerda:
PROF. MSC. ROMUERE SILVA 11
Rotação dupla
2 rotações simples, cada uma para um lado;
Nó raiz com FB 2 ou –2 com um filho (na direção de onde houve a inserção) com FB -1 ou 1 os 
quais possuem sinais trocados, neste caso a solução é uma rotação dupla;
Primeiro é rotacionado o nó com fator de balanceamento 1 ou –1 na direção apropriada e 
depois é rotacionado o nó cujo fator de balanceamento seja 2 ou –2 na direção oposta, ou seja, 
primeiro o nó filho depois o nó pai;
Dupla rotação à direita:
◦ FB do pai é Negativo, e FB do filho é positivo;
◦ Rotação à direita + rotação à esquerda.
Dupla rotação à esquerda:
◦ FB do pai é Positivo, e FB do filho é negativo;
◦ Rotação à esquerda + rotação à direita.
PROF. MSC. ROMUERE SILVA 12
Rotação dupla
Dupla rotação à direita:
Dupla rotação à esquerda:
PROF. MSC. ROMUERE SILVA 13
Algoritmo de Rotação à esquerda
Dado um nó raiz X:
Seja Y o filho à direita de X;
Torne o filho à esquerda de Y o filho à direita de X;
Torne X filho à esquerda de Y.
PROF. MSC. ROMUERE SILVA 14
Algoritmo de Rotação à direita
Dado um nó raiz X:
Seja Y o filho à esquerda de X;
Torne o filho à direita de Y o filho à esquerda de X;
Torne X filho à direita de Y.
PROF. MSC. ROMUERE SILVA 15
Algoritmo de Rotação dupla à esquerda
Algoritmo para rotação dupla à esquerda;
Algoritmo para rotação dupla à direita;
PROF. MSC. ROMUERE SILVA 16
Algoritmo de Rotação dupla à esquerda
Algoritmo para rotação dupla à direita;
Algoritmo para rotação dupla à esquerda;
PROF. MSC. ROMUERE SILVA 17
Atividades
Crie um TAD para AVL;
Defina em C uma estrutura de dados que possa representar uma árvore AVL;
Implemente o algoritmo para calcular FB e a altura;
Implemente o algoritmo para inserir em uma árvore;
Implemente o algoritmo para remover em uma árvore;
Implemente procedimento que percorra a árvore e imprima o fator de balanceamento de cada 
nó com o seguinte formato:
◦ n(FB), onde n é uma raiz de sub-árvore e FB o fator de balanceamento.
Implemente os algoritmos de rotação simples e dupla.
PROF. MSC. ROMUERE SILVA 18