Aula 8 - Árvores AVL

Prévia do material em texto

CCT0608 ALGORITMOS AVANÇADOS
Aula 8: Árvores AVL
Prof. Dr. Roney L. de S. Santos
RONEY.LIRASALE@professores.estacio.br
Aula baseada nas notas de aula do Prof. José Baranauskas (USP) (adaptado) 
Introdução
❑Árvores de altura balanceada ou de altura equilibrada foram
introduzidas em 1962 por Adelson-Velskii e Landis, também
conhecidas como árvores AVL
❑Devido ao balanceamento da árvore, as operações de busca,
inserção e remoção em uma árvore com n elementos podem
ser efetuadas em O(log2n), mesmo no pior caso
Árvore AVL
❑Uma árvore AVL é definida como:
▪ Uma árvore vazia é uma árvore AVL
▪ Sendo T uma árvore binária de busca cujas subárvores esquerda e direita
são L e R, respectivamente, T será uma árvore AVL contanto que:
❖L e R são árvores AVL
❖|hL – hR| ≤ 1, onde hL e hR são as alturas das subárvores L e R, respectivamente
❑A definição de uma árvore binária de altura equilibrada (AVL)
requer que cada subárvore seja também de altura equilibrada
Fator de Balanceamento
❑O fator de balanceamento ou fator de equilíbrio de um
nó T em uma árvore binária é definido como sendo hL – hR
onde hL e hR são as alturas das subárvores esquerda e
direita de T, respectivamente
❑Para qualquer nó T numa árvore AVL, o fator de
balanceamento assume o valor -1, 0 ou +1
▪ O fator de balanceamento de uma folha é zero
Fator de Balanceamento
-1
+1
00
0 0
+1
00
0 0
0
-1
0 0
00
Fator de Balanceamento
-1
+1
00
0 0
+1
00
0 0
0
-1
0 0
00Fator=0 indica que as 
alturas das subárvores 
esquerda e direita são iguais
Fator de Balanceamento
-1
+1
00
0 0
+1
00
0 0
0
-1
0 0
00Fator=+1 indica que a altura 
da subárvore esquerda é 
maior que da direita
Fator de Balanceamento
-1
+1
00
0 0
+1
00
0 0
0
-1
0 0
00Fator=−1 indica que a altura 
da subárvore esquerda é 
menor que da direita
Rotações
Vídeo disponível em https://www.youtube.com/watch?v=3zmjQlJhBLM
https://www.youtube.com/watch?v=3zmjQlJhBLM
Rotações
❑ O processo de rebalanceamento é conduzido utilizando 4 tipos de rotações: LL,
RR, LR, RL
▪ LL e RR são simétricas entre si assim como LR e RL
❑ As rotações são caracterizadas pelo ancestral mais próximo A do novo nó
inserido Y cujo fator de balanceamento passa a ser +2 ou -2
▪ LL: Y inserido na subárvore esquerda da subárvore esquerda de A
▪ LR: Y inserido na subárvore direita da subárvore esquerda de A
▪ RR: Y inserido na subárvore direita da subárvore direita de A
▪ RL: Y inserido na subárvore esquerda da subárvore direita de A
❑ Seja B o filho de A no qual ocorreu a inserção de Y
▪ LL (A = +2; B = +1)
▪ LR (A = +2; B = -1)
RR (A = -2; B = -1)
RL (A = -2; B = +1)
❑ C é o filho de B no qual ocorreu a inserção de Y
Rotações
❑ O processo de rebalanceamento é conduzido utilizando 4 tipos de rotações: LL,
RR, LR, RL
▪ LL e RR são simétricas entre si assim como LR e RL
▪ LL = ROTAÇÃO À DIREITA
▪ RR = ROTAÇÃO À ESQUERDA
▪ LR = ROTAÇÃO DUPLA À DIREITA
▪ RL = ROTAÇÃO DUPLA À ESQUERDA
Rotação LL
0
B
h
h+2
Subárvore balanceada
+1
A
AR
+1
B
BL BR
Subárvore desbalanceada após inserção
+2
A
h
h+2
AR
BL BR
Subárvore rebalanceada
0
B
BL
BR
0
A
h
h+2
AR
Altura de BL aumenta para h+1
Rotação LL
B
BL BR
A
AR
❑ Assumindo pA e pB ponteiros para 
as subárvores com raízes A e B:
▪ pB = pA->LeftNode;
▪ pA->LeftNode = pB->RightNode;
▪ pB->RightNode = pA;
▪ pA = pB;
pA
Rotação LL
B
BL BR
A
AR
❑ Assumindo pA e pB ponteiros para 
as subárvores com raízes A e B:
▪ pB = pA->LeftNode;
▪ pA->LeftNode = pB->RightNode;
▪ pB->RightNode = pA;
▪ pA = pB;
pA
pB
Rotação LL
B
BL BR
A
AR
❑ Assumindo pA e pB ponteiros para 
as subárvores com raízes A e B:
▪ pB = pA->LeftNode;
▪ pA->LeftNode = pB->RightNode;
▪ pB->RightNode = pA;
▪ pA = pB;pA
pB
Rotação LL
❑ Assumindo pA e pB ponteiros para 
as subárvores com raízes A e B:
▪ pB = pA->LeftNode;
▪ pA->LeftNode = pB->RightNode;
▪ pB->RightNode = pA;
▪ pA = pB;
B
BL
BR
A
AR
pA
pB
Rotação LL
❑ Assumindo pA e pB ponteiros para 
as subárvores com raízes A e B:
▪ pB = pA->LeftNode;
▪ pA->LeftNode = pB->RightNode;
▪ pB->RightNode = pA;
▪ pA = pB;
B
BL
BR
A
AR
pApB
Rotação RR
h
h+2
0
B
Subárvore balanceada
-1
A
AL
h
h+2
h
h+2
BL BR
Subárvore rebalanceada
0
B
BR
BL
0
A
AL
-1
B
BRBL
Subárvore desbalanceada após inserção
-2
A
AL
Altura de BR aumenta para h+1
Rotação RR
❑ Assumindo pA e pB ponteiros para 
as subárvores com raízes A e B:
▪ pB = pA->RightNode;
▪ pA->RightNode = pB->LeftNode;
▪ pB->LeftNode = pA;
▪ pA = pB;
B
BRBL
A
AL
pA
Rotação RR
❑ Assumindo pA e pB ponteiros para 
as subárvores com raízes A e B:
▪ pB = pA->RightNode;
▪ pA->RightNode = pB->LeftNode;
▪ pB->LeftNode = pA;
▪ pA = pB;
B
BRBL
A
AL
pA
pB
Rotação RR
❑ Assumindo pA e pB ponteiros para 
as subárvores com raízes A e B:
▪ pB = pA->RightNode;
▪ pA->RightNode = pB->LeftNode;
▪ pB->LeftNode = pA;
▪ pA = pB;
B
BRBL
A
AL
pA pB
Rotação RR
❑ Assumindo pA e pB ponteiros para 
as subárvores com raízes A e B:
▪ pB = pA->RightNode;
▪ pA->RightNode = pB->LeftNode;
▪ pB->LeftNode = pA;
▪ pA = pB;
B
BR
BL
A
AL
pA
pB
Rotação RR
❑ Assumindo pA e pB ponteiros para 
as subárvores com raízes A e B:
▪ pB = pA->RightNode;
▪ pA->RightNode = pB->LeftNode;
▪ pB->LeftNode = pA;
▪ pA = pB;
B
BR
BL
A
AL
pA pB
Rotação LR(a)
0
B
Subárvore balanceada
+1
A
-1
B
Subárvore desbalanceada após inserção
+2
A
Subárvore rebalanceada
0
C
0
A
0
C
0
B
Rotação LR(b)
Subárvore rebalanceada
0
B
BL CR
Subárvore balanceada
+1
A
h
h+2
AR
CL
0
C
h
h-1
-1
B
BL CR
Subárvore desbalanceada após inserção
+2
A
h
h+2
AR
CL
+1
C
h
0
B
BL
CR
0
C
h+2
AR
CL
-1
A
h
Rotação LR(c)
Subárvore rebalanceada
0
B
BL CR
Subárvore balanceada
+1
A
h
h+2
AR
CL
0
C
h
h-1
-1
B
BL CR
Subárvore desbalanceada após inserção
+2
A
h
h+2
AR
CL
-1
C
h
+1
B
BL
CR
0
C
h+2
AR
CL
0
A
h
Rotação LR
B
BL
CR
A
AR
CL
C
❑ Assumindo pA, pB e pC ponteiros 
para as subárvores com raízes A, B 
e C:
▪ pB = pA->LeftNode;
▪ pC = pB->RightNode;
▪ pB->RightNode = pC->LeftNode;
▪ pC->LeftNode = pB;
▪ pA->LeftNode = pC->RightNode;
▪ pC->RightNode = pA;
▪ pA = pC;
pA
Rotação LR
B
BL
CR
A
AR
CL
C
❑ Assumindo pA, pB e pC ponteiros 
para as subárvores com raízes A, B 
e C:
▪ pB = pA->LeftNode;
▪ pC = pB->RightNode;
▪ pB->RightNode = pC->LeftNode;
▪ pC->LeftNode = pB;
▪ pA->LeftNode = pC->RightNode;
▪ pC->RightNode = pA;
▪ pA = pC;
pA
pB
Rotação LR
B
BL
CR
A
AR
CL
C
❑ Assumindo pA, pB e pC ponteiros 
para as subárvores com raízes A, B 
e C:
▪ pB = pA->LeftNode;
▪ pC = pB->RightNode;
▪ pB->RightNode = pC->LeftNode;
▪ pC->LeftNode = pB;
▪ pA->LeftNode = pC->RightNode;
▪ pC->RightNode = pA;
▪ pA = pC;
pA
pB
pC
Rotação LR
B
BL
CR
A
AR
CL
C
❑ Assumindo pA, pB e pC ponteiros 
para as subárvores com raízes A, B 
e C:
▪ pB = pA->LeftNode;
▪ pC = pB->RightNode;
▪ pB->RightNode = pC->LeftNode;
▪ pC->LeftNode = pB;
▪ pA->LeftNode = pC->RightNode;
▪ pC->RightNode = pA;
▪ pA = pC;
pA
pB
pC
Rotação LR
B
BL
CR
A
AR
CL
C
❑ Assumindo pA, pB e pC ponteiros 
para as subárvores com raízes A, B 
e C:
▪ pB = pA->LeftNode;
▪ pC = pB->RightNode;
▪ pB->RightNode = pC->LeftNode;
▪ pC->LeftNode = pB;
▪ pA->LeftNode = pC->RightNode;
▪ pC->RightNode = pA;
▪ pA = pC;
pB
pC pA
Rotação LR
B
BL
CR
A
AR
CL
C
❑ Assumindo pA, pB e pC ponteiros 
para as subárvores com raízes A, B 
e C:
▪ pB = pA->LeftNode;
▪ pC = pB->RightNode;
▪ pB->RightNode = pC->LeftNode;
▪ pC->LeftNode = pB;
▪ pA->LeftNode = pC->RightNode;
▪ pC->RightNode = pA;
▪ pA = pC;
pApB
pC
Rotação LR
B
BL
CR
A
AR
CL
C
❑ Assumindo pA, pB e pC ponteiros 
para as subárvores com raízes A, B 
e C:
▪ pB = pA->LeftNode;
▪ pC = pB->RightNode;
▪ pB->RightNode = pC->LeftNode;
▪ pC->LeftNode =pB;
▪ pA->LeftNode = pC->RightNode;
▪ pC->RightNode = pA;
▪ pA = pC;
pApB
pC
Rotação LR
B
BL
CR
A
AR
CL
C
❑ Assumindo pA, pB e pC ponteiros 
para as subárvores com raízes A, B 
e C:
▪ pB = pA->LeftNode;
▪ pC = pB->RightNode;
▪ pB->RightNode = pC->LeftNode;
▪ pC->LeftNode = pB;
▪ pA->LeftNode = pC->RightNode;
▪ pC->RightNode = pA;
▪ pA = pC;
pA
pB
pC
Rotação RL(a)
0
B
Subárvore balanceada
-1
A
+1
B
Subárvore desbalanceada após inserção
-2
A
0
C
Subárvore rebalanceada
0
C
0
A
0
B
Rotação RL(b)
Subárvore rebalanceada
0
B
BRCL
Subárvore balanceada
-1
A
h
h+2
AL
CR
0
C
h
h-1
-1
B
BR
CL
0
C
h+2
AL
CR
0
A
h
+1
B
BRCL
Subárvore desbalanceada após inserção
-2
A
h
h+2
AL
CR
+1
C
h
Rotação RL(c)
Subárvore rebalanceada
0
B
BRCL
Subárvore balanceada
-1
A
h
h+2
AL
CR
0
C
h
h-1
0
B
BR
CL
0
C
h+2
AL
CR
+1
A
h
+1
B
BRCL
Subárvore desbalanceada após inserção
-2
A
h
h+2
AL
CR
-1
C
h
Inserções
❑Inserir x=7
-1
4
0
5
Inserções
❑Inserido x=7
❑A inserção produz 
uma árvore 
desbalanceada...
-2
4
-1
5
0
7
Inserções
❑Inserido x=7
❑A inserção produz 
uma árvore 
desbalanceada, cujo 
balanceamento 
envolve uma rotação 
RR
0
4
0
5
0
7
Inserções
❑Inserir x=2
0
4
0
5
0
7
Inserções
❑Inserido x=2
+1
4
+1
5
0
7
0
2
Inserções
❑Inserido x=2
❑Inserir x=1
+1
4
+1
5
0
7
0
2
Inserções
❑Inserido x=2
❑Inserido x=1
❑Ocorre 
desbalanceamento da 
subárvore de raiz 4...
+2
4
+2
5
0
7
+1
2
0
1
Inserções
❑Inserido x=2
❑Inserido x=1
❑Ocorre 
desbalanceamento da 
subárvore de raiz 4, 
que é corrigido por 
uma rotação LL
0
2
+1
5
0
7
0
1
0
4
Inserções
❑Inserir x=3
0
2
+1
5
0
7
0
1
0
4
Inserções
❑Inserido x=3
❑Ocorre 
desbalanceamento da 
subárvore de raiz 5...
-1
2
+2
5
0
7
0
1
+1
4
0
3
Inserções
❑Inserido x=3
❑Ocorre 
desbalanceamento da 
subárvore de raiz 5, 
que é corrigido por 
uma rotação LR
0
2
0
4
-1
5
0
1
0
3
0
7
Inserções
❑Inserir x=6
0
2
0
4
-1
5
0
1
0
3
0
7
Inserções
❑Inserido x=6
❑Ocorre 
desbalanceamento da 
subárvore de raiz 5...
0
2
-1
4
-2
5
0
1
0
3
+1
7
0
6
Inserções
❑Inserido x=6
❑Ocorre 
desbalanceamento da 
subárvore de raiz 5, 
que é corrigido por 
uma rotação RL
0
2
0
4
0
6
0
1
0
3
0
7
0
5
Remoção
+1
3
0
4
+1
2
0
1
0
5
0
8
+1
7
0
10
0
11
0
9
0
6
Antes da remoção Depois do rebalanceamento
Remoção
0
2
0
3
0
1
-1
5
0
8
+1
7
0
10
0
11
0
9
0
6
LL
+2
3
+1
2
0
1
0
5
0
8
+1
7
0
10
0
11
0
9
0
6
Depois da remoção Depois do rebalanceamento
0
2
0
3
0
1
-1
5
0
8
+1
7
0
10
0
11
0
9
0
6
Remoção
Obs: foi utilizado o maior elemento da subárvore esquerda do nó sendo removido
Antes da remoção Depois do rebalanceamento
Remoção
0
2
0
3
0
1
-1
5
-1
7
0
6
0
10
0
11
0
9
Obs: foi utilizado o maior elemento da subárvore esquerda do nó sendo removido
Depois da remoção Depois do rebalanceamento
Sem necessidade 
de rebalanceamento
Remoção
0
2
0
3
0
1
-1
5
-1
7
0
6
0
10
0
11
0
9
Antes da remoção Depois do rebalanceamento
Remoção
0
2
0
3
0
1
-1
5
+1
10
-1
7
0
11
0
9
0
2
0
3
0
1
-1
5
-2
7
0
10
0
11
0
9
RR
Depois da remoção Depois do rebalanceamento
0
2
0
3
0
1
-1
5
+1
10
-1
7
0
11
0
9
Remoção
Antes da remoção Depois do rebalanceamento
A remoção de nós que tem filhos é dada pela substituição pelo imediatamente maior ou menor. Aqui escolhemos o menor.
+1
2
0
1
-1
3
+1
10
-1
7
0
11
0
9
Remoção
Depois da remoção Depois do rebalanceamento
Sem necessidade 
de rebalanceamento
+1
2
0
1
-1
3
+1
10
-1
7
0
11
0
9
Remoção
Antes da remoção Depois do rebalanceamento
0
1
-2
3
+1
10
-1
7
0
11
0
9
Remoção
+1
3
0
1
0
7
0
10
0
9
0
11
RL
Depois da remoção Depois do rebalanceamento
+1
3
0
1
0
7
0
10
0
9
0
11
Remoção
0
3
-1
7
0
10
0
9
0
11
Antes da remoção Depois do rebalanceamento
0
3
-1
7
0
10
0
9
0
11
Remoção
Depois da remoção Depois do rebalanceamento
Sem necessidade 
de rebalanceamento
Remoção
0
3
-1
7
0
10
0
9
0
11
Antes da remoção Depois do rebalanceamento
Remoção
-1
3
+1
10
0
11
0
9
-2
3
0
10
0
9
0
11
RR
Depois da remoção Depois do rebalanceamento
-1
3
+1
10
0
11
0
9
Remoção
Antes da remoção Depois do rebalanceamento
-1
3
+2
10
0
9
Remoção
0
3
0
9
0
10
LR
Antes da remoção Depois do rebalanceamento
Atividade Verificadora de Aprendizado 5 
❑Implementar o algoritmo de Árvores AVL, contendo:
❑Criação da árvore
❑Inserção de elementos na árvore
❑Remoção de elementos na árvore
❑Rotações (LL, RR, LR, RL)
❑Fator de balanceamento
❑Entrega até sexta-feira, 02 de junho de 2023, às 23h59 pelo e-mail 
RONEY.LIRASALE@professores.estacio.br
mailto:RONEY.LIRASALE@professores.estacio.br
	Slide 1
	Slide 2: Introdução
	Slide 3: Árvore AVL
	Slide 4: Fator de Balanceamento
	Slide 5: Fator de Balanceamento
	Slide 6: Fator de Balanceamento
	Slide 7: Fator de Balanceamento
	Slide 8: Fator de Balanceamento
	Slide 9: Rotações
	Slide 10: Rotações
	Slide 11: Rotações
	Slide 12: Rotação LL
	Slide 13: Rotação LL
	Slide 14: Rotação LL
	Slide 15: Rotação LL
	Slide 16: Rotação LL
	Slide 17: Rotação LL
	Slide 18: Rotação RR
	Slide 19: Rotação RR
	Slide 20: Rotação RR
	Slide 21: Rotação RR
	Slide 22: Rotação RR
	Slide 23: Rotação RR
	Slide 24: Rotação LR(a)
	Slide 25: Rotação LR(b)
	Slide 26: Rotação LR(c)
	Slide 27: Rotação LR
	Slide 28: Rotação LR
	Slide 29: Rotação LR
	Slide 30: Rotação LR
	Slide 31: Rotação LR
	Slide 32: Rotação LR
	Slide 33: Rotação LR
	Slide 34: Rotação LR
	Slide 35: Rotação RL(a)
	Slide 36: Rotação RL(b)
	Slide 37: Rotação RL(c)
	Slide 38: Inserções
	Slide 39: Inserções
	Slide 40: Inserções
	Slide 41: Inserções
	Slide 42: Inserções
	Slide 43: Inserções
	Slide 44: Inserções
	Slide 45: Inserções
	Slide 46: Inserções
	Slide 47: Inserções
	Slide 48: Inserções
	Slide 49: Inserções
	Slide 50: Inserções
	Slide 51: Inserções
	Slide 52: Remoção
	Slide 53: Remoção
	Slide 54: Remoção
	Slide 55: Remoção
	Slide 56: Remoção
	Slide 57: Remoção
	Slide 58: Remoção
	Slide 59: Remoção
	Slide 60: Remoção
	Slide 61: Remoção
	Slide 62: Remoção
	Slide 63: Remoção
	Slide 64: Remoção
	Slide 65: Remoção
	Slide 66: Remoção
	Slide 67: Remoção
	Slide 68: Atividade Verificadora de Aprendizado 5 
	Slide 69