Á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