Árboles Generales y Estructuras de Búsqueda

Representación mediante Lista de Hijos

¿Hay alguna operación claramente ineficiente en la representación de árboles generales mediante lista de hijos?
Sí, en la representación de lista de hijos, la operación de búsqueda de un nodo hermano específico puede ser ineficiente porque requiere recorrer secuencialmente toda la lista de hijos del nodo padre, lo que tiene un coste $O(n)$ en el peor caso.

Vector de Posiciones Relativas

¿En qué situaciones es conveniente utilizar un vector de posiciones relativas?
Cuando conozcamos de antemano el grado que tendrá nuestro árbol (número máximo de hijos), y además cuando este sea completo, de forma que optimicemos el espacio reservado en memoria para el árbol.

Eficiencia en Árboles B

¿Por qué interesa que los árboles B tengan poca altura?
Porque el tiempo de búsqueda es proporcional al número de niveles. Si el árbol tiene poca altura, necesitaremos menos accesos a memoria secundaria (lectura de bloques), lo que mejora mucho el rendimiento. Además, al tener más hijos por nodo se reduce la necesidad de dividir o fusionar nodos, manteniendo el árbol eficiente.

Comparativa ABB vs. AVL

¿Dado un conjunto de elementos insertados en el mismo orden en un ABB y en un AVL, daría como resultado árboles de la misma altura?
No necesariamente. Un ABB (Árbol Binario de Búsqueda) no garantiza balanceo, por lo que puede generar un árbol desbalanceado con una altura mayor. En cambio, un AVL está diseñado para estar balanceado y mantener la altura logarítmica.

Un AVL es un ABB, pero el recíproco no es cierto. ¿Estás de acuerdo?
Sí, un AVL es un tipo específico de ABB que garantiza balanceo en cada inserción o eliminación. Un ABB, sin embargo, no tiene este requisito, por lo que puede estar desbalanceado.

¿Por qué se exige un equilibrio perfecto en los AVL?
Afirmación falsa, ya que en los AVL no se exige un equilibrio perfecto; el factor de desequilibrio puede ser de 1, 0 o -1. Por un lado, no se exige perfecto, y por otro lado, su estructura es para garantizar las búsquedas en orden logarítmico.

Árboles Terciarios

¿Tiene sentido el concepto de Árbol terciario de búsqueda?
Sí. La generalización de los ABB para árboles generales son los árboles B. Un árbol terciario de búsqueda sería un árbol B de orden m=3 (siendo m el número máximo de hijos de cada nodo) y k=2 (siendo k el número de elementos que contiene como máximo cada uno de los nodos).

Colas con Prioridad y APO (Heaps)

Costes en APO

¿Puede tener coste $O(n)$ la eliminación de una raíz en un APO?
No. Un APO (Árbol Parcialmente Ordenado) por definición es un árbol completo parcialmente ordenado. Por tanto, cualquiera de las dos operaciones toma un tiempo $O(\log_2 n)$, puesto que en el árbol ningún camino tiene más de $1 + \log_2 n$ nodos, ya que los elementos flotan y hunden respectivamente.

Orden de Inserción

Comentar la siguiente afirmación: el orden de inserción de elementos en un APO determina el grado de desequilibrio.
Falsa, ya que es un árbol completo y un árbol completo siempre está equilibrado; el orden de inserción no afecta al equilibrio de la estructura.

Comparativa: Lista Ordenada vs. APO

Explicar las ventajas e inconvenientes que plantean las colas con prioridad representadas como una lista ordenada por prioridad frente a un APO.

• Lista ordenada por prioridad:
  • Ventaja: La operación de extracción del elemento de mayor prioridad es inmediata ($O(1)$), ya que siempre está en la primera posición.
  • Inconveniente: La operación de inserción es costosa ($O(n)$), porque hay que recorrer la lista hasta encontrar la posición adecuada.
• APO (Árbol Parcialmente Ordenado / Heap):
  • Ventaja: Las operaciones de inserción y extracción tienen coste $O(\log n)$, lo que supone un mejor equilibrio en eficiencia.
  • Inconveniente: La implementación es algo más compleja y no se dispone directamente de los elementos en orden, solo se garantiza la propiedad de orden parcial.

Algoritmos de Grafos y TAD Partición

Algoritmo de Kruskal y Ciclos

¿Cómo resuelve el algoritmo de Kruskal la aparición de ciclos en la solución?
Kruskal utiliza el TAD Partición con técnicas como unión por rango y compresión de caminos para mantener un registro de los componentes conectados. Esto asegura que, al añadir una arista, se verifica si los extremos están en la misma componente. Si lo están, formarían un ciclo y la arista no se añade.

Estrategias de Unión y Compresión

¿Qué estrategia de unión (por altura o por tamaño) combina mejor con la técnica de compresión de caminos en el TAD partición?
La unión por tamaño combina mejor con la compresión de caminos, ya que asegura que los árboles más pequeños se unen a los más grandes, lo que, junto con la compresión de caminos, optimiza las búsquedas y reduce la altura promedio.

¿Qué beneficio aporta la compresión de caminos en la implementación del TAD partición?
En la implementación del TAD Partición mediante bosques de árboles y mediante unión por tamaño o por altura, la compresión de caminos se utiliza para poder acercarnos a órdenes constantes en la función encontrar. Esto lo conseguimos haciendo que los nodos por los que pasamos sean hijos directos del nodo raíz, de esta manera la función encontrar se acerca a un coste 1, aunque no se garantiza de forma absoluta.

Kruskal vs. Prim

¿Es necesario ordenar las aristas en el algoritmo de Kruskal?
Sí, ordenar las aristas por peso es esencial para garantizar que se consideren primero las más ligeras, lo que es fundamental para construir un árbol de expansión mínima.

¿Es necesario ordenar las aristas en el algoritmo de Prim?
Prim NO necesita ordenar todas las aristas, solo elegir la mínima en cada paso.

Los algoritmos de Prim y Kruskal resuelven el mismo problema y por tanto devuelven el mismo resultado para un grafo dado.
Ambos resuelven el mismo problema: encontrar un árbol generador de coste mínimo (MST), pero no tienen por qué devolver el mismo resultado. El resultado depende de si existen varias aristas con el mismo peso; en ese caso, podrían existir varias soluciones diferentes. Si no existen aristas con pesos iguales, la solución de Prim y Kruskal sería la misma.

Nodos Visitados y Subgrafos

Explica por qué es necesario marcar los nodos visitados en un grafo.
Existen dos razones: una es para no procesar un nodo más de una vez (especialmente si el grafo tiene ciclos) y la segunda es para poder procesarlos todos si existe más de una componente conexa en el grafo.

Todos los subgrafos de $n-1$ aristas de un grafo de $n$ nodos, ¿son árboles generadores? ¿sólo los subgrafos de coste mínimo?
No. Un subgrafo con $n-1$ aristas no es necesariamente un árbol generador: además de tener $n-1$ aristas, debe ser conexo y acíclico. Dentro de los que sí son árboles generadores, aquellos con coste mínimo reciben el nombre de árboles generadores mínimos (MST).

Tablas Hash

Conceptos Fundamentales

¿Qué es una función hash y cuáles son sus propiedades deseables?
Una función hash transforma una clave de cualquier tipo en un índice entero dentro del rango de la tabla. Sus propiedades deseables son: ser determinista (misma clave → mismo índice), distribuir uniformemente las claves para minimizar colisiones y ser eficiente de calcular.

¿Qué es una colisión en una tabla hash y por qué se produce?
Una colisión ocurre cuando dos claves distintas producen el mismo índice. Se produce inevitablemente cuando el número de claves posibles es mayor que el tamaño de la tabla. Es imposible eliminarlas completamente, solo minimizarlas con una buena función hash.

Resolución de Colisiones

Explica la resolución de colisiones por encadenamiento (hashing abierto).
Cada celda de la tabla contiene una lista enlazada de todos los elementos cuya clave produce ese índice. Ventaja: la tabla nunca se llena. Inconveniente: coste adicional de memoria y acceso indirecto por punteros.

Explica la resolución de colisiones por direccionamiento abierto (hashing cerrado).
Todos los elementos se almacenan dentro de la propia tabla. Cuando hay colisión se busca otra celda libre mediante una función de exploración (lineal, cuadrática o doble hashing). Inconveniente: la tabla puede llenarse y el rendimiento degrada con el factor de carga.

Factor de Carga y Rendimiento

¿Qué es el factor de carga (λ) de una tabla hash y qué valor se recomienda?
El factor de carga es λ = n/M (elementos / tamaño). Con hashing abierto se recomienda λ < 1 (idealmente < 0.75). Con hashing cerrado, λ no puede superar 1 al usar direccionamiento abierto, y cuanto mayor sea, peor será el rendimiento en las búsquedas.

¿En qué condiciones se da el caso peor y mejor de la operación de búsqueda en el hashing cerrado?

• Peor caso: Aparece cuando el factor de carga es alto y se forman secuencias largas de colisiones (clustering). La búsqueda puede requerir recorrer casi toda la tabla, con coste $O(n)$.
• Mejor caso: Se da cuando no hay colisión y la clave se encuentra en la posición exacta. Suele ocurrir con factores de carga bajos y buena dispersión. Coste: $O(1)$.

Técnicas de Exploración

¿Qué problema tiene la exploración lineal y cómo lo soluciona la exploración cuadrática?
La exploración lineal produce agrupamiento primario: bloques de celdas ocupadas que degradan el rendimiento. La exploración cuadrática usa un incremento i² para saltar posiciones, reduciendo el agrupamiento primario, aunque puede generar agrupamiento secundario.

¿En qué consiste el doble hashing y qué ventaja tiene?
Usa dos funciones hash: h(k, i) = (h1(k) + i·h2(k)) mod M. La ventaja es que el incremento depende de la clave, eliminando tanto el agrupamiento primario como el secundario.

¿Por qué se recomienda que el tamaño M de la tabla hash sea un número primo?
Un M primo garantiza una mejor distribución de las claves y evita concentraciones en subconjuntos de celdas. En doble hashing, asegura que la exploración recorra todas las celdas antes de repetirse.

Eliminación y Costes Medios

¿Cómo se realiza la operación de eliminación en hashing con direccionamiento abierto y qué problema plantea?
No se puede dejar la celda vacía porque rompería las cadenas de exploración. La solución es marcar la celda con un valor especial «eliminado» (tumba/deleted), que se salta en las búsquedas pero se puede reutilizar en las inserciones.

Compara el coste medio de búsqueda exitosa y fallida en una tabla hash con encadenamiento.
El coste medio de búsqueda exitosa es aproximadamente 1 + λ/2 comparaciones, y el de búsqueda fallida es λ (longitud media de la lista). Si λ es pequeño y constante, ambas operaciones son $O(1)$ en media.

Ejercicios Prácticos

Inserción en Árbol B

Insertar en un árbol B el elemento 13, seguido del 39.
Procedimiento de inserción y división de nodos:

• 1º: Hacemos división 9 | 10 | 11, 13, 15 y promocionamos el 11. Luego realizaremos división 7 | 11, 18, 32, 50 y promocionamos el 18.
• 2º: Hacemos división 34 | 38 | 39, 45 | 49 y promocionamos el 39.