AULA_9_AVL

Prévia do material em texto

Algoritmo e Estrutura de Dados II 
COM 112 
Vanessa Souza 
Universidade Federal de Itajubá – Instituto de Matemática e Computação 
Aula 9 
Implementação da AVL 
 Cada vez que um nó é inserido ou removido da árvore, é 
preciso: 
 Atualizar o fator de balanceamento do caminho onde o nó foi 
inserido ou removido 
 Verificar se a árvore continua balanceada 
 Se o balanceamento se desfez, aplicar as rotações para 
reestabelecer o balanceamento da árvore 
 
 Lembrar que existe uma prova matemática que garante 
que, ao balancear a sub-árvore que se desbalanceou com 
a inserção/remoção, a árvore toda volta ao estado 
balanceado. 
Implementação da AVL – INSERÇÃO 
Inserir nó x 
Atualiza Fator Balanceamento 
Verifica Balanceamento 
Rotações 
Desbalanceou? 
Implementação da AVL – INSERÇÃO 
Inserir nó x 
Atualiza Fator Balanceamento 
Verifica Balanceamento 
Rotações 
Desbalanceou? 
Implementação da AVL – INSERÇÃO 
Inserir nó x 
Atualiza Fator Balanceamento 
Verifica Balanceamento 
Rotações 
Desbalanceou? 
Implementação da AVL – INSERÇÃO 
 
 
 Atualiza o balanceamento do nó pai 
 Como? 
 Se aumentou a profundidade da 
árvore, atualiza recursivamente o 
balanceamento 
 Como saber se a profundidade da árvore 
aumentou? 
 Até quando a recursividade? 
 
 
 
 
Inserir nó x 
Atualiza Fator Balanceamento 
Verifica Balanceamento 
Rotações 
Desbalanceou? 
Implementação da AVL – INSERÇÃO 
Inserir nó x 
Atualiza Fator Balanceamento 
Verifica Balanceamento 
Rotações 
Desbalanceou? 
Implementação da AVL – INSERÇÃO 
Inserir nó x 
Atualiza Fator Balanceamento 
Verifica Balanceamento 
Rotações 
Desbalanceou? 
Implementação da AVL – INSERÇÃO 
Inserir nó x 
Atualiza Fator Balanceamento 
Verifica Balanceamento 
Rotações 
Desbalanceou? 
Implementação da AVL – INSERÇÃO 
Inserir nó x 
Atualiza Fator Balanceamento 
Verifica Balanceamento 
Rotações 
Desbalanceou? 
Implementação da AVL – INSERÇÃO 
 
 
 
 
Diferença 
de altura no 
nó 
Diferença de altura 
do nó filho do nó 
desbalanceado 
Tipo de rotação 
 
2 
1 Simples à direita 
0 Simples à direita 
-1 Dupla : esquerda – 
direita 
 
-2 
1 Dupla : direita- 
esquerda 
0 Simples à esquerda 
-1 Simples à esquerda 
Inserir nó x 
Atualiza Fator Balanceamento 
Verifica Balanceamento 
Rotações 
Desbalanceou? 
Implementação da AVL – INSERÇÃO 
Inserir nó x 
Atualiza Fator Balanceamento 
Verifica Balanceamento 
Rotações 
Desbalanceou? 
Implementação da AVL – INSERÇÃO 
 Rotação simples à esquerda 
 
 
 
 
 O FB de x e de q passa a ser 0 
 
 
 
 
Inserir nó x 
Atualiza Fator Balanceamento 
Verifica Balanceamento 
Rotações 
Desbalanceou? 
Implementação da AVL – INSERÇÃO 
 Rotação simples à direita 
 
 
 
 
 O FB de x e de q passa a ser 0 
 
 
 
 
Inserir nó x 
Atualiza Fator Balanceamento 
Verifica Balanceamento 
Rotações 
Desbalanceou? 
Implementação da AVL – INSERÇÃO 
 Rotação dupla –Dir-Esq 
 
 
 
 
 O FB de x e de q passa a ser 0; 
 Se q tiver filho da esquerda, o FB é o FB 
do filho da esq + 1; 
 
 
 
Inserir nó x 
Atualiza Fator Balanceamento 
Verifica Balanceamento 
Rotações 
Desbalanceou? 
Implementação da AVL – INSERÇÃO 
 Rotação dupla –Esq-Dir 
 
 
 
 
 O FB de x e de q passa a ser 0; 
 Se q tiver filho da direita, o FB é o FB do 
filho da direita - 1; 
 
 
 
Inserir nó x 
Atualiza Fator Balanceamento 
Verifica Balanceamento 
Rotações 
Desbalanceou?