javascript-algorithms
Á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
