AVL - Slide

Prévia do material em texto

AVL 
Equipe 2: 
 Amanda de Paula 
 Joeline Dutra 
 Rebeca Nunes 
Conteúdo 
• História 
• Conceito 
• Fator de Balanceamento 
• Aplicação 
• Estrutura de dados 
• Rotação 
• Simples 
• Dupla 
• Qual rotação usar? 
• Inserção 
• Remoção 
História 
• Foi proposta em 1962. 
• Os matemáticos Georgy Adelson-Velsky e Evgenii Landis são 
os seus criadores. 
• A ideia era de uma árvore binária balanceada dinamicamente. 
• Ou seja, enquanto o dado está sendo inserido. 
• Este tipo de árvore ficou conhecida como árvore AVL, pelas 
iniciais dos nomes dos seus inventores 
História 
Georgy Maximovich Adelson-
Velsky 
(1922-2014) 
Evgenii Mikhailovich Landis 
(1921-1997) 
Conceito 
• O diferencial da árvore AVL é que seu balanceamento é feito 
enquanto se adiciona. 
 
• O balanceamento é feito por rotações, que podem ser simples 
ou duplas, para a direita ou para a esquerda. 
 
• A complexidade da árvore no pior caso é de 1,44 log n 
 
• Essa complexidade se deve ao fato de que a árvore é 
balanceada dinamicamente. 
 
Conceito 
• O fator chave da AVL é balanceamento. 
 
• Balanceamento é relacionado ao equilíbrio da árvore. 
 
• Se ela está maior para um lado do que para o outro, 
dependendo de seu tipo, pode não estar em equilíbrio. 
 
• Como verificar se uma árvore está balanceada? Com o fator 
de balanceamento. 
 
Fator de balanceamento 
• Enquanto para nós é algo visual, a máquina apenas processa 
dados. Logo o fator de balanceamento se torna necessário. 
• O fator de balanceamento (FB) para uma árvore AVL só pode 
ser 1, 0 ou -1. 
• O fator de balanceamento de uma folha é sempre 0. 
• FB=hD-hE 
0 
0 
+1 
0 
-1 
+1 
0 
hD 
hE 
Fator de balanceamento 
• Árvores desbalanceadas: 
 
 
 
 
 
 
9 
8 
4 
6 
5 
5 
1 
3 
9 
7 
2 
Aplicação 
• Redes de comunicação: 
• Na reconstrução de mensagens 
• Ordenando os pacotes 
• Descartando os repetidos 
 
• Codificação de Huffman: 
• Compressão e descompressão de arquivos 
 
Estrutura de dados 
• typedef struct no { 
 int chave; 
 int fb; 
 
 struct no *Pai; //Opcional 
 struct no *FilhoEsquerdo 
 struct no *FilhoDireito 
} no; 
Rotação 
• Existem 4 tipos de rotação para a árvore AVL. 
 
• Elas são: 
• Rotação para a esquerda ou Esquerda simples (RE) 
• Rotação para a direita ou Direita simples (RD) 
• Dupla rotação para a esquerda ou Rotação Direita-Esquerda (RDE) 
• Dupla rotação para a direita ou Rotação Esquerda-Direita (RED) 
 
Rotação para a esquerda 
• Balanceando: 
a 
b 
Insere c 
c 
a 
b 
FB(c)=0 
FB(b)=+1 
FB(a)=+2 
c a 
b 
c 
a 
b Rotaciona 
FB(a)=0 
FB(c)=0 
FB(b)=0 
Passo a passo 
• Ap = P; 
• Af = Ap->FilhoDireito; (F) 
• Ap->FilhoDireito= Af->FilhoEsquerdo; 
• Af->FilhoEsquerdo = Ap; 
• Ap = Af; 
P 
F 
P 
F 
Rotação para a direita 
• Balanceando: 
Insere a 
a 
c 
b 
FB(a)=0 
FB(b)=-1 
FB(c)=-2 
c a 
b 
a 
c 
b Rotaciona 
c 
b 
FB(a)=0 
FB(c)=0 
FB(b)=0 
Passo a passo 
• Ap = P; 
• Af = Ap->FilhoEsquerdo; (F) 
• Ap->FilhoEsquerdo = Af->FilhoDireito; 
• Af->FilhoDireito = Ap; 
• Ap = Af; 
P 
F P 
F 
Dupla rotação para a esquerda 
• Balanceando: 
• Primeiro a sub-árvore 
a 
c 
Insere b 
b 
a 
c 
FB(c)=0 
FB(b)=+1 
FB(a)=+2 
c 
b 
b 
c 
Resultando 
c 
a 
b 
FB(b)=0 
FB(c)=-1 
FB(a)=+2 
Rotação para 
a direita 
Dupla rotação para a esquerda 
• Voltando para a árvore: 
c a 
b 
c 
a 
b 
Rotação 
para a 
esquerda 
FB(a)=0 
FB(c)=0 
FB(b)=0 
Passo a passo 
• Ap = P; 
• Af = Ap->FilhoDireito; (F) 
• An = Af->FilhoEsquerdo; (N) 
• Af->FilhoEsquerdo = An->FilhoDireito; 
• An->FilhoDireito = Af; 
• Ap->FilhoDireito = An->FilhoEsquerdo; 
• An->FilhoEsquerdo = Ap; 
• Ap = An; 
N 
P 
F 
N 
P F 
Dupla rotação para a direita 
• Balanceando: 
• Primeiro a sub-árvore 
Insere b 
FB(b)=0 
FB(a)=+1 
FB(c)=-2 
c 
a 
b 
c 
a 
FB(c)=0 
FB(b)=-1 
FB(a)=-2 
b 
a 
a 
b 
Resultando Rotação para 
a esquerda 
a 
c 
b 
Dupla rotação para a direita 
• Voltando para a árvore: 
c a 
b 
Rotação 
para a 
direita 
FB(a)=0 
FB(c)=0 
FB(b)=0 
a 
c 
b 
Passo a passo 
• Ap = P; 
• Af = Ap->FilhoEsquerdo; (F) 
• An = Af->FilhoDireito; (N) 
• Af->FilhoDireito = An->FilhoEsquerdo; 
• An->FilhoEsquerdo = Af; 
• Ap->FilhoEsquerdo = An->FilhoDireito; 
• An->FilhoDireito = Ap; 
• Ap = An; 
N 
P 
F 
N 
P F 
Qual rotação usar? 
Diferença de 
altura de um nó 
Diferença de altura do nó 
filho do nó desbalanceado 
Tipo de rotação 
2 
1 Simples à esquerda 
-1 
Dupla com filho para a 
direita e pai para a 
esquerda 
-2 
1 
Dupla com filho para a 
esquerda e pai para a 
direita 
-1 Simples à direita 
Inserção 
• Do mesmo modo que na árvore binária. 
• Inserir e calcular o FB. 
• Se FB for diferente de -1, 0 e 1, fazer rotação até que esteja 
novamente balanceada. 
 
• Exemplo: 
 
Remoção 
• Remoção normal como em ABB 
• Rebalanceamento 
Dúvidas? 
Referências 
• Geral: 
• WALKER, Julienne. AVL trees. Disponível em: 
http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut
_avl.aspx 
• Criadores da AVL: 
• WIKIPEDIA. Evgenii Landis. Disponível em: 
http://en.wikipedia.org/wiki/Evgenii_Landis 
• WIKIPEDIA. Georgy Adelson-Velsky. Disponível em: 
http://en.wikipedia.org/wiki/Georgy_Adelson-Velsky 
• Fator de balanceamento: 
• Árvore AVL. Disponível em: 
http://www.passeidireto.com/arquivo/2536633/arvore-avl 
Referências 
• Complexidade e aplicação: 
• TOFFOLO, Túlio. Árvores AVL. Disponível em: 
http://www.decom.ufop.br/toffolo/site_media/uploads/2011-
1/bcc202/slides/25._arvores_%28parte_2%29.pdf 
• Codificação de Huffman: 
• BORGES, Henrique. Algoritmo de Huffman. Disponível em: 
http://www.youtube.com/watch?v=2yWfo50jZiw 
• COSTA, Jean. Algoritmo de Huffman. Disponível em: 
http://www.youtube.com/watch?v=MXI4LWgDucA 
• WIKIPÉDIA. Codificação de Huffman. Disponível em: 
http://pt.wikipedia.org/wiki/Codifica%C3%A7%C3%A3o_de_Huff
man 
 
Referências 
• Estrutura de dados: 
• DUTRA, Caio. Árvore Binária AVL. Disponível em: 
http://www.vivaolinux.com.br/script/Arvore-binaria-AVL 
• Rotação: 
• ANDRADE, Lívia. Árvores AVL. Disponível em: 
http://www.passeidireto.com/arquivo/1012626/aula-5_arvore-
avl 
• HARGROVE, John. The AVL Tree Rotations Tutorial. Disponível em: 
http://pages.cs.wisc.edu/~paton/readings/liblitVersion/AVL-Tree-
Rotations.pdf 
• NASCIMENTO, Edson. Árvore AVL. Disponível em: 
http://colabweb.ufam.edu.br/pluginfile.php/14107/mod_resourc
e/content/3/aed2_10_Arvore%20AVL.pdf 
Referências 
• Inserção e Remoção: 
• BUENO, Letícia. Árvores AVL. Disponível em: 
http://professor.ufabc.edu.br/~leticia.bueno/classes/aed2/materi
ais/avl.pdf 
• MORRIS, John. AVL trees. Disponível em: 
https://www.cs.auckland.ac.nz/software/AlgAnim/AVL.html