Introdução_Arvores_Balanceadas_Estrutura_de_Dados_II_exercicios_resolvidos

Prévia do material em texto

Estrutura de Dados II
Prof. Gilberto Vieira da Silva
Árvores Balanceadas
Objetivos 
• Entender o conceito de balanceamento, e 
sua importância para a eficiência das árvores 
de busca binárias (ABB);
• Entender a lógica do processo de • Entender a lógica do processo de 
balanceamento de uma ABB;
• Desenvolver habilidade para adaptar a 
lógica do balanceamento a novas situações, 
e para a elaboração de algoritmos sobre 
árvores binárias de busca balanceadas.
Objetivos 
Objetivos 
Problemas com ABB
Exercício 1:
a) Dada uma ABB inicialmente vazia, insira 
(desenhe) os seguintes elementos (nessa 
ordem): M, F, S, D, J, P, U.ordem): M, F, S, D, J, P, U.
Exercício 2:
b) Dada uma ABB inicialmente vazia, insira 
(desenhe) os seguintes elementos (nessa 
ordem): A, B, C, D, E, F, G, H, I, J, K, L, M, 
N, O, P, Q, R, S, T, U, V, W, X, Y, Z.
Problemas com ABB
Comparando as respostas dos exercícios 
1 e 2:
Problemas com ABB
Comparando as respostas dos exercícios 
1 e 2:
Problemas com ABB
Porque? Porque? 
Considere uma ABB uniformemente distribuída.
Do nível 0 ao nível 2 cabem 7 elementos, mas 
temos que visitar apenas 3 nós para identificar se 
X está ou não na árvore.
Problemas com ABB
Então, como podemos identificar 
quantos elementos cabem em uma 
árvore binária:
Nr elementos = (2n+1) – 1
Nível Quantos 
Cabem
0 1
1 3
2 7
3 15 Nr elementos = (2 ) – 1
Conforme pode ser observado, para 
identificar se X está em uma árvore 
com 1 milhão de registros é 
necessário visitar apenas 20 nós, 
incluindo a raiz
3 15
4 31
N (2n+1)-1
9 1023
12 8192
15 65.536
19 1 milhão
29 1 bilhão
39 1 trilhão
Problemas com ABB
Então, essa eficiência na busca por um 
elemento ocorre somente quando a árvore está 
corretamente balanceada.
Definição de uma 
ABB Balanceada
Uma árvore de busca binária é dita balanceada Uma árvore de busca binária é dita balanceada 
(ou ABBB, ou ainda árvore AVL) se e somente 
se para cada nó a altura de suas sub-árvores
diferem de, no máximo, 1.
Definição de uma 
ABB Balanceada
Exemplos:
Exercício:
Considere a figura ao lado:
• A inserção da chave 25 causaria 
desbalanceamento?
•A inserção da chave 40 causaria 
desbalanceamento (considere a árvore como 
mostra a figura, sem a chave 25)?
• A inserção da chave 9 causaria 
desbalanceamento (considere a árvore como 
mostra a figura, sem as chaves 25 e 40)?
Exercício:
Continuação:Continuação:
• A inserção da chave 13 causaria 
desbalanceamento (considere a árvore como 
mostra a figura, sem as chaves 9, 25 e 40)?
•A inserção da chave 17 causaria 
desbalanceamento (considere a árvore como 
mostra a figura, sem as chaves 9, 13, 25 e 40)?
• A inserção da chave 21 causaria 
desbalanceamento (considere a árvore como 
mostra a figura, sem as chaves 9, 13, 17, 25 e 40)?
Processo de Processo de 
RebalanceamentoRebalanceamentoRebalanceamentoRebalanceamento
Caso do Algoritmo InsereCaso do Algoritmo Insere
Rebalanceamento
Caso 1: Caso 1: 
Rotação Simples: Esquerda-Esquerda (EE)
Pense:Pense:
Chave inserida causando o 
desbalanceamento da árvore.
He = 2 e Hd = 0
Como a árvore poderia ser 
ajustada, de modo a ficar 
balanceada?
Rebalanceamento
Caso 1: Caso 1: 
Rotação Simples: Esquerda-Esquerda (EE)
Desenhe uma nova ABB, e Desenhe uma nova ABB, e 
balanceadabalanceadabalanceadabalanceada
Rebalanceamento
Caso 2: Caso 2: 
Rotação Simples: Esquerda-Esquerda (EE)
Chave inserida causando o 
desbalanceamento da árvore.
He = 3 e Hd = 1
Rebalanceamento
Caso 2: Caso 2: 
Rotação Simples: 
Esquerda-Esquerda (EE)
Passo 1: Passo 2: Passo 1: 
Reposicionar a raiz 
e as chaves principais
Passo 2: 
Reposicionar as demais chaves da árvore
Cross Over
Rebalanceamento
Caso 3: Caso 3: 
Rotação Simples: Esquerda-Esquerda (EE)
NOTA:
�Para identificar o nó que desbalanceou, 
siga “de baixo para cima”, a partir da chave 
Chave inserida causando o 
desbalanceamento da árvore.
He = 3 e Hd = 1
siga “de baixo para cima”, a partir da chave 
que acabou de ser inserida. Considere a 
primeira chave que achar desbalanceada, 
nesse caminho “de baixo para cima”.
Rebalanceamento
Caso 3: Caso 3: 
Rotação Simples: 
Esquerda-Esquerda (EE)
Passo 1: Passo 2: Passo 1: 
Reposicionar a raiz 
e as chaves principais
Passo 2: 
Reposicionar as demais chaves da árvore
Exercícios
Desenhe a nova árvore EE do Insere:Desenhe a nova árvore EE do Insere:
Desenhe a nova árvore, resultante do rebalanceamento da árvore das 
figuras fornecidas. 
1) Considere que a chave que acabou de ser inserida está indicada em 
vermelho. 
2) A nova árvore deve ser uma árvore binária de busca, e deve ser 
balanceada. 
3) Identifique a chave onde ocorreu o desbalanceamento, identifique as 
3 chaves principais, posicione-as, e então posicione as demais 
chaves.
Exercícios (Continuação)
A) B) C)
D)
Rebalanceamento
Caso 4: Caso 4: 
Rotação Simples: Direita-Direita (DD)
Esta rotação segue a mesma simétrica da EE.Esta rotação segue a mesma simétrica da EE.
Exercícios
Desenhe a nova árvore DD do Insere:Desenhe a nova árvore DD do Insere:
Desenhe a nova árvore, resultante do rebalanceamento da árvore das 
figuras fornecidas. 
1) Considere que a chave que acabou de ser inserida está indicada em 
vermelho. 
2) A nova árvore deve ser uma árvore binária de busca, e deve ser 
balanceada. 
3) Identifique a chave onde ocorreu o desbalanceamento, identifique as 
3 chaves principais, posicione-as, e então posicione as demais 
chaves.
Exercícios (Continuação)
A) B) C)
D)
Rebalanceamento
Caso 5: Caso 5: 
Rotação Dupla: Esquerda-Direita (ED)
Desbalanceada Balanceada
Rebalanceamento
Caso 6: Caso 6: 
Rotação Dupla: Esquerda-Direita (ED)
Passo 1: Passo 2:
Desbalanceada
Árvore Balanceada
Realocação das Chaves
Cross Over
Exercícios
Desenhe a nova árvore ED do Insere:Desenhe a nova árvore ED do Insere:
Desenhe a nova árvore, resultante do rebalanceamento da árvore das 
figuras fornecidas. 
1) Considere que a chave que acabou de ser inserida está indicada em 
vermelho. 
2) A nova árvore deve ser uma árvore binária de busca, e deve ser 
balanceada. 
3) Identifique a chave onde ocorreu o desbalanceamento, identifique as 
3 chaves principais, posicione-as, e então posicione as demais 
chaves.
Exercícios (Continuação)
A) B) C)
D)