Estructuras de datos y algoritmos avanzados

Estructuras de datos y algoritmos avanzados: AVL, heaps y Dijkstra

En este módulo aprenderás los conceptos clave de los árboles AVL, la representación de heaps en arreglos y el funcionamiento del algoritmo de Dijkstra. Cada apartado incluye definiciones, ejemplos y explicaciones que facilitan la comprensión y la memorización.

Origen del nombre del algoritmo AVL

El algoritmo AVL lleva sus iniciales de los apellidos de sus creadores: Adelson‑Velsky y Landis. Fue publicado en 1962 y constituye el primer árbol binario de búsqueda auto‑balanceado.

Recuerda: A‑V‑L = nombres de los creadores.

Factor de equilibrio en un árbol AVL

El factor de equilibrio (FE) de un nodo se calcula como la diferencia entre la altura del subárbol derecho y la altura del subárbol izquierdo:

• FE = altura(derecha) − altura(izquierda)

Este valor indica cuánto se desbalancea la rama superior del árbol. Un FE positivo significa que el subárbol derecho es más alto; un FE negativo indica lo contrario.

Altura derecha menos altura izquierda.

Condición de equilibrio en un árbol AVL

Un árbol AVL se considera equilibrado cuando todos sus nodos tienen un factor de equilibrio entre -1 y 1 (inclusive). Esta restricción garantiza que la altura del árbol sea O(log n), lo que permite operaciones de búsqueda, inserción y eliminación en tiempo logarítmico.

Regla práctica: -1 ≤ FE ≤ 1.

Rotaciones en árboles AVL

Cuando una inserción genera un desequilibrio, se aplican rotaciones para restaurar el balance. Existen cuatro casos típicos:

• LL (izquierda‑izquierda): rotación simple hacia la derecha.
• RR (derecha‑derecha): rotación simple hacia la izquierda.
• LR (izquierda‑derecha): rotación doble (izquierda seguida de derecha).
• RL (derecha‑izquierda): rotación doble (derecha seguida de izquierda).

En el caso LL la rotación correcta es simple hacia la derecha, ya que el desequilibrio está en el subárbol izquierdo del nodo desbalanceado.

Imagina empujar una puerta que se atora al abrirla: la rotación derecha la libera.

Características de un heap completo

Un heap (montículo) es una estructura de datos basada en un árbol binario casi completo. Su característica principal es que todos los niveles están completos excepto el último, que se llena de izquierda a derecha. Esta forma garantiza la máxima compactación y permite una representación eficiente en un arreglo.

Piensa en una estantería donde cada fila se llena antes de comenzar la siguiente.

Representación de un heap en un arreglo

Gracias a la completitud, los nodos de un heap pueden almacenarse en un vector o arreglo usando índices simples:

• Para el nodo en la posición i (índice base 0):
  • Padre = (i‑1) / 2
  • Hijo izquierdo = 2*i + 1
  • Hijo derecho = 2*i + 2

Esta representación permite acceso O(1) a cualquier nodo y operaciones de inserción y extracción en O(log n) mediante min‑heap o max‑heap.

Piensa en un árbol como una fila numerada.

Algoritmo de Dijkstra: condición de finalización

El algoritmo de Dijkstra encuentra el camino más corto desde un origen a todos los vértices de un grafo ponderado con pesos no negativos. La ejecución termina cuando la cola de prioridad queda vacía. En ese momento, todos los vértices alcanzables han sido extraídos y sus distancias mínimas están fijadas.

Recuerda: “vacío = terminado”.

Estructura de datos utilizada en Dijkstra

Para seleccionar el siguiente vértice a procesar, Dijkstra emplea una cola de prioridad (usualmente implementada como un min‑heap). Esta estructura garantiza que siempre se extraiga el vértice con la distancia provisional más pequeña, manteniendo la optimalidad del algoritmo.

Piensa “min‑heap” como una fila de corredores más rápidos.

Resumen de conceptos clave

• AVL: árbol auto‑balanceado, factor de equilibrio = altura(derecha) − altura(izquierda), FE entre -1 y 1.
• Rotaciones AVL: LL → rotación derecha, RR → rotación izquierda, LR y RL → rotaciones dobles.
• Heap completo: todos los niveles llenos salvo el último, que se llena de izquierda a derecha.
• Representación de heap en arreglo: índices padre/hijo calculados aritméticamente.
• Dijkstra: termina cuando la cola de prioridad está vacía; usa un min‑heap para seleccionar vértices.

Preguntas de autoevaluación

Refuerza tu aprendizaje respondiendo las siguientes preguntas. Cada una está acompañada de su explicación para consolidar el conocimiento.

1. ¿Cuál es el origen del nombre del algoritmo AVL?

   Respuesta: Proviene de los apellidos de Adelson, Velsky y Landis.

2. ¿Cómo se calcula el factor de equilibrio en un árbol AVL?

   Respuesta: Diferencia entre las alturas del subárbol derecho e izquierdo.

3. ¿Cuándo está equilibrado un árbol AVL?

   Respuesta: Cuando los factores de equilibrio están entre -1, 0 o 1.

4. En una inserción LL, ¿qué rotación se realiza?

   Respuesta: Rotación simple hacia la derecha.

5. ¿Cuál es la característica principal de un heap completo?

   Respuesta: Todos los niveles están completos excepto el último, que se llena de izquierda a derecha.

6. ¿Cómo se aprovecha la completitud al implementar un heap?

   Respuesta: Representándolo en un arreglo mediante índices.

7. ¿Cuál es la condición de finalización típica del algoritmo de Dijkstra?

   Respuesta: Cuando la cola de prioridad queda vacía.

8. ¿Qué estructura de datos se usa habitualmente en Dijkstra?

   Respuesta: Una cola de prioridad (min‑heap).

Dominar estos conceptos te permitirá diseñar soluciones eficientes y comprender algoritmos avanzados en la práctica de la informática.