Árboles AVL

Un árbol AVL es un árbol binario de búsqueda que cumple con la condición de que la diferencia entre las alturas de los subárboles de cada uno de sus nodos es, como mucho 1.

La denominación de árbol AVL viene dada por los creadores de tal estructura (Adelson-Velskii y Landis).

Recordamos que un árbol binario de búsqueda es un árbol binario en el cual cada nodo cumple con que todos los nodos de su subárbol izquierdo son menores que la raíz y todos los nodos del subárbol derecho son mayores que la raíz. El tiempo de las operaciones sobre un árbol binario de búsqueda es de "O(log n)" promedio, pero el peor caso es O(n), donde n es el número de elementos.

La propiedad de equilibrio que debe cumplir un árbol para ser AVL asegura que la profundidad del árbol sea O(log(n)), por lo que las operaciones sobre estas estructuras no deberán recorrer mucho para hallar el elemento deseado. Como se verá, el tiempo de ejecución de las operaciónes sobre estos árboles es, a lo sumo O(log(n)) en el peor caso, donde n es la cantidad de elementos del árbol.

Sin embargo, y como era de esperarse, esta misma propiedad de equilibrio de los árboles AVL implica una dificultad a la hora de insertar o eliminar elementos: estas operaciones pueden no conservar dicha propiedad.

Características básicas

• La propiedad de balanceo garantiza que la altura del árbol sea de O(log n).
• En cada nodo del árbol se guarda información de la altura.
• La altura del árbol vacío es -1. 
• Al realizar operaciones de inserción o eliminación se debe actualizar la información de altura de los nodos y recuperar la propiedad de balanceo si fuera necesario, es decir, si hubiera sido destruida.

Cambios en altura

En inserción (dH > 0), si un hijo (y) incrementa su altura, el padre (x) también la incrementa si su factor de equilibrio era -1 o 0 (hijo izquierdo) o bien 0 o +1 (hijo derecho)

En borrado (dH < 0), si un hijo (y) decrementa su altura, el padre (x) también la decrementa si su factor de equilibrio era -1 (hijo izquierdo) o +1 (hijo derecho)

Rotaciones

Tras una operación de inserción o borrado, se recorren los ascendientes, recalculando sus factores de equilibrio y teniendo en cuenta el cambio en altura del subárbol.

Es posible que en el recorrido el factor de equilibrio de algún nodo pasa a valer +2 ó -2 (desequilibrado).

En ese caso se aplica una determinada rotación que restablece el equilibrio del nodo (aunque es posible que cambie la altura del nodo).

En un árbol AVL se necesitan 2 tipos de rotaciones (simples y dobles), en un sentido u otro (izquierdas y derechas).

Teniendo en cuenta los distintos ajustes de factores de equilibrio y posibles resultados respecto al cambio de altura, existen seis casos a considerar.

Rotación 2|1 (Simple derecha).

Rotación 2|0 (Simple derecha).

Rotación 2|-1 (Doble derecha).

Rotación -2|-1 (Simple izquierda).

Rotación -2|0 (Simple izquierda).

Rotación -2|1 (Doble izquierda).