th3patoxxp

El árbol AVL toma su nombre de las iniciales de los apellidos de sus inventores, Georgii Adelson-Velskii y Yevgeniy Landis. Lo dieron a conocer en la publicación de un artículo en 1962,«An algorithm for the organization of information» («Un algoritmo para la organización de la información»).

Los árboles AVL están siempre equilibrados de tal modo que para todos los nodos,la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa. Gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsquedaen uno de estos árboles se mantiene siempre en orden de complejidad O(log n). El factor de equilibrio puede ser almacenado directamente en cada nodo o ser computado a partir de las alturasde los subárboles.

Para conseguir esta propiedad de equilibrio, la inserción y el borrado de los nodos se ha de realizar de una forma especial. Si al realizar una operación de inserción oborrado se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los nodos.

Los árboles AVL más profundos son los árboles de Fibonacci.
Definición formalDefinición de la altura de un árbol

Sea T un árbol binario de búsqueda y sean T_i y T_d sus subárboles, su altura H(T), es:

0 si el árbol T contiene solo la raíz
1 + \max(H(T_i),H(T_d)) si contiene más nodos

Definición de árbol AVL

Un árbol vacío es un árbol AVL
Si T es un árbol no vacío y T_i y T_d sus subárboles, entonces T es AVL si y solo si:T_i es AVL
T_d es AVL
|H(T_i) - H(T_d)| el nodo está equilibrado y sus subárboles tienen exactamente la misma altura.
1 -> el nodo está equilibrado y susubárbol derecho es un nivel más alto.
-1 -> el nodo está equilibrado y su subárbol izquierdo es un nivel más alto.

Si el factor de equilibrio |Fe| >= 2 es necesario reequilibrar.