El nombre AVL son las iniciales de los hombres que idearon este tipo de árbol Adelson-Velskii y Landis en 1962. Básicamente un árbol AVL es un Árbol binario de búsqueda al que se le añade una condición de equilibrio. Esta condición es que para todo nodo la altura de sus subárboles izquierdo y derecho pueden diferir a lo sumo en 1.Caracteristicas

– Un AVL es un ABB
– La diferencia entre las alturas de los subárboles derecho e izquierdo no debe excederse en más de 1.
– Cada nodo tiene asignado un peso de acuerdo a las alturas de sus subárboles.
– Un nodo tiene un peso de 1 si su subárbol derecho es más alto, -1 si su subárbol izquierdo es más alto y 0 si las alturas son las mismas.
– La inserción y eliminación en AVLs es la misma que en los ABBs.
Equilibrio

Equilibrio (n) = altura-der (n) – altura-izq (n) describe relatividad entre subárbol der y subárbol izq.
+ (positivo) -> der mas alto (profundo)
– (negativo) -> izq mas alto (profundo)

Un árbol binario es un AVL si y sólo si cada uno de sus nodos tiene un equilibrio de –1, 0, + 1. Si alguno de los pesos de los nodos se modifica en un valor no válido (2 o -2) debe seguirse un esquema de rotación.

Operaciones sobre un AVL

– Insertar
– Balancear
* Caso 1 Rotación simple izquierda RSI
* Caso 2 Rotación simple derecha RSD
* Caso 3 Rotación doble izquierda RDI
* Caso 4 Rotación doble derecha RDD
– Eliminar
– Calcular Altura

Insertar un Dato
Usamos la misma técnica para insertar un nodo en un ABB ordenado. Trazamos una ruta desde el nodo raíz hasta un nodo hoja (donde hacemos la inserción).

Insertamos el nodo nuevo.
Volvemos a trazar la ruta de regreso al nodo raíz, ajustando el equilibrio a lo largo de ella.
Si el equilibrio de un nodo llega a ser + – 2, volvemos a ajustar los subárboles de los nodos para que su equilibrio se mantenga acorde con los lineamientos AVL (que son +- 1).

Balancear el Árbol+

Caso 1: Rotación simple izquierda RSI
Si esta desequilibrado a la izquierda y su hijo derecho tiene el mismo signo (+) hacemos rotación sencilla izquierda.

Luego de la rotación:


Caso 2: Rotación simple derecha RSD

Luego de la rotación:

Hay varios puntos que cabe señalar aquí:
– Se conserva el orden apropiado del árbol.
– Restablece todos los nodo a equilibrios apropiados AVL
– Conserva el recorrido en orden que el árbol anterior.
– Sólo necesitamos modificar 3 apuntadores para lograr el nuevo equilibrio (con la de la raíz).

Caso 3: Rotación doble izquierda RDI
Si está desequilibrado a la izquierda (FE < –1), y su hijo derecho tiene distinto signo (+) hacemos rotación doble izquierda-derecha.

Otro ejemplo de esta rotación:

Caso 4: Rotación doble derecha RDD
Si esta desequilibrado a la derecha y su hijo izquierdo tiene distinto signo (–) hacemos rotación doble derecha-izquierda.

Otro ejemplo:

Eliminar un Dato

Al eliminar un nodo en un árbol AVL puede afectar el equilibrio de sus nodos. Entonces hay que hacer rotaciones simples o dobles. Eliminas un nodo como lo hacemos en un árbol binario ordenado. Al localizar el nodo que queremos eliminar seguimos este procedimiento:

– Si el nodo es un nodo hoja, simplemente lo eliminamos.
– Si el nodo solo tiene un hijo, lo sustituimos con su hijo.
– Si el nodo eliminado tiene dos hijos, lo sustituimos por el hijo derecho y colocamos el hijo izquierdo en el subárbol izquierdo del hijo derecho.

Ahora que hemos eliminado el nodo, tenemos que volver a equilibrar el árbol:
– Si el equilibrio del padre del nodo eliminado cambia de 0 a +-1 el algoritmo concluye.
– Si el padre del nodo eliminado cambio de +-1 a 0, la altura del árbol ha cambiado y se afecte el equilibrio de su abuelo.
– Si el equilibrio del padre del nodo eliminado cambia de +- 1 a +- 2 hay que hacer una rotación.
– Después de concluirla, el equilibrio del padre podría cambiar, lo que, a su vez, podría forzarnos a hacer otros cambios (y probables rotaciones) en toda la ruta hacia arriba a medida que ascendemos hacia la raíz. Si encontramos en la ruta un nodo que cambie de 0 a +- 1 entonces terminamos.

Implementación de Árbol AVL en SEED

Descripción
Es una representación de un Árbol Binario auto-balanceable, su fin es el de crear un factor de balance entre los Nodos del Árbol de manera para cada Nodo en cualquier parte del Árbol, la altura de la rama izquierda no difiera en más de una unidad de la altura de la rama derecha o viceversa, y de esta manera después de cada operación siempre se encuentren balanceados “por altura”.

La implementación de este Árbol AVL se realiza tomando como base en Árbol Binario de Búsqueda (ABB), por tal motivo se realiza la herencia de los atributos, métodos y operaciones, la inserción y retiro de datos en el Árbol se realizan de forma muy similar, con la condición que si alguna de las operaciones altera el equilibrio del Árbol, se deben realizar operaciones especiales denominadas “rotaciones” que permiten balancear nuevamente el Árbol.

Al igual que la estructura ArbolBinario que fundamenta su implementación en el elemento fundamental “NodoBin”, la Estructura ArbolAVL basa su funcionamiento en el elemento “NodoAVL”, “NodoAVL” posee las misma características de “NodoBin”, por esto “NodoAVL” hereda los atributos y operaciones de “NodoBin”, solo difiere la aparición de un nuevo atributo balanceo “bal”. A su vez, cada uno de los Nodos Binarios (NodoBin) también deben ser alterados, de manera que en cada uno de ellos se pueda almacenar su factor de balance (atributo “bal”) y así poder hacer más fácil la realización del balanceo. Las operaciones realizadas por el Árbol AVL no son muy distintas a las planteadas para los anteriores Arboles Binarios de Búsqueda, con la diferencia del balanceo y las rotaciones; Por lo que esta estructura extiende de la estructura ArbolBinarioBusqueda, la inserción y retiro de datos dentro del Árbol es de manera ordenada, manteniendo siempre el factor de balance de cada Nodo en un valor que oscila entre 1 y -1.

En el siguiente Diagrama se puede observar los atributos y operaciones que se implementaron en la estructura.

Requerimientos funcionales implementados para Árboles AVL:
RF1 – Crear un nuevo Árbol AVL.
RF2 – Conocer y editar la raíz del Árbol AVL.
RF3 – Insertar nuevos datos en un Árbol AVL, sin que este pierda sus propiedades.
RF4 – Eliminar datos de un Árbol AVL, sin que este pierda sus propiedades.
RF5 – Consultar la existencia de objetos dentro del Árbol AVL.
RF6 – Consultar el listado de hojas de un Árbol AVL.
RF7 – Conocer el número de hojas del Árbol AVL.
RF8 – Recorrer un Árbol AVL en Preorden.
RF9 – Recorrer un Árbol AVL en Inorden.
RF10 – Recorrer un Árbol AVL en PostOrden.
RF11 – Recorrer un Árbol AVL por niveles.
RF12 – Conocer el peso de un Árbol AVL.
RF13 – Consultar la altura de un Árbol AVL.
RF14 – Conocer por consola los datos presentes en el Árbol AVL.

Implementación de un Simulador para Árboles AVL:
El Simulador para Árbol AVL posee las operaciones indicadas por su menú de opciones dentro del mismo: