Arboles AVL

El arbol AVL o Arbol Binario Valanceado se caracteriza por tener una altura en la rama derecha e izquiera que no supera la unidad   (-1 >     0    > 1), en caso de que no se cumpla lo anterior, no es un arbol balanceado, a lo cual sera necesario realizar rotacion (a la derecha o a la izquierda).

El árbol AVL fue ideado por los matemáticos rusos Adelson-Velskii y Landis.

En la gráfica se muestra un árbol AVL balanceado con los nodos (A, B, C), siendo A el nodo padre y B,C sub arboles.

Factor de balance:

Se empieza a determinar el Factor Balance desde la parte baja del árbol o base, en este caso desde el nodo 3, cuyo FB es 0, ya que este apunta a NULL. Las conexiones que se desprenden al lado izquierdo de cada nodo son positivos, los de la derecha negativos, vasta con restar el total que se tiene de los niveles derechos a los izquierdos para obtener el FB, por ejemplo para el 6 el FB es igual a 1.

Rotación hacia la derecha:

Si el árbol se encuentra des balanceado hacia la izquierda, basta con realizar la rotación al lado derecho para equilibrar el árbol (similar al proceso que se realiza con una balanza):

Se identifica p y q, determinando el FB del árbol; si se observa de abajo hacia arriba, el primer FB que sea diferente a 1 se le señala con una flecha y se le identifica con una p, anterior al nodo donde se hallo p, se le identificara como q:

Al recorrer el árbol Inorden antes de la rotación, se obtiene (3,6,7,8,9,10,12,15), el cual debe quedar igual luego de la rotación:

La raíz del árbol queda con FB 1, de manera que es balanceado.

Rotación hacia la izquierda:

Para hacer una rotación a la izquierda el árbol debe de estar desbalanceado hacia la derecha:

Se identifica p y q segun el FB que se explico anteriormente: 

Se rota el nodo identificado como p hacia la derecha:

Al realizar FB, se puede concluir que el arbol se encuentra balanceado, debido a que el nodo (12) posee factor de balance 0.

Doble rotación hacia la derecha:

Para hacer la doble rotación a la derecha el árbol debe estar desbalanceado hacia la izquierda, el factor de balance del nodo indicado por “p” debe ser mayor a 1 y el FB del nodo indicado por q es igual a -1. Se deben considerar los siguientes pasos:

-         -Una rotación a la izquierda desde q.

-         -Una rotación a la derecha desde p.

Una vez identificado el FB, se señala p y q:

Se rota el nodo señalado como q hacia la izquierda:

Ahora, se debe rotar el nodo p hacia la derecha:

Verificando FB, se determina que el arbol se encuentra balanceado.

Doble rotación hacia la izquierda:

Para hacer la doble rotación a la izquierda el árbol debe estar desbalanceado hacia la derecha, el factor de balance del nodo indicado por “p” debe ser menor a -1 y el FB del nodo indicado por “q” es igual a -1 ó a 1. Hay que tener en cuenta dos instrucciones las cuales son:

-         -Una rotación a la derecha desde “q”.

-         -Una rotación a la izquierda desde “p”.

Ejemplo:

Ya identificamos el FB ahora identificamos quien es “p” y quien es “q” al hacerlo nos debería quedar así:

Ahora vamos a empezar las rotaciones, dice que la primera rotación es del nodo que está apuntando “q” y es hacia la derecha entonces quedaría de la siguiente manera:

Como ya rotamos el nodo que apunta “q”, ahora rotamos hacia la izquierda el nodo que apunta “p” y nos quedaría así:

Y nos queda un árbol AVL balanceado, podemos verificarlo al hacer el FB.

Código C++: