UPE – Caruaru – Sistemas de Informação
Disciplina: Estrutura de Dados e Arquivo
Prof.: Paulemir G. Campos
Pesquisas de Dados
(Parte 2)
05/11/2015
EDA - Prof. Paulemir Campos
1
Conteúdo

Árvores AVL





Definição;
Exemplo e contra-exemplo;
Balanceamento;
Exemplo de rotação dupla.
Referências
05/11/2015
EDA - Prof. Paulemir Campos
2
Árvores AVL
05/11/2015
EDA - Prof. Paulemir Campos
3
Árvores AVL: Definição


Árvore criada por Adelson-Velskii e
Landis, daí o nome Árvore AVL;
É uma árvore de pesquisa binária
balanceada cujo módulo da diferença
entre as alturas das sub-árvores
esquerda e direita de cada nó nunca é
maior do que 1.
05/11/2015
EDA - Prof. Paulemir Campos
4
Árvores AVL: Definição


Em outras palavras, o valor do
balanceamento de cada nó de uma
árvore AVL é igual a 1, 0 ou –1.
Caso contrário, a árvore binária não é
AVL, pois estará desbalanceada.
05/11/2015
EDA - Prof. Paulemir Campos
5
Árvores AVL: Exemplo
-1
1
0
0
0
0
1
0
0
0
05/11/2015
-1
0
0
EDA - Prof. Paulemir Campos
0
0
0
0
6
Árvores AVL: Contra-exemplo

Exemplo de Árvore não-AVL
-1
1
0
0
0
0
1
0
0
0
05/11/2015
-2
0
0
EDA - Prof. Paulemir Campos
0
0
0
7
Árvores AVL: Balanceamento

Balanceamento de Árvore Binária por
Rotação Esquerda:
ponteiro tArvore GiraEsquerda (ponteiro tArvore raiz) {
ponteiro tArvore novaRaiz
novaRaiz = raiz->direito
raiz->direito = novaRaiz->esquerdo
novaRaiz->esquerdo = raiz
retorna novaRaiz
}
05/11/2015
EDA - Prof. Paulemir Campos
8
Árvores AVL: Balanceamento
Exemplo de balanceamento por rotação
esquerda.

A
-2
1
B
0
C
-1
0
D
1
F
0
05/11/2015
-1
E
A
B
G
-1
D
0
0
0
C
0
E
0
G
F
EDA - Prof. Paulemir Campos
9
Árvores AVL: Balanceamento

Balanceamento de Árvore Binária por
Rotação Direita:
ponteiro tArvore GiraDireita (ponteiro tArvore raiz) {
ponteiro tArvore novaRaiz
novaRaiz = raiz->esquerdo
raiz->esquerdo = novaRaiz->direito
novaRaiz->direito = raiz
retorna novaRaiz
}
05/11/2015
EDA - Prof. Paulemir Campos
10
Árvores AVL: Balanceamento

Exemplo de balanceamento por rotação
direita.
2
0
D
1
A
-1
B
0
-1
F
05/11/2015
1
E
D
F
0
0
0
C
B
G
1
E
-1
0
EDA - Prof. Paulemir Campos
A
C
0
G
11
Árvores AVL: Balanceamento

Características:


Quando se efetua uma rotação esquerda
ou direita numa árvore de pesquisa binária,
a ordem dos elementos percorrendo-a em
ordem central não se altera.
Isto é, a árvore de pesquisa binária
continua ordenada.
05/11/2015
EDA - Prof. Paulemir Campos
12
Árvores AVL: Balanceamento

Características:


Árvore desbalanceada com valor negativo
pode ser balanceada com rotação
esquerda;
Árvore desbalanceada com valor positivo
pode ser balanceada com rotação direita.
05/11/2015
EDA - Prof. Paulemir Campos
13
Árvores AVL: Balanceamento

Descrição das rotações nos seguintes casos:
Diferença de altura
do nó desbalanceado
(hSE-hSD)
-2
2
05/11/2015
Diferença de altura do
nó filho do nó
desbalanceado (hSE-hSD)
Tipo de Rotação
-1
Simples à esquerda
0
Simples à esquerda
1
Dupla com filho à direita e
pai à esquerda
-1
Dupla com filho à
esquerda e pai à direita
0
Simples à direita
1
Simples à direita
EDA - Prof. Paulemir Campos
14
Árvores AVL: Balanceamento
Exemplo de Rotação Dupla

Dada a árvore de
pesquisa binária ao
lado, pede-se para
balanceá-la aplicando
operações de rotação
à esquerda e/ou à
direita conforme
necessário.
05/11/2015
20
15
12
25
19
18
EDA - Prof. Paulemir Campos
15
Árvores AVL: Balanceamento
Exemplo de Rotação Dupla

Primeiro aplica-se uma rotação à esquerda
no nó 15 da árvore desbalanceada inicial.
2
-1
0
15
12
2
0
1
0
20
25
19
2
19
18
05/11/2015
0
0
12
20
0
25
15
0
EDA - Prof. Paulemir Campos
18
16
Árvores AVL: Balanceamento
Exemplo de Rotação Dupla

Depois, basta aplicar uma rotação à direita
no nó 20 da árvore obtida no passo anterior.
2
19
2
0
0
12
15
20
0
0
25
0
0
0
15
12
19
-1
0
18
20
25
0
18
05/11/2015
EDA - Prof. Paulemir Campos
17
Referências
05/11/2015
EDA - Prof. Paulemir Campos
18
Referências

ASCENCIO, A. F. G; ARAÚJO, G. S.
Estruturas de Dados: algoritmos,
análise da complexidade e
implementações em JAVA e
C/C++. São Paulo: Pearson Prentice
Hall, 2010.
05/11/2015
EDA - Prof. Paulemir Campos
19
Referências

SZWARCFITER, J. L.; MARKENZON, L.
Estruturas de Dados e seus
Algoritmos. 2. ed. Rio de Janeiro:
LTC, 1994.
05/11/2015
EDA - Prof. Paulemir Campos
20