Árvores AVL
Eficiência temporal
Evita seu pior caso de degeneração
Árvore de busca binária desbalanceada
Auto balanceamento
Árvores AVL
Rotações
As alturas das subárvores esquerda e direita de cada nó diferem no máximo por uma unidade
Fator de balanceamento de cada nó varia entre -1, 0 e 1
Altura da árvore vazia é -1
transformação local para reequilibrar a árvore
Simples
Dupla
Rotação direita(R-rotation)
Rotação direita-esquerda(RL-rotation)
Rotação esquerda(L-rotation)
Rotação esquerda-direita(LR-rotation)
chave inserida na subárvore esquerda do filho esquerdo
chave inserida na subárvore direita do filho da direita
chave inserida na subárvore esquerda do filho direito
chave inserida na subárvore direita do filho esquerdo