Balanceo de Árboles: Árboles AVL

4.1 Problemas de árboles no balanceados

En los árboles normales (no balanceados) al añadir elementos pueden ocurrir efectos indeseados.

1. Incremento de la altura del árbol:

En los árboles no balanceados la altura puede alcanzar n (donde n es el número de nodos), lo que lleva a una degradación del rendimiento.

El tiempo de ejecución de las operaciones principales (búsqueda, inserción, eliminación) en el peor caso se convierte en O(n).

2. Distribución desigual de nodos:

En los árboles no balanceados algunos subárboles pueden contener significativamente más nodos que otros, lo que lleva a un uso ineficiente de la memoria y un aumento en el tiempo de procesamiento.

3. Deterioro del tiempo de ejecución de las operaciones:

En los árboles no balanceados, las operaciones de búsqueda, inserción y eliminación requieren más tiempo debido al aumento de la altura del árbol.

Ejemplo de un árbol no balanceado:

En este ejemplo, el árbol se convierte efectivamente en una lista enlazada, y el tiempo de ejecución de las operaciones se vuelve lineal.

4.2 Definición de un árbol AVL y sus propiedades

Un árbol AVL (nombrado por sus inventores, Adelson-Velsky y Landis) es un tipo de árbol de búsqueda binaria balanceado, en el cual para cualquier nodo la diferencia de altura de sus subárboles izquierdo y derecho no excede 1.

Propiedades de un árbol AVL:

1. Balanceo:

La diferencia de alturas de los subárboles izquierdo y derecho de cualquier nodo no excede 1.

Esto asegura una altura del árbol de O(log n), donde n es el número de nodos, lo que garantiza una ejecución efectiva de las operaciones de búsqueda, inserción y eliminación.

2. Árbol de búsqueda binaria:

Un árbol AVL posee todas las propiedades de un árbol de búsqueda binaria: para cualquier nodo, todos los claves en el subárbol izquierdo son menores que la clave del nodo, y todos los claves en el subárbol derecho son mayores que la clave del nodo.

3. Balanceo automático:

Después de cada operación de inserción o eliminación se realiza un balanceo del árbol para preservar sus propiedades.

4.3 Ejemplos de balanceo de árboles

Las rotaciones son operaciones que se realizan para restaurar el balance en un árbol AVL después de insertar o eliminar nodos. Existen cuatro tipos de rotaciones: izquierda, derecha, izquierda-derecha y derecha-izquierda.

1. Rotación Izquierda (Left Rotation):

En la rotación izquierda el nodo x se eleva, y su nodo hijo derecho y se convierte en su padre. El subárbol izquierdo de y se convierte en el subárbol derecho de x.

2. Rotación Derecha (Right Rotation):

En la rotación derecha el nodo x se eleva, y su nodo hijo izquierdo y se convierte en su padre. El subárbol derecho de y se convierte en el subárbol izquierdo de x.

3. Rotación Izquierda-Derecha (Left-Right Rotation):

Primero se realiza una rotación izquierda sobre el nodo hijo izquierdo, y luego una rotación derecha sobre el mismo nodo.

4. Rotación Derecha-Izquierda (Right-Left Rotation):

Primero se realiza una rotación derecha sobre el nodo hijo derecho, y luego una rotación izquierda sobre el mismo nodo.

4.4 Operaciones principales en árboles AVL

Las operaciones principales en árboles AVL incluyen inserción, eliminación y búsqueda.

Inserción (Insertion)

Debemos insertar un nuevo nodo en el árbol AVL y balancearlo si es necesario.

Pasos:

1. Inserción del nodo:
   • Comenzamos desde la raíz del árbol y recursivamente encontramos el lugar correcto para el nuevo nodo, comparando su valor con los nodos actuales.
   • Insertamos el nuevo nodo en el lugar encontrado, como en un árbol de búsqueda binaria común.
2. Actualización de alturas:
   • Después de insertar, actualizamos las alturas de todos los nodos en el camino desde el nuevo nodo hasta la raíz.
3. Balanceo del árbol:
   • Comprobamos el balance de cada nodo en el camino desde el nuevo nodo hasta la raíz.
   • Si el balance de algún nodo se rompe (diferencia de alturas de los subárboles izquierdo y derecho es mayor que 1), realizamos la rotación correspondiente para restaurar el balance.

Ejemplo:

2. Eliminación (Deletion)

Debemos eliminar un nodo del árbol AVL y balancearlo si es necesario.

Pasos:

1. Búsqueda y eliminación del nodo:

• Comenzamos desde la raíz del árbol y recursivamente encontramos el nodo a eliminar.
• Eliminamos el nodo como en un árbol de búsqueda binaria común:
• Si el nodo es una hoja, simplemente lo eliminamos.
• Si el nodo tiene un hijo, reemplazamos el nodo con su hijo.
• Si el nodo tiene dos hijos, encontramos el nodo más pequeño en el subárbol derecho (o el más grande en el izquierdo), copiamos su valor en el nodo a eliminar y recursivamente eliminamos el nodo más pequeño en el subárbol derecho.

2. Actualización de alturas:

• Después de eliminar, actualizamos las alturas de todos los nodos en el camino desde el nodo eliminado hasta la raíz.

3. Balanceo del árbol:

• Comprobamos el balance de cada nodo en el camino desde el nodo eliminado hasta la raíz.
• Si el balance de algún nodo se rompe, realizamos la rotación correspondiente para restaurar el balance.

Ejemplo:

3. Búsqueda (Search)

Debemos encontrar un nodo con un valor dado en el árbol AVL.

Pasos:

1. Búsqueda recursiva:

• Comenzamos desde la raíz del árbol y recursivamente comparamos el valor buscado con los nodos actuales.
• Si el valor es menor que el nodo actual, pasamos al subárbol izquierdo.
• Si el valor es mayor que el nodo actual, pasamos al subárbol derecho.
• Si el valor coincide con el nodo actual, devolvemos este nodo.

Ejemplo: