12_Arvore Balanceada AVL

Prévia do material em texto

1
Árvore Balanceada AVL
1
Estrutura de Dados e 
Algoritmos
Prof. Cláudio Campelo, PhD
Departamento de Sistemas & Computação / UFCG
Árvore Binária
2
� Qual o tempo das operações de inserção e busca
em uma BST?
� O que acontece quando uma BST possui uma
topologia que “pesa” muito para um dos lados?
� Seria possível uma árvore se reorganizar
dinamicamente para garantir operações em tempo 
O(log n)?
8
7
6
2
1
8
7
6
2
1
2
Árvore Binária Balanceada (AVL)
3
� Origem:
� Adelson-Velskii, G.; E. M. Landis (1962). 
� "An algorithm for the organization of information". 
Proceedings of the USSR Academy of Sciences 146: 
263–266. (Russian) English translation by Myron J. 
Ricci in Soviet Math. Doklady, 3:1259–1263, 1962. 
� AVL (Adelson-Velskii e Landis)
Árvore Binária Balanceada (AVL)
4
� É uma árvore binária de busca (BST) cujo 
objetivo é remover o problema do pior caso onde 
a altura é O(n).
� Uso de invariante:
� Balanceamento: a altura das sub-árvores diferem no 
máximo em 1. 
3
Exemplo
5
Altura 
(considerando as 
folhas)
Exercício 
6
� Quais destas árvores são AVL?
42
8815
946 63
7157
27
20
42
8815
63
7157
27
20
42
8828
946 6327
4
Exercício 
7
� Quais destas árvores são AVL?
42
8815
946 63
7157
27
20
Árvore AVL
42
8815
63
7157
27
20
Não é árvore AVL!
42
8828
946 6327
Não é árvore AVL!
Árvore Binária Balanceada (AVL)
8
� Buscas, inserções e remoções possuem 
complexidade O(log n).
� Inserções e remoções podem requerer o 
rebalanceamento da árvore.
� Operações de rotação reajustam a árvore.
5
Árvore Binária Balanceada (AVL)
9
� O fator de balanceamento (FB) é dado pela 
diferença: 
FB = height(left) - height(right)
� O FB indica para onde a árvore pesa: 
� -1: a árvore pesa para a direita
� 0: não pesa pra nenhum lado
� 1 a árvore pesa para a esquerda
Exemplo
10
Fator de 
balanceamento
6
Árvore Binária Balanceada (AVL)
11
� A busca realizada em uma árvore AVL é igual a 
realizada em uma BST
Altura: Teorema
12
� A altura de uma árvore AVL com N nós internos 
sempre está entre:
log N ≤ h < 1.44.log(N + 2) – 1.328
7
Árvore Binária Balanceada (AVL)
13
� Inserções
� As inserções funcionam exatamente como na BST
� Entretanto…
� Inserções podem desbalancear a árvore!
� Como resolver?
� Usando operações de rotação
� O fator de balanceamento diz quando aplicar rotação
Árvore Binária Balanceada (AVL)
14
� Rotação
� Operação sobre árvores binarias que muda as estruturas 
sem interferir na ordem dos elementos. 
� Move um nó pra cima e um nó para baixo
� Quais os efeitos imediatos de uma rotação?
8
Árvore Binária Balanceada (AVL)
15
� Rotação
� Operação sobre árvores binárias que muda as estruturas 
sem interferir na ordem dos elementos. 
� Move um nó pra cima e um nó para baixo
� Quais os efeitos imediatos de uma rotação?
� A altura de uma sub-árvore diminui enquanto a altura da 
outra aumenta.
� Garante uma árvore próxima do preenchimento completo 
(melhor caso).
� Operações de inserção e busca em O(log n).
Árvore Binária Balanceada (AVL)
16
� Rotação
� Simples: ocorre quando um nó está desbalanceado e 
seu filho estiver inclinado no mesmo sentido (ou sem 
inclinação).
� Dupla: ocorre quando um nó estiver desbalanceado e 
seu filho estiver inclinado no sentido inverso. 
9
Rotação simples
17
Rotação simples
18
10
Rotação
19
� Generalização da rotação:
� Root – nó pai das subárvores a serem rotacionadas
� Pivot – o nó que será o novo pai
� RS – filho do mesmo lado da rotação (rotation side) 
� OS – filho do lado oposto da rotação (opposite side)
� Pseudo-código:
Pivot = Root.OS 
Root.OS = Pivot.RS 
Pivot.RS = Root 
Root = Pivot 
Rotação
20
� Generalização da rotação:
� Root – nó pai das subárvores a serem rotacionadas
� Pivot – o nó que será o novo pai
� RS – filho do mesmo lado da rotação (rotation side) 
� OS – filho do lado oposto da rotação (opposite side)
� Pseudo-código:
Pivot = Root.OS 
Root.OS = Pivot.RS 
Pivot.RS = Root 
Root = Pivot 
root
Q
P C
A B
11
Rotação
21
� Generalização da rotação:
� Root – nó pai das subárvores a serem rotacionadas
� Pivot – o nó que será o novo pai
� RS – filho do mesmo lado da rotação (rotation side) 
� OS – filho do lado oposto da rotação (opposite side)
� Pseudo-código:
Pivot = Root.OS
Root.OS = Pivot.RS 
Pivot.RS = Root 
Root = Pivot 
root
Q
P C
A B
Rotação
22
� Generalização da rotação:
� Root – nó pai das subárvores a serem rotacionadas
� Pivot – o nó que será o novo pai
� RS – filho do mesmo lado da rotação (rotation side) 
� OS – filho do lado oposto da rotação (opposite side)
� Pseudo-código:
root
pivot
Q
P C
A B
Pivot = Root.OS 
Root.OS = Pivot.RS 
Pivot.RS = Root 
Root = Pivot 
12
Rotação
23
� Generalização da rotação:
� Root – nó pai das subárvores a serem rotacionadas
� Pivot – o nó que será o novo pai
� RS – filho do mesmo lado da rotação (rotation side) 
� OS – filho do lado oposto da rotação (opposite side)
� Pseudo-código:
root
pivot
Q
P C
A B
Pivot = Root.OS 
Root.OS = Pivot.RS 
Pivot.RS = Root 
Root = Pivot 
Rotação
24
� Generalização da rotação:
� Root – nó pai das subárvores a serem rotacionadas
� Pivot – o nó que será o novo pai
� RS – filho do mesmo lado da rotação (rotation side) 
� OS – filho do lado oposto da rotação (opposite side)
� Pseudo-código:
root
pivot
Q
P C
A B
Pivot = Root.OS 
Root.OS = Pivot.RS
Pivot.RS = Root 
Root = Pivot 
13
Rotação
25
� Generalização da rotação:
� Root – nó pai das subárvores a serem rotacionadas
� Pivot – o nó que será o novo pai
� RS – filho do mesmo lado da rotação (rotation side) 
� OS – filho do lado oposto da rotação (opposite side)
� Pseudo-código:
root
pivot
Q
P C
A B
Pivot = Root.OS 
Root.OS = Pivot.RS 
Pivot.RS = Root 
Root = Pivot 
Rotação
26
� Generalização da rotação:
� Root – nó pai das subárvores a serem rotacionadas
� Pivot – o nó que será o novo pai
� RS – filho do mesmo lado da rotação (rotation side) 
� OS – filho do lado oposto da rotação (opposite side)
� Pseudo-código:
root
pivot
Q
P C
A B
Pivot = Root.OS 
Root.OS = Pivot.RS 
Pivot.RS = Root 
Root = Pivot 
14
Rotação
27
� Generalização da rotação:
� Root – nó pai das subárvores a serem rotacionadas
� Pivot – o nó que será o novo pai
� RS – filho do mesmo lado da rotação (rotation side) 
� OS – filho do lado oposto da rotação (opposite side)
� Pseudo-código:
root
pivot
Q
P C
A B
Pivot = Root.OS 
Root.OS = Pivot.RS 
Pivot.RS = Root 
Root = Pivot 
Rotação
28
� Generalização da rotação:
� Root – nó pai das subárvores a serem rotacionadas
� Pivot – o nó que será o novo pai
� RS – filho do mesmo lado da rotação (rotation side) 
� OS – filho do lado oposto da rotação (opposite side)
� Pseudo-código:
root
Q
P
C
A
B
Pivot = Root.OS 
Root.OS = Pivot.RS 
Pivot.RS = Root 
Root = Pivot 
pivot
15
Rotação
29
� Generalização da rotação:
� Root – nó pai das subárvores a serem rotacionadas
� Pivot – o nó que será o novo pai
� RS – filho do mesmo lado da rotação (rotation side) 
� OS – filho do lado oposto da rotação (opposite side)
� Pseudo-código:
root
Q
P
C
A
B
Pivot = Root.OS 
Root.OS = Pivot.RS 
Pivot.RS = Root 
Root = Pivot 
pivot
Qual a ordem de complexidade da rotação?
Rotação: análise de casos
30
� Representação
� Casos: Left-Left e Right-Right
� Resolvidos com rotação SIMPLES no sentido contrário
da inclinação
� Left-Left:raiz pesa pra esquerda e filho esquerdo pesa 
pra esquerda ou está balanceado (FB=0): rotação pra 
direita na raiz
� Right-Right: raiz pesa pra direita e filho pesa pra direita 
ou está balanceado (FB=0): rotação pra esquerda na raiz
1
0
2 -2
-1
0
0
0
2
0
-2
0
00
LL RR
16
Rotação: analise de casos
31
� Representação
� Casos: Left-Right e Right-Left
� Resolvidos rotação DUPLA seguindo o mesmo sentido do 
caso aplicando primeiro no filho e depois no pai
� Left-Right: raiz pesa pra esquerda e filho esquerdo pesa
pra direita: rotação esquerda no filho e direita no pai
� Right-Left: raiz pesa pra direita e filho direito pesa pra 
esquerda: rotação direita no filho e esquerda no pai
-1
0
2 -2
1
0
LR RL
Rotações Duplas
32
17
Operações sobre árvore AVL
33
� Inserções:
� Insere normalmente e depois reajusta a árvore (se 
necessário) para deixá-la balanceada novamente
� Remoções:
� Remove o nó normalmente como na BST depois reajusta a 
árvore (se necessário) para deixá-la balanceada novamente
� Fazem uso de rotações convenientes em nós 
desbalanceados: simples (LL,RR) ou dupla (RL, LR)
� Abordagem recursiva é mais simples para ambas as 
operações
Árvore AVL
34
� Questões de implementação
� Como seria implementada uma árvore AVL em Java?
� É possível usar herança na implementação de AVL?
18
Árvore AVL
35
� Questões de implementação
� Como seria implementada uma árvore AVL em Java?
� É possível usar herança na implementação de AVL?
public interface AVLTree<T extends Comparable<T>> 
extends BST<T>{
}
Árvore AVL
36
� Que métodos precisam ser redefinidos?
public interface AVLTreeImpl<T extends Comparable<T>> 
extends BSTImpl<T>{
public boolean isEmpty();
public int height();
public boolean search(T element);
public void insert(T element);
public T maximum();
public T minimum();
public void remove(T element);
public T[] preOrder();
public T[] order();
public T[] postOrder();
public int size();
}
19
Árvore AVL
37
� Que métodos precisam ser redefinidos?
public interface AVLTreeImpl<T extends Comparable<T>> 
extends BSTImpl<T>{
public boolean isEmpty();
public int height();
public boolean search(T element);
public void insert(T element);
public T maximum();
public T minimum();
public void remove(T element);
public T[] preOrder();
public T[] order();
public T[] postOrder();
public int size();
}
Árvore AVL
38
� Como seria a redefinição da inserção?
Insert (T element){
Insert-recursive(root,element);
}
Insert-recursive(BSTNode node, T element){
...
}
20
Árvore AVL
39
� Como seria a redefinição da inserção?
Insert-recursive(BSTNode node, T element){
if(node=NIL){
node.data = element
node.left = NIL
node.right = NIL
}else{
if(element < node.data){
Insert-recursive (node.left, element)
}else if (element > node.data){
Insert-recursive (node.right, element)
}
rebalance(node)
}
}
Árvore AVL
40
� Como seria a redefinição da remoção?
remove (T element){
BSTNode<T> found = search(element); 
remove-recursive(found);
}
Remove-recursive(BSTNode node){
...
}
21
Árvore AVL
41
� Como seria a redefinição da remoção?
Remove-recursive(BSTNode node) {
if(node != NIL){
if(node is leaf){
node = NIL
rebalanceUp(node)
}else if (node has one child){
if node != root
if(node is left child){
if(node.left != NIL)
node.left is left child of node.parent
else
node.right is left child of node.parent
else //node is right child
if(node.left != NIL)
node.left is right child of parent
else
node.right is right child of parent 
else
root is a not NIL child
rebalanceUp(node)
}else{
BSTNode sucessor = sucessor(node);
node.data = sucessor.data
Remove-recursive (sucessor);
}
}
}
Árvore AVL
42
� Como seria a redefinição da remoção?
Remove-recursive(BSTNode node) {
if(node != NIL){
if(node is leaf){
node = NIL
rebalanceUp(node)
}else if (node has one child){
if node != root 
if(node is left child){
if(node.left != NIL)
node.left is left child of node.parent
else
node.right is left child of node.parent
else //node is right child
if(node.left != NIL)
node.left is right child of parent
else
node.right is right child of parent 
else
root = not NIL child
rebalanceUp(node)
}else{
BSTNode sucessor = sucessor(node);
node.data = sucessor.data;
Remove-recursive (sucessor);
}
}
}
rebalanceUp(BSTNode<T> node) {
BSTNode parent = node.parent
while (parent != null) {
rebalance(parent);
parent = parent.parent;
}
}
22
Árvore AVL
43
� Que métodos auxilares a AVL precisa ter?
public interface AVLTreeImpl<T extends Comparable<T>> 
extends BSTImpl<T>{
public void insert(T element);
public void remove(T element);
}
Árvore AVL
44
� Que métodos auxilares a AVL precisa ter?
public interface AVLTreeImpl<T extends Comparable<T>> 
extends BSTImpl<T>{
public void insert(T element);
public void remove(T element);
private int calculateBalance(BSTNode<T> node)
private void rebalance(BSTNode<T> node)
private void rebalanceUp(BSTNode<T> node)
private void leftRotation(BSTNode<T> node)
private void rightRotation(BSTNode<T> node)
}
23
Árvore AVL
45
� Como seria o método calcular o balance de uma
árvore AVL?
int calculateBalance(BSTNode<T> node) {
if ( node != NIL )
return height (node.left) – height (node.right)
}
Árvore AVL
46
� Como seria o rebalanceamento de uma árvore?
void rebalance(BSTNode<K,V> node) {
balance = calculateBalance(node)
IF ( |balance| > 1 )
determina o caso de balanceamento
aplica a rotação adequada (LL,RR,LR,RL)
}
24
Árvore AVL
47
� Como seriam os métodos de rotação a esquerda e a 
direita?
� É só implementar o algoritmo genérico
� Uma implementação é o espelho (inverso) da outra
Pivot = Root.OS 
Root.OS = Pivot.RS 
Pivot.RS = Root 
Root = Pivot 
Referências
48
� Seção 7.4
� 1a edição