AULA e10
Algoritmos e Estruturas de Dados I
Árvores AVL – Inserção
(rotação LL)
Prof. Luciano Antonio Digiampietri
Inserções em Árvore AVL
● Realiza-se a inserção seguindo as regras de
árvores de busca binária, de maneira recursiva.
● Durante a volta da recursão, atualiza-se o
balanceamento de cada nó e verifica se ele
viola a propriedade de um árvore AVL.
● Notem que o nó inserido (balanceamento igual a
zero) e seu pai não irão violar a regra.
● Se o nó atual violar a propriedade, realiza-se
uma “rotação” para corrigira a árvore.
Inserções em Árvore AVL
-1
0 0
0 0
Inserções em Árvore AVL
-1
0 0
0 0
Inserções em Árvore AVL
-2
-1 0
1 0
0
Inserções em Árvore AVL
A partir do nó inserido:
-2 O primeiro nó com
balanceamento igual a -2,
se existir, será chamada
-1 0 de p (o “problema”)
● Seu filho, no sentido da
1 0
inserção será chamado
de u
● Seu neto, no sentido da
0 inserção será chamado
de v
Inserções em Árvore AVL
p A partir do nó inserido:
-2 O primeiro nó com
balanceamento igual a -2,
u se existir, será chamada
-1 0 de p (o “problema”)
v
● Seu filho, no sentido da
1 0
inserção será chamado
de u
● Seu neto, no sentido da
0 inserção será chamado
de v
Inserções em Árvore AVL
u
u
v p
v
Inserções em Árvore AVL
● Há quatro configurações possíveis para
p, u e v:
p p p p
30 30 10 10
u u u u
10 20 20 30
v 20 10 v v 30 20 v
Inserções em Árvore AVL
Posição relativa de u em relação à p e de v em relação à u:
Esquerda- Esquerda- Direita- Direita-
Direita Esquerda Direita Esquerda
LR LL RR RL
30 30 10 10
L L R R
10 20 20 30
R L R L
20 10 30 20
Inserções em Árvore AVL
LR LL RR RL
30 30 10 10
L L R R
10 20 20 30
R L R L
20 10 30 20
20
10 30
Rotação LL
p
-2
u A
-1
v B
?
-1/0/1
C D
Rotação LL
u
u A
v p
v B
C D
Rotação LL
p
u u
u A
v p v p
v B
C D B A
C D
Rotação LL – altura dos nós
p h
-2
h-1 u h-3
A
-1
h-2 v B h-3
?
-1/0/1
C D
h-3 ou h-4 ou
h-4 h-3
Rotação LL – altura dos nós
p h
-2
h-1 u h-3 u
A
-1
h-2 v h-2 v p
B h-3
?
-1/0/1
C D C D B A
h-3 ou h-4 ou h-3 ou h-4 ou h-3 h-3
h-4 h-3 h-4 h-3
Rotação LL – altura dos nós
p h
-2
h-1 u h-3 u h-1
A
-1
h-2 v h-2 v p h-2
B h-3
?
-1/0/1
C D C D B A
h-3 ou h-4 ou h-3 ou h-4 ou h-3 h-3
h-4 h-3 h-4 h-3
Rotação LL – balanceamento
p h
-2
h-1 u h-3
A
-1
h-2 v B h-3
?
C D
h-3 ou h-4 ou
h-4 h-3
Rotação LL – balanceamento
p h
-2
h-1 u h-3 u h-1
A
-1
h-2 v h-2 v p h-2
B h-3
?
C D C D B A
h-3 ou h-4 ou h-3 ou h-4 ou h-3 h-3
h-4 h-3 h-4 h-3
Rotação LL – balanceamento
p h
-2
h-1 u h-3 u h-1
A
-1 0
h-2 v h-2 v p h-2
B h-3
? ? 0
C D C D B A
h-3 ou h-4 ou h-3 ou h-4 ou h-3 h-3
h-4 h-3 h-4 h-3
Rotação LL – código
PONT rotacaoL(PONT p){
PONT u, v;
u = p->esq;
if(u->bal == -1) { // LL
p->esq = u->dir;
u->dir = p;
p->bal = 0;
u->bal = 0;
return u;
}
AULA e10
Algoritmos e Estruturas de Dados I
Árvores AVL – Inserção
(rotação LL)
Prof. Luciano Antonio Digiampietri