Árvore AVL (AVL Tree)

Na ciência da computação, uma árvore AVL (em homenagem aos inventores Adelson-Velsky e Landis) é uma árvore de pesquisa binária auto balanceada. Foi a primeira estrutura de dados a ser inventada. Em uma árvore AVL, as alturas de duas sub-árvores filhas de qualquer nó diferem no máximo em um; se a qualquer momento diferirem por em mais de um, um rebalanceamento é feito para restaurar esta propriedade. Pesquisa, inserção e exclusão possuem tempo O(log n) tanto na média quanto nos piores casos, onde n é o número de nós na árvore antes da operação. Inserções e exclusões podem exigir que a árvore seja reequilibrada por uma ou mais rotações.

Animação mostrando a inserção de vários elementos em uma árvore AVL. Inclui as rotações de esquerda, direita, esquerda-direita e direita-esquerda.

Árvore AVL com fatores de equilíbrio (verde)

Rotações de Árvores AVL

Rotação Esquerda-Esquerda

Rotação direita-direita

Rotação Esquerda-Direita

Rotação Direita-Esquerda