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:
- 2) Simples a esquerda:
Basta empurrar o nó para baixo, e depois para a esquerda, e seu filho à direita o substitui.
Exemplo:
- 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:
- 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:
