Arvores AVL

ÁRVORES AVL
Estrutura de Dados

Árvores Balanceadas
Uma árvore é dita balanceada quando as suas subárvores à esquerda e à direita possuem a mesma altura.
Todos os links vazios estão no mesmo nível, ou seja, que a árvore está completa.
A árvore que não está balanceada, define-se como degenerada

Árvores Balanceadas
Balanceamento Estático
- O balanceamento estático de uma árvore binária consiste em construir uma nova versão, reorganizando-a.

Balanceamento Dinâmico: AVL
Árvore AVL em homenagem aos matemáticos russos
(Adelson-Velskii e Landism -1962)
Uma árvore AVL é uma árvore binária de pesquisa onde a diferença em altura entre as subárvores esquerda e direita é no máximo 1 (positivo ou negativo).
A essa diferença chamamos de “fator de balanceamento” de n (FatBal (n)).
Essa informação deverá constar em cada nó de uma árvore balanceada

Á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 Fator de uma folha é sempre Zero (0)

Árvores Balanceadas
Exemplos de árvores AVL e árvores não-AVL.
Os números nos nodos representam o FB para cada nodo.
Para uma árvore ser AVL os fatores de balanço devem ser necessariamente -1, 0, ou 1.
Árvores AVL

Árvores Não AVL

Balanceamento de AVL
Inicialmente inserimos um novo nodo na árvore.
A inserção deste novo nodo pode ou não violar a propriedade de balanceamento. Caso a inserção do novo nodo não viole a propriedade de balanceamento podemos então continuar inserindo novos nodos.
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.

Árvores AVL
Se quisermos manter a árvore balanceada a cada inserção, devemos ter um algoritmo que ajuste os fatores de balanceamento

O algoritmo corrige a estrutura través de movimentação dos nós,