Árvore Binária Balanceada - AVL

Prévia do material em texto

Árvore AVL
• Árvore binária balanceada
• Proposta por Adelson-Velskii e Landis (1962)
• Fator de balanceamento
• Cada nó armazena a altura das suas sub-
árvores.
26/08/2021 Árvore Binária Balanceada (AVL) 2
Árvore AVL
• Árvore binária balanceada
– Uma árvore é considerada AVL se, e somente
se, para cada um de seus nós, as alturas das
sub-árvores à direita e à esquerda forem
iguais, ou diferem em apenas uma unidade.
• Fator de balanceamento
– Responsável por mostrar quando a árvore está
desbalanceada.
26/08/2021 Árvore Binária Balanceada (AVL) 3
Árvore AVL - Vantagens
• Foi a primeira estrutura de dados a oferecer operações
de inserção, remoção e busca em tempo O(log n)
(algoritmo muito rápido).
• Em média, uma árvore desbalanceada de 10.000 nós,
são necessárias 5.000 comparações O(n/2) para efetuar
uma busca, já numa árvore AVL essa média baixa para
14 comparações.
• Deixando a árvore com o menor altura possível
(balanceada), o custo de algoritmo (busca, inserção e
remoção de dados) diminui, deixando-o mais rápido.
26/08/2021 Árvore Binária Balanceada (AVL) 4
Árvore AVL
• Uma árvore é AVL se ((Hd - He) < 2)
26/08/2021 Árvore Binária Balanceada (AVL) 5
Árvore AVL
• Uma árvore não é AVL se ((Hd - He) >= 2)
26/08/2021 Árvore Binária Balanceada (AVL) 6
Árvore AVL
26/08/2021 Árvore Binária Balanceada (AVL) 7
Fator de Balanceamento
• Para cada nó, define-se um fator de balanceamento
(FatBal) que deve ser -1, 0 ou +1 para que a árvore esteja
balanceada.
• Calculado pela diferença entre a sub-árvore da direita e
sub-árvore da esquerda. Ele é o responsável por avisar se
a árvore está ou não balanceada.
– FatBal = altura (sub-árvore direita) – altura (sub-árvore esquerda)
– FatBal = -1, quando a sub-árvore da esquerda é maior que a direita em uma 
unidade. 
– FatBal = 0, quando as duas sub-árvores tem a mesma altura.
– FatBal = +1, quando a sub-árvore da direita é maior que a esquerda em uma 
unidade.
26/08/2021 Árvore Binária Balanceada (AVL) 8
Fator de Balanceamento
• Toda vez que é realizada uma operação na árvore
(inserção/remoção de registros) o fator de
balanceamento é verificado.
• A inserção/remoção pode ou não alterar as propriedades
de balanceamento.
– Caso a inserção/remoção não afete as propriedades de
balanceamento, pode-se inserir/remover registros sem
problemas.
– Caso a inserção/remoção afete as propriedades de
balanceamento, nesse caso é necessário balancear a árvore.
Isso é feito através do processo de ROTAÇÃO.
26/08/2021 Árvore Binária Balanceada (AVL) 9
ROTAÇÃO DA ÁRVORE
• Existem 4 tipos de rotações para a Árvore
AVL:
–Rotação simples à esquerda
–Rotação simples à direita
–Rotação dupla à esquerda
–Rotação dupla à direita
26/08/2021 Árvore Binária Balanceada (AVL) 10
ROTAÇÃO DA ÁRVORE
• Rotação simples à esquerda (EE)
26/08/2021 Árvore Binária Balanceada (AVL) 11
• Rotação simples à direita (DD)
26/08/2021 Árvore Binária Balanceada (AVL) 12
ROTAÇÃO DA ÁRVORE
ROTAÇÃO DA ÁRVORE
• Rotação dupla à esquerda (DE)
(rotação simples à direita + rotação simples à esquerda)
26/08/2021 Árvore Binária Balanceada (AVL) 13
ROTAÇÃO DA ÁRVORE
• Rotação dupla à direita (ED)
(rotação simples à esquerda + rotação simples à direita)
26/08/2021 Árvore Binária Balanceada (AVL) 14
ROTAÇÃO DA ÁRVORE
Para identificar quando uma rotação é simples ou
dupla deve-se observar os sinais do FatBal:
– Se o sinal do FatBal for igual, a rotação é simples
– Se o sinal do FatBal for diferente, a rotação é dupla
– Se FatBal for positivo, a rotação é para a esquerda
– Se FatBal for negativo, a rotação é para a direita
26/08/2021 Árvore Binária Balanceada (AVL) 15
OPERAÇÕES CRÍTICAS
Quais são as operações que podem causar
desbalanceamento na árvore?
26/08/2021 Árvore Binária Balanceada (AVL) 16
OPERAÇÕES CRÍTICAS
Quais são as operações que podem causar
desbalanceamento na árvore?
• INSERÇÃO DE ELEMENTOS
26/08/2021 Árvore Binária Balanceada (AVL) 17
OPERAÇÕES CRÍTICAS
Quais são as operações que podem causar
desbalanceamento na árvore?
• INSERÇÃO DE ELEMENTOS
• REMOÇÃO DE ELEMENTOS
26/08/2021 Árvore Binária Balanceada (AVL) 18
INSERÇÃO DE ELEMENTOS
• Sempre ocorre nos nós folhas
– Pode ocasionar:
• Aumento da altura da sub-árvore
• Alteração dos fatores de balanceamento
• Algoritmo de Inserção
– Efetuar a inserção do elemento desejado
– Atualizar os fatores de balanceamento
– Verificar o balanceamento da árvore
– Se a árvore não estiver balanceada, corrigir a
estrutura através de rotações
26/08/2021 Árvore Binária Balanceada (AVL) 19
INSERÇÃO DE ELEMENTOS - ALGORITMO
• Inserir como se fosse em uma árvore Binária
de Busca (mesmo procedimento);
• Na “volta” da recursão verificamos nós que
violam o balanceamento AVL, pois apenas
sub-árvores que contém o elemento inserido
mudaram de altura;
• Correção dos nós desbalanceados (só podem
ser os ancestrais)
– Casos: EE, DD, ED e DE
26/08/2021 Árvore Binária Balanceada (AVL) 20
INSERÇÃO DE ELEMENTOS
• Rotação Simples à Esquerda – Exemplo:
26/08/2021 Árvore Binária Balanceada (AVL) 21
Inserir 22
INSERÇÃO DE ELEMENTOS
• Rotação Simples à Esquerda – Exemplo:
26/08/2021 Árvore Binária Balanceada (AVL) 22
Inserir 22
INSERÇÃO DE ELEMENTOS
• Rotação Simples à Direita – Exemplo:
26/08/2021 Árvore Binária Balanceada (AVL) 23
Inserir 27
INSERÇÃO DE ELEMENTOS
• Rotação Simples à Direita – Exemplo:
26/08/2021 Árvore Binária Balanceada (AVL) 24
Inserir 27
INSERÇÃO DE ELEMENTOS
• Rotação Dupla à Esquerda – Exemplo:
26/08/2021 Árvore Binária Balanceada (AVL) 25
Inserir 25
INSERÇÃO DE ELEMENTOS
• Rotação Dupla à Esquerda – Exemplo:
26/08/2021 Árvore Binária Balanceada (AVL) 26
Inserir 25
INSERÇÃO DE ELEMENTOS
• Rotação Dupla à Direita – Exemplo:
26/08/2021 Árvore Binária Balanceada (AVL) 27
Inserir 28
INSERÇÃO DE ELEMENTOS
• Rotação Dupla à Direita – Exemplo:
26/08/2021 Árvore Binária Balanceada (AVL) 28
Inserir 28
REMOÇÃO DE ELEMENTOS
• Considere que o elemento a ser removido
encontra-se na raiz da árvore T:
– A raiz não possui filhos. Deve-se remover a raiz e
anular T;
– A raiz possui um único filho. Nesse caso, deve-se
remover a raiz e substituí-la por seu filho;
– A raiz possui dois filhos. Nesse caso, deve-se
escolher o nó que armazena o menor elemento na
sub-árvore direita e substituir a raiz por ele.
26/08/2021 Árvore Binária Balanceada (AVL) 29
REMOÇÃO DE ELEMENTOS - ALGORITMO
• Remover o elemento desejado como em um
árvore BB;
• Na “volta” da recursão verificamos nós que
violam o balanceamento AVL;
• Correção dos nós desbalanceados (só podem
ser os ancestrais)
• Diferenças com a inserção:
– Uma situação a mais no EE e no DD
– Alguns casos alteram a altura da sub-árvore
26/08/2021 Árvore Binária Balanceada (AVL) 30
REMOÇÃO DE ELEMENTOS
• Rotação Simples à Esquerda – Exemplo:
26/08/2021 Árvore Binária Balanceada (AVL) 31
REMOÇÃO DE ELEMENTOS
• Rotação Simples à Esquerda – Exemplo:
26/08/2021 Árvore Binária Balanceada (AVL) 32
REMOÇÃO DE ELEMENTOS
• Rotação Simples à Direita – Exemplo:
26/08/2021 Árvore Binária Balanceada (AVL) 33
REMOÇÃO DE ELEMENTOS
• Rotação Simples à Direita – Exemplo:
26/08/2021 Árvore Binária Balanceada (AVL) 34
REMOÇÃO DE ELEMENTOS
• Rotação Dupla à Esquerda – Exemplo:
26/08/2021 Árvore Binária Balanceada (AVL) 35
REMOÇÃO DE ELEMENTOS
• Rotação Dupla à Esquerda – Exemplo:
26/08/2021 Árvore Binária Balanceada (AVL) 36
REMOÇÃO DE ELEMENTOS
• Rotação Dupla à Direita – Exemplo:
26/08/2021 Árvore Binária Balanceada (AVL) 37
REMOÇÃO DE ELEMENTOS
• Rotação Dupla à Direita – Exemplo:
26/08/2021 Árvore Binária Balanceada (AVL) 38
REFERÊNCIAS
• SZWARCFITER, Jayme Luiz; MARKENZON, Lilian. Estruturas
de Dados e seus Algoritmos. 2. ed. rev. Rio de Janeiro: LTC, 
1994.
• M. T. GOODRICH et al.
– Estruturas de Dados e Algoritmos em Java
– Data Structures and Algorithms in Java
– Data Structures and Algorithms in C++
– Lectures Slides
• H. T. CORMEN et al
– Introductionto Algorithms
– Algoritmos - Teoria e Prática
26/08/2021 Árvore Binária Balanceada (AVL) 39
Material Extra!
• https://www.cs.usfca.edu/~galles/visualizatio
n/AVLtree.html
26/08/2021 Árvore Binária Balanceada (AVL) 40
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html