AVL Tree es un árbol de búsqueda binario equilibrado. La publicación introdujo árboles de búsqueda binarios. Los tiempos de búsqueda, inserción y eliminación de un árbol binario dependen de la altura del árbol. En el peor de los casos, la altura es O(n). Si un árbol está perfectamente equilibrado, es decir, un árbol binario completo, su altura es log n. ¿Podemos mantener un árbol perfectamente equilibrado? Sí, pero hacerlo será costoso. El compromiso es mantener un árbol bien equilibrado, es decir, las alturas de los dos subárboles de cada nodo son aproximadamente las mismas.

Los árboles AVL están bien equilibrados. Los árboles AVL fueron inventados en 1962 por dos informáticos rusos, G. M. Adelson-Velsky y E. M. Landis (de ahí el nombre AVL). En un árbol AVL, la diferencia entre las alturas de los dos subárboles de cada nodo es 0 o 1. Se puede demostrar que la altura máxima de un árbol AVL es O(log n).

El proceso para insertar o eliminar un elemento en un árbol AVL es el mismo que en un árbol de búsqueda binario normal, excepto que es posible que deba reequilibrar el árbol después de una operación de inserción o eliminación. El factor de equilibrio de un nodo es la altura de su subárbol derecho menos la altura de su subárbol izquierdo. Se dice que un nodo está equilibrado si su factor de equilibrio es -1, 0 o 1. Un nodo se considera pesado a la izquierda si su factor de equilibrio es -1, y pesado a la derecha si su factor de equilibrio es 1.