ARBOLES AVL

INTRODUCCIÓN

Definición. 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.

Recordamos también que el tiempo de las operaciones sobre un árbol binario de búsqueda son 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 operaciones 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.

Operaciones con arboles AVL

A continuación una operación sencilla sobre un árbol binario de búsqueda que conserva el orden en sus nodos y que nos ayudará a restaurar la propiedad de equilibrio de un árbol AVL al efectuar operaciones sobre el mismo que puedan perturbarla. Hay dos tipos de rotación simple: hacia la izquierda, hacia la derecha.

En este ejemplo al momento de querer insertar el nodo 3 se produce un  desequilibrio. Para retomar la propiedad de equilibrio simplemente se realiza una rotación simple. En este caso se dice que la rotación es izquierda ya que la “pérdida de equilibrio se produce hacia la izquierda”.

Así quedaría el árbol después de la rotación simple, y ahora si podemos afirmar que es un árbol AVL porque está equilibrado

En el caso de un “desequilibrio” hacia la derecha, la rotación es análoga y se denomina rotación simple derecha.

Rotaciones dobles

Hemos visto cómo restaurar la propiedad de equilibrio cuando se presentan desequilibrios “hacia la izquierda” o “hacia la derecha” luego de realizar inserciones en un árbol AVL. Sin embargo y como veremos, pueden ocurrir “desequilibrios en zig-zag”. Como por ejemplo: