AVL Tree é uma árvore de pesquisa binária balanceada. A postagem introduziu árvores de pesquisa binária. Os tempos de busca, inserção e exclusão de uma árvore binária dependem da altura da árvore. No pior caso, a altura é O(n). Se uma árvore é perfeitamente balanceada – ou seja, uma árvore binária completa – sua altura é log n. Podemos manter uma árvore perfeitamente equilibrada? Sim, mas isso custará caro. O compromisso é manter uma árvore bem balanceada – ou seja, as alturas das duas subárvores de cada nó são aproximadamente as mesmas.

Árvores AVL são bem balanceadas. As árvores AVL foram inventadas em 1962 por dois cientistas da computação russos, GM Adelson-Velsky e EM Landis (daí o nome AVL). Em uma árvore AVL, a diferença entre as alturas das duas subárvores de cada nó é 0 ou 1. Pode-se mostrar que a altura máxima de uma árvore AVL é O(log n).

O processo para inserir ou excluir um elemento em uma árvore AVL é o mesmo que em uma árvore de pesquisa binária normal, exceto que pode ser necessário reequilibrar a árvore após uma operação de inserção ou exclusão. O fator de equilíbrio de um nó é a altura de sua subárvore direita menos a altura de sua subárvore esquerda. Um nó é considerado balanceado se seu fator de equilíbrio for -1, 0 ou 1. Um nó é considerado pesado à esquerda se seu fator de equilíbrio for -1, e pesado à direita se seu fator de equilíbrio for 1.