Il nome AVL viene dai suoi inventori G.M. Adelson-Velsky e E.M. Landis, che pubblicarono il loro algoritmo nel saggio "An algorithm for the organization of information" del 1962.
Per evitare di dover contare ogni volta l'altezza di un sottoalbero, si salva nel nodo il coefficiente di bilanciamento, che è definito come l'altezza del sottoalbero destro meno quella del sottoalbero sinistro.