Cuestión 1. Construcción con rotaciones

Insertamos 10, 20, 30, 40, 50, 25 partiendo del árbol vacío. Notación: cada nodo se anota como clave(FE), con FE = altura(izq) − altura(der) y altura de un subárbol vacío = −1, hoja = 0.

Inserción de 10 → raíz.

Inserción de 20 → a la derecha de 10.

Inserción de 30 → a la derecha de 20. Antes de rotar:

Inserción de 40 → a la derecha de 30.

Inserción de 50 → a la derecha de 40. Antes de rotar:

Inserción de 25 → BST: 25 > 20 → derecha; 25 < 40 → izquierda; 25 < 30 → izquierda de 30. Antes de rotar:

• FE(10) = 0, FE(25) = 0, FE(50) = 0 (hojas)
• FE(20) = altura(10) − altura(25) = 0 − 0 = 0
• FE(40) = altura(∅) − altura(50) = −1 − 0 = −1
• FE(30) = altura(20) − altura(40) = 1 − 1 = 0

Todos los FE ∈ {−1, 0}, árbol AVL válido.

Árbol final con factores de equilibrio:

Altura mínima. El árbol tiene altura h = 2 (contando aristas: por ejemplo 30→40→50). Es la mínima posible para 6 claves: un árbol completo de altura 2 (3 niveles) almacena hasta 2^3 − 1 = 7 ≥ 6 nodos, mientras que uno de altura 1 solo aloja 3. Comprobado: nuestro AVL alcanza la altura mínima.

Como apunte de nivel tribunal: el AVL no garantiza siempre la altura mínima absoluta, sino la cota h ≤ 1,44·log₂(n+2) (árboles de Fibonacci). En este caso concreto el resultado sí coincide con el mínimo teórico y, en general, la altura queda siempre en O(log n).

Cuestión 2. Por qué AVL y no BST

Forma del BST sin equilibrar con 10, 20, 30, 40, 50. Como cada clave es mayor que todas las anteriores, siempre se inserta como hijo derecho del último nodo. El BST degenera en una lista enlazada inclinada a la derecha:

• Altura: h = n − 1 = 4 aristas (5 niveles). En general, para n claves ordenadas, h = n − 1.
• Coste de búsqueda: buscar la clave 50 (o una inexistente mayor) recorre los n nodos → O(n). La búsqueda binaria se ha perdido por completo; el BST se comporta como una búsqueda secuencial.

Garantía O(log n) del AVL. El invariante FE ∈ {−1,0,+1} mantiene la altura acotada. Se demuestra con los números de Fibonacci: el AVL con menos nodos para una altura h tiene N(h) = N(h−1) + N(h−2) + 1 nodos (árbol de Fibonacci). De ahí se deduce:

Como búsqueda, inserción y borrado recorren un único camino raíz→hoja y solo aplican un número constante de rotaciones por nivel afectado, su coste es proporcional a la altura → O(log n) en todos los casos, frente al O(n) del peor caso del BST.

Información extra en cada nodo. Cada nodo AVL debe almacenar, además de clave e hijos, su altura (o, equivalentemente, su factor de equilibrio). Con la altura de los hijos se recalcula en O(1):

Mantener la altura/FE actualizado tras cada inserción o borrado es lo que permite detectar el desequilibrio y decidir la rotación sin recorrer el subárbol completo.

Cuestión 3. Borrado de la clave 30

Partimos del árbol final de la cuestión 1:

Paso 1 — Localizar y elegir sustituto. El nodo 30 es ahora la raíz y tiene dos hijos (el subárbol 20-10-25 y la rama 40-50). En un nodo con dos hijos se sustituye por el predecesor in-orden (máximo del subárbol izquierdo, aquí el 25) o el sucesor in-orden (mínimo del subárbol derecho). Tomamos el sucesor in-orden: el mínimo del subárbol derecho de 30 es 40 (40 no tiene hijo izquierdo). Copiamos la clave 40 en la raíz y eliminamos el nodo 40 original, reenganchando su hijo derecho (50) en su lugar.

Subárboles afectados: el subárbol derecho (la rama 40-50). Tras copiar 40 arriba, 50 pasa a colgar directamente de la nueva raíz:

Paso 2 — Recalcular alturas y FE subiendo hacia la raíz.

• FE(10) = 0, FE(25) = 0, FE(50) = 0 (hojas).
• FE(20) = altura(10) − altura(25) = 0 − 0 = 0 → equilibrado.
• FE(40) (la nueva raíz) = altura(20) − altura(50) = 1 − 0 = +1 → equilibrado.

Paso 3 — ¿Desequilibrio? No. Todos los FE quedan en {−1, 0, +1}. El borrado no provoca desequilibrio, por lo que no se requiere ninguna rotación en este caso.

Árbol resultante:

Nota sobre propagación. A diferencia de la inserción (donde una única rotación restablece todo el árbol), en el borrado una rotación puede reducir la altura del subárbol y desequilibrar a un ancestro, obligando a propagar el reequilibrado hacia la raíz (potencialmente O(log n) rotaciones). En este supuesto concreto no llega a producirse, pero el algoritmo general debe seguir comprobando el FE en cada ancestro hasta la raíz.

Cuestión 4. Esquema de la rotación simple a la derecha

La rotación simple a la derecha se aplica al caso LL (el subárbol izquierdo es el más alto y el desequilibrio viene por la izquierda del hijo izquierdo). El hijo izquierdo h sube a ocupar el lugar del nodo desequilibrado z, que baja a la derecha; el antiguo subárbol derecho de h (T2) se reengancha como subárbol izquierdo de z.

Java:

Nodo rotarDerecha(Nodo z) {
    Nodo h  = z.izq;     // hijo izquierdo, será la nueva raíz
    Nodo T2 = h.der;     // subárbol que cambia de padre

    // 1) Reasignación de punteros (orden seguro: primero "girar")
    h.der = z;           // z pasa a ser hijo derecho de h
    z.izq = T2;          // T2 pasa a ser hijo izquierdo de z

    // 2) Recalcular alturas: PRIMERO el nodo que queda abajo (z),
    //    LUEGO el que queda arriba (h), porque h depende de z.
    z.altura = 1 + Math.max(altura(z.izq), altura(z.der));
    h.altura = 1 + Math.max(altura(h.izq), altura(h.der));

    // 3) Devolver la nueva raíz del subárbol
    return h;
}

int altura(Nodo n) { return (n == null) ? -1 : n.altura; }

Punteros reasignados y orden:

1. Guardar h = z.izq y T2 = h.der antes de modificar nada (si no, se pierden las referencias).
2. h.der = z (z baja a la derecha de h).
3. z.izq = T2 (T2 cuelga de z).
4. Recalcular alturas de abajo arriba: primero z (queda como hijo) y después h (queda como nueva raíz y su altura depende de la ya actualizada de z).
5. Retornar h para que el padre re-enlace el subárbol.

El coste es O(1) (número constante de reasignaciones).

Composición de la rotación LR (en una frase): el caso LR se resuelve con dos rotaciones simples encadenadas: primero una rotación a la izquierda sobre el hijo izquierdo del nodo desequilibrado (lo transforma en un caso LL) y, a continuación, una rotación a la derecha sobre el propio nodo desequilibrado. Simétricamente, RL = rotación derecha sobre el hijo derecho + rotación izquierda sobre el nodo.

Cuestión 5. Comparación con tabla hash

(a) Complejidad de la búsqueda por clave.

• AVL: O(log n) tanto en caso medio como en el peor caso, porque la altura está acotada logarítmicamente por el invariante de equilibrio.
• Tabla hash: O(1) en el caso medio (con buena función hash y factor de carga controlado), pero O(n) en el peor caso, cuando todas las claves caen en el mismo cubo (colisiones masivas o función hash deficiente).

(b) Operaciones «gratis» del AVL. Al ser un árbol binario de búsqueda ordenado, el AVL ofrece sin coste adicional:

• Recorrido ordenado (in-orden): visita las claves de menor a mayor id en O(n), directamente.
• Consultas por rango (p. ej. «recursos con id entre 100 y 200»): O(log n + k), localizando el extremo inferior y avanzando in-orden.
• Además: mínimo / máximo (O(log n)) y predecesor / sucesor de una clave.

Una tabla hash no preserva ningún orden entre las claves: el hashing dispersa los id por los cubos sin relación con su valor, de modo que recorrer ordenado o consultar rangos obliga a leer toda la tabla y reordenar.

(c) Factor de carga. El factor de carga es:

Mide cómo de «llena» está la tabla. Al crecer λ aumenta la probabilidad de colisión y, por tanto, la longitud media de las listas de desbordamiento (en encadenamiento) o el número de sondeos (en direccionamiento abierto), degradando el O(1) ideal. Para mantener el rendimiento se realiza rehashing (se amplía m y se reubican las claves) cuando λ supera un umbral típico (≈ 0,75 en encadenamiento; menor, ≈ 0,5, en direccionamiento abierto).

Conclusión. Si el requisito principal es listar los recursos ordenados por id (y previsiblemente hacer consultas por rango), la elección correcta es el árbol AVL: ofrece el recorrido ordenado y las consultas por rango de forma nativa y eficiente, con búsqueda/inserción/borrado garantizados en O(log n) incluso en el peor caso. La tabla hash sería preferible solo si la operación dominante fuera el acceso puntual por clave exacta sin necesidad de orden ni rangos, donde su O(1) medio resulta imbatible.