Árvores AVL: Balanceamento Dinâmico

Prévia do material em texto

SUMÁRIO 
 
 
 O que são árvores? 
 Árvores Balanceadas 
 Balanceamento estático e dinâmico! 
 Árvores AVL 
 Fator de Balanceamento (Fatbal) 
 Rotação Simples(Esquerda e direita) 
 Rotação Dupla (Esquerda e Direita) 
 Exemplos 
 Referências. 
 
 
O que são Árvores? 
 
 São estruturas de dados não lineares que 
caracterizam uma relação entre dados; 
 
 A relação existente entre os dados é uma relação de 
hierarquia onde um conjunto de nodos é 
hierarquicamente subordinado a outro. 
Árvores 
 Uma arvore é considerada balanceada quando suas sub-
arvores à esquerda e à direita possuem a mesma altura. 
 A árvore não balanceada é definida como degenerada 
Balanceadas 
Árvore Binária Balanceada 
Árvore Binária Degenerada 
Árvores 
 Balanceamento Estático: 
 - Este balanceamento consiste em, depois de um certo 
tempo de uso da árvore, destruir sua estrutura, guardando 
suas informações em uma lista ordenada e reconstruí-la de 
forma balanceada. 
 
 Balanceamento Dinâmico: 
 - Tem por objetivo reajustar os nós de uma árvore sempre 
que uma inserção ou remoção provocar desbalanceamento. 
 - Um exemplo de Balanceamento dinâmico são as árvores 
AVL. 
Balanceadas 
Árvores AVL 
 O termo AVL vem de seus fundadores Adel´son, Vel´skii e 
Landis (1962). Foi a primeira estrutura de dados a oferecer 
operações de inserção, remoção e busca em tempo 
logaritmo ou seja é um algoritmo muito rápido. 
 
- Em uma árvore degenerada de 10.000 nós, são necessárias 5.000 comparações para efetuar 
uma busca, já numa árvore AVL, com o mesmo número de nós, essa média baixa para 14 
comparações. – 
 
 A árvore AVL é uma árvore binária de busca e sua estrutura 
foi construída de forma que a altura da sub-árvore direita é 
diferente da altura da sub-árvore esquerda de no máximo 1. 
 
Árvores AVL 
Fator de Balanceamento 
 Sendo assim, para cada nó define-se um fator de 
balanceamento(fatbal), que deve ser -1,0 ou 1. 
Fatbal = altura (sub-arvore direita) – altura (sub-árvore esquerda) 
-> Fatbal = -1, quando a sub-árvore da esquerda é um nível mais alto 
que a direita. 
-> Fatbal = 0, quando as duas sub-árvores tem a mesma altura. 
-> Fatbal = 1, quando a sub-árvore da direita é um nível mais alto que 
a esquerda. 
 
 
Balanceamento em AVL 
 Inserimos um novo nodo na árvore. 
 
 Esta inserção pode ou não alterar as propriedades de 
balanceamento. 
 
 Caso a inserção desse novo nodo não viole alguma 
propriedade de balanceamento, podemos continuar 
inserindo novos nodos. 
 
 Se a inserção afetar as propriedades de balanceamento 
devemos restaurar o balanço da árvore. Esta restauração é 
efetuada através de ROTAÇÕES na árvore. 
I) Rotação simples à esquerda 
Rotação: 
II) Rotação simples à direita 
Rotação: 
III) Rotação dupla à esquerda 
Rotação: 
 
(rotação simples à direita + rotação simples à esquerda) 
IV) Rotação dupla à direita 
 
Rotação: 
 
(rotação simples à esquerda + rotação simples à direita) 
Dicas: 
 
a) Para identificar quando uma rotação é simples 
ou dupla deve-se observar os sinais do Fb: 
 • Sinal for igual, a rotação é simples 
 • Sinal for diferente a rotação é dupla 
 
b) Se Fb for positivo (+) a rotação para à esquerda 
 
c) Se Fb for negativa (-) a rotação para à direita 
Rotação: 
Caso I: Rotação Simples 
 Suponha que inserimos os números 50, 40 e 30 em uma 
árvore. Obteremos então: 
 
 
 
• A inserção novamente produziu um desbalanceamento. 
 
• Neste caso, como os sinais dos FB são os mesmos, significa que precisamos fazer apenas 
uma ROTAÇÃO SIMPLES à direita no nodo com FB -2. 
 
• No caso simétrico (nodo com FB 2) faríamos uma rotação simples à esquerda. 
 
Caso I: Rotação Simples 
• Após a rotação simples teremos: 
 
• A árvore está balanceada dentro das propriedades de AVL. 
 
Exemplo: 
 Considerando a árvore abaixo: 
• A árvore está balanceada, como podemos observar pelos Fb de cada nodo. 
• São dois os possíveis casos de desbalancemento 
Caso II: Rotação Dupla 
 Ao inserir o número 5 na árvore teremos a seguinte 
árvore: 
 
• O nodo 8 fica com o FB -2 e tem um filho com FB +1. Neste caso para manter o balanceamento 
devemos aplicar duas rotações, também denominada ROTAÇÃO DUPLA. 
• Primeiro rotaciona-se o nodo com FB 1 para a esquerda. 
 
Caso II: Rotação Dupla 
• Logo rotaciona-se o nodo que possuía FB -2 na direção 
oposta, nesse caso a direita. 
 
 
Caso II: Rotação Dupla 
• Os FB dos nodos voltaram a ficar dentro do esperado das árvores AVL. 
 
• O caso simétrico ao explicado acima acontece com os sinais de FB 
 trocados, ou seja, um nodo com FB +2 com um filho com FB -1. Também 
 utilizariamos uma rotação dupla, mas nos sentidos contrários, ou seja, o 
 nodo com FB -1 seria rotacionado para a direita e o nodo com FB +2 seria 
 rotacionado para a esquerda. 
 
 
 A descrição do algoritmo em pseudo-código para a 
construção de uma árvore AVL seria: 
 
 
 Inserir o novo nodo normalmente 
 Iniciando com o nodo pai do nodo recém-inserido, testar se a propriedade 
AVL é violada no novo nodo. Temos aqui 2 possibilidades: 
 A condição AVL foi violada 
 Execute as operações de rotação conforme for o caso (Caso I ou Caso II). 
 Volte ao passo de Inserção. 
 A condição AVL não foi violada. 
 Se o nodo recém-testado não tem pai, ou seja, é o nodo raiz da árvore, volte 
para inserir novo nodo. 
 
Conclusões 
 Balanceamento de árvores busca minimizar o número 
médio de comparações necessárias para localizar 
qualquer dado. 
 Operações de inserção e remoção de nós tendem a tornar 
as árvores desbalanceadas. 
 Há um custo extra de processamento. 
 
 Compensado quando os dados armazenados precisam ser 
recuperados muitas vezes. 
21 
AVL Tree Applet 
 http://www.site.uottawa.ca/~stan/csi2514/applets/avl/BT.h
tml 
22