Arvore AVL

Uma árvore binária é denominada AVL quando a diferença de altura entre as subárvores da esquerda e direita (sae e sad) de um nó qualquer N não é
superior a 1. O fato da árvore estar balanceada resulta em ganho de desempenho para operações realizadas sobre árvores binárias, como na inserção, remoção e consulta de valores.
Se a árvore estiver balanceada, todas estas operações gastam, no pior caso,
um tempo O(logn), que neste caso representa a altura da árvore binária
balanceada, mas se a árvore não estiver balanceada, o tempo de busca no pior caso pode ser 2.

Algoritmo para balanceamento:

Se a árvore não estiver balanceada, o tempo de busca para o caso pode ser
O(n), ou seja, equivalente ao tempo de busca de valores em uma lista
encadeada (no pior caso, todos os elementos tem que ser consultados).

Quando inserimos um novo nó em uma árvore balanceada, podem ocorrer três situações distintas:
– se h(sae) = h(sad), após a inserção as alturas vão ser diferentes, porém a
árvore continua balanceada
– se h(sae) > h(sad) e o nó for inserido na sad, as alturas ficam iguais e o
balanceamento foi melhorado.
– se h(sae) > h(sad) e o nó for inserido na sae, o balanceamento fica violado.

Algoritmo para inserção

Rebalancear a árvore

Quando precisamos rebalancear a árvore, devemos escolher uma dentre 4 rotações para realizar esta tarefa:

  • Rotação à Esquerda
  • Rotação à Direita
  • Dupla rotação a Esquerda (Esquerda + direita)
  • Dupla rotação a Direita (Direita + Esquerda)

Dessa forma você deixa sua árvore balanceada.

Para ter acesso à implementação integral do algorismo, acesse :

https://gist.github.com/rodrigovilar/5754425