Fundamentos de Algoritmos: Rotaciones AVL, Teorema Maestro y Coste de Huffman

Tipos de Rotaciones en Árboles AVL

1. Rotación Simple a la Derecha (Right Rotation, RR)

Se utiliza cuando el subárbol izquierdo está más alto que el derecho (desbalance Left-Left o LL).

      y                  x
     / \                / \
    x   C    ---->    A   y
   / \                    / \
  A   B                  B   C

• y se mueve hacia la derecha.
• x sube como nuevo nodo «padre» (raíz).
• Esto corrige un desbalance del tipo Left-Left (LL).

2. Rotación Simple a la Izquierda (Left Rotation, LL)

Es el caso simétrico. Se utiliza cuando el subárbol derecho está más alto (desbalance Right-Right o RR).

      x                  y
     / \                / \
    A   y    ---->    x   C
       / \          / \
      B   C        A   B

• x se mueve hacia la izquierda.
• y sube como nuevo nodo «padre» (raíz).
• Corrige desbalance Right-Right (RR).

3. Rotación Doble Izquierda-Derecha (Left-Right, LR)

Se utiliza cuando el subárbol izquierdo está alto, pero su hijo derecho es el más alto (desbalance Left-Right o LR).

1. Primero, rotación izquierda sobre el hijo izquierdo (x).
2. Luego, rotación derecha sobre el nodo desbalanceado (z).

      z                  z                  y
     / \                / \                / \
    x   D    -->      y   D    -->      x   z
   / \              / \                / \ / \
  A   y            x   C              A B C D
     / \          / \
    B   C        A   B

4. Rotación Doble Derecha-Izquierda (Right-Left, RL)

Es el caso simétrico (espejo) del LR. Se utiliza cuando el subárbol derecho está alto, pero su hijo izquierdo es el más alto (desbalance Right-Left o RL).

1. Rotación derecha sobre el hijo derecho (z).
2. Rotación izquierda sobre el nodo desbalanceado (x).

      x                  x                  y
     / \                / \                / \
    A   z    -->      A   y    -->      x   z
       / \              / \            / \ / \
      y   D            B   z          A B C D
     / \                  / \
    B   C                C   D

El Teorema Maestro para Ecuaciones de Recurrencia

El Teorema Maestro es una herramienta fundamental para determinar la complejidad temporal de algoritmos recursivos de tipo «Divide y Vencerás», cuya ecuación de recurrencia sigue la forma $T(n) = aT(n/b) + f(n)$.

Parámetros Clave del Teorema Maestro

• a: Número de llamadas recursivas.
• b: Factor de división del tamaño del problema ($b > 1$).
• k: Exponente de $n$ en la función $f(n)$ (orden polinomial).
• p: Exponente del logaritmo en la función $f(n)$ (orden logarítmico).

La comparación crucial se realiza entre $a$ y $b^k$.

Concepto de Logaritmo

El logaritmo responde a la pregunta:

“¿A qué potencia debo elevar la base para obtener un número dado?”

equivale a

Cálculo de Costes Algorítmicos: Aplicación al Algoritmo de Huffman

1. Identificación del Algoritmo y sus Operaciones

Para el Algoritmo de Huffman, que opera sobre un alfabeto de $c$ símbolos, las operaciones realizadas en la Cola de Prioridad son:

1. $c$ inserciones iniciales (una por cada símbolo del alfabeto).
2. $c – 1$ iteraciones del bucle principal, donde en cada iteración se realizan:
   • $2 \times$ eliminarMinimo (extracción de los dos nodos de menor frecuencia).
   • $1 \times$ insertar (inserción del nodo combinado).

Consideraciones importantes:

• Nunca se usa disminuirPrioridad (a menos que el algoritmo lo requiera explícitamente).
• Nunca se cuenta consultarMinimo a menos que se haga explícitamente.

2. Conteo de Operaciones Totales

Se resume el número de veces que ocurre cada operación en función de $c$:

3. Uso de Costes Amortizados de la Cola de Prioridad

Es crucial utilizar los costes temporales correctos según la implementación de la Cola de Prioridad (Montículo Binomial, Fibonacci, etc.).

• Usa costes amortizados, ya que el ejercicio generalmente solicita el coste total del algoritmo:
  • Insertar $\to O(1)$ amortizado.
  • EliminarMinimo $\to O(\log c)$ amortizado (si $c$ es el tamaño máximo de la cola).
• Advertencia: No uses el peor caso puntual de cada operación, salvo que te pidan explícitamente “peor caso de cada operación”.

4. Cálculo del Coste Total por Tipo de Operación

Se multiplica el número de veces que ocurre la operación por su coste amortizado:

5. Determinación del Coste Total Dominante

• Al comparar $O(c)$ y $O(c \log c)$, el término dominante es $O(c \log c)$.
• Esa será la respuesta final de la complejidad temporal del algoritmo de Huffman.

6. Reglas de Oro y Consejos de Examen

• Ignora operaciones que Huffman no utilice (como disminuirPrioridad).
• Coste Total vs. Peor Caso Puntual: Si el ejercicio pide el coste del algoritmo completo, usa costes amortizados, incluso si se menciona la frase «peor caso».
• Tamaño de la Cola: El tamaño máximo de la cola suele ser $k \approx c$, por lo que $\log k \approx \log c$.

Ejercicio 5: Coste de Huffman con Montículo de Fibonacci

Ejercicio 5 Examen Enero (Costes Huffman)

Un montículo de Fibonacci es una estructura de datos que permite implementar el Tipo Abstracto de Datos Cola de Prioridad con costes temporales específicos, siendo $k$ el tamaño de la cola de prioridad.

Determine, en función de $c$, el coste temporal en el peor caso del algoritmo de Huffman cuando se aplica a un alfabeto de $c$ caracteres, suponiendo que la cola de prioridad utilizada se implementa mediante un montículo de Fibonacci.

Justifique su respuesta.

Solución Detallada

El algoritmo de Huffman realiza inicialmente c inserciones en una cola de prioridad y,
posteriormente, un bucle de c - 1 iteraciones, cada una con dos extracciones del mínimo y
una inserción.

Dado que cada inserción tiene coste amortizado O(1), el coste total de las inserciones es
O(c) en la primera etapa y O(c) en la segunda etapa. Cada extracción del mínimo tiene coste
amortizado O(log c), por lo que el coste total de las extracciones es O(c log c).

El coste temporal del algoritmo en el peor caso viene dado por el coste dominante: O(c log c).

Ejercicio 6: Coste de Huffman con Montículo Binomial Perezoso

Ejercicio 6 Examen Junio (Costes)

Un montículo binomial perezoso es una estructura de datos que permite implementar el Tipo Abstracto de Datos Cola de Prioridad con costes temporales específicos, siendo $k$ el tamaño de la cola de prioridad.

[Nota: Se asume que los costes amortizados son O(1) para insertar y O(log k) para eliminarMínimo, siguiendo la práctica habitual en este contexto.]

Determine, en función de $c$, el coste temporal en el peor caso del algoritmo de Huffman cuando se aplica a un alfabeto de $c$ caracteres, suponiendo que la cola de prioridad utilizada por el algoritmo se implementa mediante un montículo binomial perezoso.

Explique cómo se obtiene el resultado, detallando cuántas veces se ejecuta cada operación y cuál es el coste total asociado a cada una de ellas.

Solución Detallada

El algoritmo de Huffman realiza inicialmente c inserciones en una cola de prioridad y,
posteriormente, un bucle de c - 1 iteraciones, cada una con dos extracciones del mínimo y
una inserción.

1. Conteo de operaciones:
   - Inserciones totales: c + (c - 1) = 2c - 1.
   - Extracciones del mínimo totales: 2 * (c - 1) = 2c - 2.

2. Costes amortizados (asumiendo O(1) para insertar y O(log c) para eliminarMínimo):
   - Coste total de inserciones: (2c - 1) * O(1) = O(c).
   - Coste total de extracciones: (2c - 2) * O(log c) = O(c log c).

El coste temporal del algoritmo en el peor caso (coste total amortizado) viene dado por el término dominante: O(c log c).

Ejercicio 7: Aplicación del Teorema Maestro a un Algoritmo Recursivo

Ejercicio 7 Examen Enero (Teorema Maestro)

El siguiente algoritmo recursivo determina si un dato aparece en un vector:

bool buscar(const vector<float> &v, float dato) {
    if (v.size() == 0)
        return false;
    if (v.size() == 1)
        return v[0] == dato;

    int mitad = v.size() / 2;

    // Crear subvector izquierda (Costo O(n/2))
    vector<float> izquierda(mitad);
    for (int i = 0; i < mitad; i++)
        izquierda[i] = v[i];
    if (buscar(izquierda, dato))
        return true;

    // Crear subvector derecha (Costo O(n/2))
    vector<float> derecha(v.size() - mitad - 1);
    for (int i = mitad + 1, j = 0; i < v.size(); i++, j++)
        derecha[j] = v[i];
    if (buscar(derecha, dato))
        return true;

    // Revisar el elemento del medio (Costo O(1))
    return v[mitad] == dato;
}

Utilizando el Teorema Maestro, y siendo $n$ el tamaño del vector:

1. Analice el coste temporal del algoritmo en el peor caso en función de $n$.
2. Analice el coste temporal del algoritmo en el mejor caso en función de $n$.

En cada apartado, indique:

• (i) qué ecuación recursiva se obtiene para el coste temporal y cuáles son los valores de $a, b, k$ y $p$;
• (ii) a qué solución se llega aplicando el teorema a partir de esa ecuación.

Análisis Preliminar del Coste

La solución se basa en un esquema de división en cuartos, donde el trabajo no recursivo $f(n)$ es lineal ($O(n)$) debido a la creación de subvectores (copia de datos).

Consideramos que el algoritmo divide el vector en cuatro partes aproximadas:

1. [inicio, cuartoIzquierda] $\to$ llamada recursiva (tamaño $\approx n/4$).
2. [cuartoIzquierda+1, cuartoDerecha] $\to$ búsqueda lineal o trabajo no recursivo (tamaño $\approx n/2$).
3. [cuartoDerecha+1, fin] $\to$ llamada recursiva (tamaño $\approx n/4$).

a) Peor Caso

En el peor caso, el dato no se encuentra o está al final, por lo que siempre se ejecutan todas las llamadas recursivas y el trabajo no recursivo completo.

(i) Ecuación Recursiva y Parámetros

La ecuación de recurrencia es:

Para simplificar, se utiliza la forma estándar:

Identificación de los parámetros del Teorema Maestro:

• $a = 2$
• $b = 4$
• $f(n) = O(n) \implies k = 1, p = 0$

(ii) Aplicación del Teorema Maestro

Se compara $a$ con $b^k$:

Comparar $k=1$ con $\log_b a = \log_4 2$:

Dado que $1 > 1/2$, estamos en el Caso 3 del Teorema Maestro, donde $f(n)$ domina polinomialmente.

✅ Conclusión (Peor Caso):

b) Mejor Caso

En el mejor caso, el dato se encuentra en la primera posición de la primera llamada recursiva, o en el elemento central. Asumiendo que se encuentra rápidamente en la primera llamada recursiva, solo se ejecuta una llamada y el trabajo no recursivo es constante ($O(1)$).

(i) Ecuación Recursiva y Parámetros

Solo se ejecuta una llamada recursiva de tamaño $\approx n/4$ y el trabajo no recursivo es constante $O(1)$:

Identificación de los parámetros del Teorema Maestro:

• $a = 1$
• $b = 4$
• $f(n) = O(1) \implies k = 0, p = 0$

(ii) Aplicación del Teorema Maestro

Se compara $a$ con $b^k$:

• $\log_b a = \log_4 1 = 0$. Dado que $k=0$, estamos en el Caso 2 del Teorema Maestro.

La solución es $T(n) = O(n^k \log^{p+1} n)$:

✅ Conclusión (Mejor Caso):