Arboles AVL

DESARROLLO

Arboles AVL:

Un árbol AVL  es un árbol binario balanceado, es decir la altura de la rama izquierda no difiere de la rama derecha en más de una unidad.  Ósea que está en un rango de           (-1 >     0    > 1) si el dígito es mayor que 1 o menor que -1 quiere decir que el árbol esta des-balanceado por lo tanto se harán unas respectivas rotaciones a la derecha o hacia la izquierda. El árbol AVL fue ideado por los matemáticos rusos Adelson-Velskii y Landis.

En la gráfica que observamos podemos ver un árbol AVL balanceado y vemos tres letras (A, B, C) donde A es el nodo padre, y B, C son los sub arboles.

Factor de balance:

Para saber el factor de balance empezamos de abajo hacia arriba es decir:

Como se muestra en la (grafica 2) empezamos desde abajo para hallar el FB; es decir desde donde está el nodo que contiene al “3”, Entonces el FB del nodo que contiene al “3” es 0 porque está apuntando a NULL. Ahora el FB del nodo que contiene al “6” es de 1; porque el nodo “1” tiene una raíz o hijo a su lado izquierdo que es el “3” y a la derecha no tiene nada, entonces al  hacer una sencilla operación de resta se tiene que:

1-0=1

Ahora intentémoslo con el nodo que contiene al 10; según en la gráfica su FB es de 2 probémoslo:

4-2=2

Donde 4 es la cantidad de sub-arboles que tiene a su izquierda y 2 la cantidad de sub-arboles que tiene a su derecha. 

Rotación hacia la derecha:

Para hacer una rotación a la derecha el árbol debe de estar des-balanceado hacia la izquierda es decir:

Ahora lo que debemos hacer es identificar quien es “p” y quien es “q”, para identificarlos se halla el FB del árbol. Entonces para hallar “p” miramos de abajo hacia arriba y apenas se encuentre un 2 le colocamos una flecha al frente indicando que este es “p” y al anterior nodo ósea el “6”, le colocamos “q”. Entonces quedaría de la siguiente manera:

Si recorremos el árbol en Inorden nos quedaría (3,6,7,8,9,10,12,15). Entonces al hacerle la rotación nos debería de quedar de igual manera, entonces para hacer la rotación tomamos el nodo que está indicando “p” y le damos un giro a la derecha y nos quedaría así:

Y ya tenemos el árbol balanceado porque al hacer el FB no nos da ningún número mayor a 1.

Rotación hacia la izquierda:

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

Ahora lo que debemos hacer es identificar quien es “p” y quien es “q”, para identificarlos se halla el FB del árbol. Entonces para hallar “p” miramos de abajo hacia arriba y apenas se encuentre un número mayor que 1 o un número menor que -1  le colocamos una flecha al frente indicando que este es “p” y al anterior nodo ósea el “20”, le colocamos “q”. Entonces quedaría de la siguiente manera:

Lo siguiente es rotar el nodo que está indicando “p” hacia la izquierda y quedaría de la siguiente forma: 

De esta manera al hacer el FB nos damos cuenta que es un árbol balanceado por lo tanto es un árbol AVL.

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. Hay que tener en cuenta dos instrucciones las cuales son:

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

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

Ejemplo:

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

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

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

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

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.

En este link se puede observar un ejemplo de cada una de las rotaciones que se vieron anteriormente 

http://www.youtube.com/watch?v=8ly4jg3TdSE