Aula 5_Arvore AVL

Prévia do material em texto

ÁRVORES AVL
Lívia N. Andrade
Árvores Balanceadas
� Para que uma árvore seja, de fato, um mecanismo
eficiente, é preciso que os seus elementos estejam
distribuídos de forma relativamente homogênea pela
estrutura (sub-árvores);
� Como as operações de inserção e remoção são 
aleatórias, é preciso ter um operador capaz de 
manter os elementos distribuídos de forma 
homogênea entre as sub-árvores;
� Esse é o operador de balanceamento.
Árvores Binárias Balanceadas
O balanceamento de uma árvore pode ser feito 
segundo duas estratégias:
Global – envolvendo toda a árvore
Exemplo: Algoritmo DSW
Local – envolvendo apenas uma parte da árvore
Exemplo: árvores AVL ou árvores Rubronegras
Balanceamento Global
� No balanceamento global a árvore balanceada 
pode ser construída a partir de uma estrutura 
externa;
� Nesse caso o algoritmo é relativamente simples, 
bastando criar uma lista ordenada com o conteúdo 
da árvore (antes ou mesmo depois da existência da 
árvore);
� Dessa lista constrói-se a árvore já balanceada.
Balanceamento Local
� O balanceamento local faz uso de algoritmos que 
trabalham apenas em parte da árvore, a cada 
inserção ou remoção;
� Algoritmos desse tipo podem ser representados 
pelas árvores AVL ou árvores Rubronegras.
Árvores AVL
� Recebem esse nome em homenagem aos seus criadores, 
os matemáticos russos Adelson-Velskii e Landis, 1962.
� Uma árvore AVL é uma árvore binária de pesquisa onde a 
diferença em altura entre as subárvore esquerda e direita é 
no máximo 1 (positivo ou negativo). 
� Quando a diferença chega a 2 ou –2, deve ser refeito o 
balanceamento através de rotações.
� Chamamos essa diferença de “fator de balanceamento”.
Árvores AVL
� Assim, para cada nodo podemos definir um fator de 
balanceamento (FB), que vem a ser um número inteiro 
igual a:
FB(nodo p) = altura(subárvore direita p) - altura(subárvore
esquerda p)
O FB de um nó folha será sempre 0.
Árvores AVL
6
FB(nodo p) = altura(subárvore direita p) - altura(subárvore
esquerda p)
alt_d = 2
alt_e = 3
FB = 2 – 3 = -1
6
2 8
1 4
3
12
Árvores AVL
6
FB(nodo p) = altura(subárvore direita p) - altura(subárvore
esquerda p)
FB = -1 alt_d = 1
alt_e = 06
2 8
1 4
3
12
alt_e = 0
FB = 1 – 0 = 1
Árvores AVL
6
FB(nodo p) = altura(subárvore direita p) - altura(subárvore
esquerda p)
FB = -1
6
2 8
1 4
3
12
FB = 1
alt_d = 0
alt_e = 0
FB = 0 – 0 = 0
Árvores AVL
6
FB(nodo p) = altura(subárvore direita p) - altura(subárvore
esquerda p)
FB = -1
alt_d = 2
6
2 8
1 4
3
12
FB = 1
FB = 0
alt_d = 2
alt_e = 1
FB = 2 – 1 = 1
Árvores AVL
6
FB(nodo p) = altura(subárvore direita p) - altura(subárvore
esquerda p)
FB = -1
6
2 8
1 4
3
12
FB = 1
FB = 0
FB = 1
FB = 0
FB = 0
FB = -1
Árvores AVL 
� Os números nos nós representam o FB para cada 
nó.
� Para uma árvore ser AVL os fatores de balanço 
devem ser necessariamente -1, 0, ou 1.devem ser necessariamente -1, 0, ou 1.
Exemplos de Árvores AVL 
11
1
0
0
0
-1
-1
0
0
-1
0 0
0 0
-1
Exemplos de Árvores não-AVL
0-2
0
+2
-1
-2
+1
0
0
-1
Balanceamento de Árvores AVL 
� Inicialmente inserimos um novo nó na árvore.
� A inserção deste novo nó pode ou não violar a propriedade 
de balanceamento.
� Caso a inserção do novo nó não viole a propriedade de 
balanceamento podemos então continuar inserindo novos nós.
� Caso contrário precisamos nos preocupar em restaurar o 
balanço da árvore. A restauração deste balanço é efetuada 
através do que denominamos ROTAÇÕES na árvore.
Exemplos de 
Balanceamento de Árvores AVL 
� Vamos considerar a seguinte árvore (os números ao lado dos nodos 
são o FB de cada nó):
8
-1
� A árvore acima está balanceada, como podemos observar pelos 
FB de cada nodo.
8
4
2 6
10
0
0
0 0
Exemplos de 
Balanceamento de Árvores AVL 
� Existem 2 casos possíveis de desbalanceamento da 
árvore:
Tipo 1: é necessário fazer uma rotação dupla para manter a � Tipo 1: é necessário fazer uma rotação dupla para manter a 
árvore balanceada
� Tipo 2: é necessário fazer uma rotação simples para manter 
a árvore balanceada
Dicas
� Para identificarmos quando uma rotação é simples ou dupla, 
observamos os sinais de FB:
� se o sinal for igual, a rotação é simples.� se o sinal for igual, a rotação é simples.
� Se FB+ rotação para esquerda
� Se FB- rotação para direita
� se o sinal for diferente a rotação é dupla.
� Mais detalhes na tabela de “Descrição de Rotações”
Exemplos de 
Balanceamento de Árvores AVL 
� Tipo 1: Ao inserir o número 5 na árvore. 
8
-1
8
-2
8
4
2 6
10
0
0
0 0
8
4
2 6
10
0
1
0 -1
5
0
Exemplos de 
Balanceamento de Árvores AVL 
� Tipo 1: Ao inserir o número 5 na árvore. 
8
-1
8
-2
8
4
2 6
10
0
0
0 0
8
4
2 6
10
0
1
0 -1
5
0
Solução para manter o balanceamento:
Como os sinais dos FB são diferentes, efetuar duas rotações, também 
denominada ROTAÇÃO DUPLA.
Exemplos de 
Balanceamento de Árvores AVL 
� Tipo 2: Ao inserir o número 3 na árvore. 
8
-1
8
-2
8
4
2 6
10
0
0
0 0
8
4
2 6
10
0
-1
1 0
3
0
Exemplos de 
Balanceamento de Árvores AVL 
� Tipo 2: Ao inserir o número 3 na árvore. 
8
-1
8
-2
8
4
2 6
10
0
0
0 0
8
4
2 6
10
0
-1
1 0
3
0
Solução para manter o balanceamento:
Como os sinais dos FB são os mesmos, efetuar uma rotação, também 
denominada ROTAÇÃO SIMPLES.
Descrição das rotações
Diferença de altura 
de um nó
Diferença de altura do nó filho 
do nó desbalanceado
Tipo de rotação
2
1 Simples à esquerda
0 Simples à esquerda
Dupla com filho para a 
-1
Dupla com filho para a 
direita e pai para a 
esquerda
-2 1
Dupla com filho para a 
esquerda e pai para a 
direita
0 Simples à direita
-1 Simples à direita
Descrição das rotações
Diferença de altura 
de um nó
Diferença de altura do nó filho 
do nó desbalanceado
Tipo de rotação
2
1 Simples à esquerda
0 Simples à esquerda
Dupla com filho para a 
-1
Dupla com filho para a 
direita e pai para a 
esquerda
-2 1
Dupla com filho para a 
esquerda e pai para a 
direita
0 Simples à direita
-1 Simples à direita
Exemplos de Balanceamento 
Rotação simples à esquerda
6
1
Árvore Balanceada
6
2
Árvore Desbalanceada
+ 126
8
0
6
8
1
12
0
+ 12
Exemplos de Balanceamento 
Rotação simples à esquerda
6
1
Árvore Balanceada
6
2
Árvore Desbalanceada
+ 126
8
0
6
8
1
+ 12
12
0
Nó desbalanceado
Filho do nó 
desbalanceado
Exemplos de Balanceamento 
Rotação simples à esquerda
6
1
Árvore Balanceada
6
2
Árvore Desbalanceada
+ 126
8
0
6
8
1
12
0
+ 12
Rotação simples 
para a esquerda
Exemplos de Balanceamento 
Rotação simples à esquerda
6
1
Árvore Balanceada
6
2
Árvore Desbalanceada
+ 126
8
0
6
8
1
12
0
+ 12
8
0
0
6 12
0
Árvore Balanceada
Descrição das rotações
Diferença de altura 
de um nó
Diferença de altura do nó filho 
do nó desbalanceado
Tipo de rotação
2
1 Simples à esquerda
0 Simples à esquerda
Dupla com filho para a 
-1
Dupla com filho para a 
direita e pai para a 
esquerda
-2 1
Dupla com filho para a 
esquerda e pai para a 
direita
0 Simples à direita
-1 Simples à direita
Exemplos de Balanceamento 
Rotação simples à esquerda
Árvore Balanceada Árvore Desbalanceada
- 6
12
0
1
10
6
0
12
0
2
10
14
0
11
0
14
0
11
0
Exemplos de Balanceamento 
Rotação simples à esquerda
Árvore Balanceada Árvore Desbalanceada
- 6
12
0
1
10
6
0
12
0
2
10
14
0
11
0
14
0
11
0
Nó desbalanceado
Filho do nó 
desbalanceado
Exemplos de Balanceamento 
Rotação simples à esquerda
Árvore Balanceada Árvore Desbalanceada
- 6
12
0
1
10
6
0
12
0
2
10
14
0
11
0
14
0
11
0
Rotação simples 
para a esquerda
Exemplos de Balanceamento 
Rotação simples à esquerda
Árvore Balanceada Árvore Desbalanceada
- 6
12
0
1
10
6
0
12
0
2
10
14
0
11
0
14
0
11
0
Árvore Balanceada
12
-1
14
0
10
1
11
0
Descrição das rotações
Diferença de altura 
de um nó
Diferença de altura do nó filho 
do nó desbalanceado
Tipo de rotação
2
1 Simples à esquerda0 Simples à esquerda
Dupla com filho para a 
-1
Dupla com filho para a 
direita e pai para a 
esquerda
-2 1
Dupla com filho para a 
esquerda e pai para a 
direita
0 Simples à direita
-1 Simples à direita
Rotação dupla com filho para a direita 
e pai para a esquerda
6
8
0
1
Árvore Balanceada
6
8
-1
2
Árvore Desbalanceada
+ 7
12
0
6
8
0
1
Árvore Balanceada
6
8
-1
2
Árvore Desbalanceada
+ 7
Rotação dupla com filho para a direita 
e pai para a esquerda
7
0
Nó desbalanceado
Filho do nó 
desbalanceado
6
8
0
1
Árvore Balanceada
6
8
-1
2
Árvore Desbalanceada
+ 7
Rotação dupla com filho para a direita 
e pai para a esquerda
7
0
Rotação para a 
direita no filho do 
nó desbalanceado
6
8
0
1
Árvore Balanceada Árvore Desbalanceada
6
8
-1
2
+ 7
Rotação dupla com filho para a direita 
e pai para a esquerda
7
0
6
7
1
2
8
0
Árvore Desbalanceada
6
8
0
1
Árvore Balanceada Árvore Desbalanceada
6
8
-1
2
+ 7
Rotação dupla com filho para a direita 
e pai para a esquerda
7
0
Rotação para a 
esquerda no nó 
desbalanceado
6
7
1
2
8
0
Árvore Desbalanceada
6
8
0
1
Árvore Balanceada Árvore Desbalanceada
6
8
-1
2
+ 7
Rotação dupla com filho para a direita 
e pai para a esquerda
7
0
6
7
0
0 80
Árvore Balanceada
6
7
1
2
8
0
Árvore Desbalanceada
Descrição das rotações
Diferença de altura 
de um nó
Diferença de altura do nó filho 
do nó desbalanceado
Tipo de rotação
2
1 Simples à esquerda
0 Simples à esquerda
Dupla com filho para a 
-1
Dupla com filho para a 
direita e pai para a 
esquerda
-2 1
Dupla com filho para a 
esquerda e pai para a 
direita
0 Simples à direita
-1 Simples à direita
Rotação dupla com filho para a 
esquerda e pai para a direita
6
3
0
1
Árvore Balanceada Árvore Desbalanceada
+ 5 6
3
1
-2
5
0
Rotação dupla com filho para a 
esquerda e pai para a direita
6
3
0
1
Árvore Balanceada Árvore Desbalanceada
+ 5 6
3
1
-2
5
0
Nó desbalanceadoFilho do nó 
desbalanceado
Rotação dupla com filho para a 
esquerda e pai para a direita
6
3
0
1
Árvore Balanceada Árvore Desbalanceada
+ 5 6
3
1
-2
5
0
Rotação para a 
esquerda no filho do 
nó desbalanceado
Rotação dupla com filho para a 
esquerda e pai para a direita
6
3
0
1
Árvore Balanceada Árvore Desbalanceada
+ 5 6
3
1
-2
5
0
Árvore Desbalanceada
6
5
-1
-2
3
0
6
3
0
1
Árvore Balanceada Árvore Desbalanceada
+ 5 6
3
1
-2
Rotação dupla com filho para a 
esquerda e pai para a direita
5
0
Árvore Desbalanceada
Rotação para a 
direita no nó 
desbalanceado
6
5
-1
-2
3
0
Rotação dupla com filho para a 
esquerda e pai para a direita
6
3
0
1
Árvore Balanceada Árvore Desbalanceada
+ 5 6
3
1
-2
5
0
Árvore Desbalanceada
6
5
-1
-2
3
0
Árvore Balanceada
6
5
0
0
3
0
Descrição das rotações
Diferença de altura 
de um nó
Diferença de altura do nó filho 
do nó desbalanceado
Tipo de rotação
2
1 Simples à esquerda
0 Simples à esquerda
Dupla com filho para a 
-1
Dupla com filho para a 
direita e pai para a 
esquerda
-2 1
Dupla com filho para a 
esquerda e pai para a 
direita
0 Simples à direita
-1 Simples à direita
Exemplos de Balanceamento 
Rotação simples à direita
Árvore Balanceada Árvore Desbalanceada
- 14
14
0
-1
10
6
0
-2
10
6
0
8
0
2
0
8
0
2
0
Exemplos de Balanceamento 
Rotação simples à direita
Árvore Balanceada Árvore Desbalanceada
- 14
14
0
-1
10
6
0
-2
10
6
0
8
0
2
0
8
0
2
0
Nó desbalanceado
Filho do nó 
desbalanceado
Exemplos de Balanceamento 
Rotação simples à direita
Árvore Balanceada Árvore Desbalanceada
- 14
14
0
-1
10
6
0
-2
10
6
0
8
0
2
0
8
0
2
0
Rotação simples 
para a direita
Exemplos de Balanceamento 
Rotação simples à direita
Árvore Balanceada Árvore Desbalanceada
- 14
14
0
-1
10
6
0
-2
10
6
0
8
0
2
0
8
0
2
0
Árvore Balanceada
0
10
-1
8
2
6
0
1
Descrição das rotações
Diferença de altura 
de um nó
Diferença de altura do nó filho 
do nó desbalanceado
Tipo de rotação
2
1 Simples à esquerda
0 Simples à esquerda
Dupla com filho para a 
-1
Dupla com filho para a 
direita e pai para a 
esquerda
-2 1
Dupla com filho para a 
esquerda e pai para a 
direita
0 Simples à direita
-1 Simples à direita
Exemplos de Balanceamento 
Rotação simples à direita
8
6
0
-1
Árvore Balanceada Árvore Desbalanceada
+ 2 8
6
-1
-2
2
0
Exemplos de Balanceamento 
Rotação simples à direita
8
6
0
-1
Árvore Balanceada Árvore Desbalanceada
+ 2 8
6
-1
-2
2
0
Nó desbalanceado
Filho do nó 
desbalanceado
Exemplos de Balanceamento 
Rotação simples à direita
8
6
0
-1
Árvore Balanceada Árvore Desbalanceada
+ 2 8
6
-1
-2
2
0
Rotação simples 
para a direita
Exemplos de Balanceamento 
Rotação simples à direita
8
6
0
-1
Árvore Balanceada Árvore Desbalanceada
+ 2 8
6
-1
-2
2
0
Árvore Balanceada
0
8
6
0
2
0
Pseudo-código do algoritmo para 
construção de uma árvore AVL
1. Insira o novo nó normalmente (da mesma maneira que inserimos 
numa árvore binária de pesquisa);
2. Iniciando com o nó pai do nó recém-inserido, teste se a 
propriedade AVL é violada neste nó (ou seja, teste se o FB deste 
nó é >1 ou < -1). Existe 2 possibilidades:nó é >1 ou < -1). Existe 2 possibilidades:
2.1 A condição AVL foi violada
2.1.1 Execute as operações de rotação conforme for o caso (vide tabela 
de descrições)
2.1.2 Volte ao passo 1
2.2 A condição AVL não foi violada
Se o nó recém-testado não tem pai, ou seja, é o nó raiz da árvore, volte 
para inserir novo nó (Passo 1)
Exemplo
Construir uma árvore AVL com os seguintes dados:
� Inserir inicialmente 10, 20, 30
� Se necessário fazer balanceamento.
� Inserir 25 e 27
� Se necessário fazer balanceamento
Exemplo
A inserção dos 3 primeiros números resulta na seguinte árvore:
Após a inserção do elemento 30 a árvore fica desbalanceada. Para 
balancear a árvore acima, é necessário apenas uma rotação. 
Fazemos uma rotação para a esquerda no nó com FB 2. A árvore 
resultante fica:
Exemplo
� O passo seguinte é inserir os nós 25 e 27. A árvore fica 
desbalanceada apenas após a inserção do nó 27.
� Neste caso, para manter a árvore balanceada, é necessário 
fazer um rotação dupla. 
Exemplo
� O nó 30 tem FB -2 e o seu nó filho tem FB 1. Precisamos 
efetuar uma rotação dupla, ou seja, uma rotação simples à 
esquerda do nó 25, resultando:
Exemplo
� Seguida de uma rotação simples à direita do nó 30, resultando:
e a árvore está balanceada.
Exercício 1
� Considere a inserção dos seguintes valores (nesta ordem) 
em uma árvore AVL: 5,3,8,2,4,7,10,1,6,9,11. Para essas 
inserções nenhuma rotação é necessária. Desenhe a árvore 
AVL resultante e determine o fator de balanceamento de 
cada nó.cada nó.
Exercício 2
Determinado sistema armazena registros por chaves 
numéricas em uma árvore AVL. Nessa árvore são 
inseridos os seguintes valores: 20,10,5,30,25,27 e 28 
nessa ordem. nessa ordem. 
Apresente passo a passo como a árvore vai sendo 
construída. Realize as rotações necessárias e indique 
qual rotação foi realizada em cada caso.
Resolvendo o Exercício 2
1) Inserção das chaves 20 e 10, nessa ordem
� A árvore ficou pendendo para a esquerda
� O fator de balanceamento do nó cuja chave é 20 é -1.
� O fator de uma folha é sempre 0 (zero).� O fator de uma folha é sempre 0 (zero).
2) Continuar as inserções ...
Referências Utilizadas
� Livro:
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: implementações em Java e C/C++. São Paulo: 
Pearson Prentice Hall, 2010.
� Notas de aula da disciplina, disponível no 
Moodle.