Algoritmos/Estruturas de dados/Árvore AVL

Uma árvore AVL , é aquela onde em qualquer nó, as alturas de suas duas subárvores, na esquerda e direita, diferem em módulo de no máximo uma unidade. Ou seja, Cada nó possui um fator de balanceamento que consiste na diferença entre o número de níveis de suas subárvores à esquerda e à direita:

AVLfator(i)  = alturaDir(i) –alturaEsq(i)

Cada nó armazena seu fator de balanceamento, e quando o fator de um nó se torna ±2, deve ser efetuada uma rotação nesse nó.

Existem quatro tipos de rotação:

• 1) Simples a direita:

Basta empurrar o nó para baixo, e depois para a direita, e seu filho da esquerda o substitui.

Exemplo:

Rotação Simples à Direita

• 2) Simples a esquerda:

Basta empurrar o nó para baixo, e depois para a esquerda, e seu filho à direita o substitui.

Exemplo:

Rotação Simples à Esquerda

• 3) Rotação Dupla à direita:

A rotação dupla à direita é combinação da rotação para a esquerda, seguido de uma rotação para a direita. Exemplo:

Rotação Dupla à Direita

• 4) Rotação Dupla à esquerda:

A rotação dupla à esquerda é uma combinação da rotação para a direita, seguido de uma rotação para a esquerda.

Exemplo:

Rotação Dupla à Esquerda