Árboles

Preguntas Frecuentes sobre Árboles

1. ¿Por qué surgen los árboles?

Los árboles surgen para crear jerarquías y permitir búsquedas eficientes en orden logarítmico O(log n).

2. ¿En qué situaciones es conveniente utilizar un vector de posiciones relativas?

Un vector de posiciones relativas es conveniente cuando el árbol tiene muchos nodos y un nivel bajo, minimizando la memoria desperdiciada y maximizando la eficiencia espacial.

3. ¿Cuántos tipos de recorrido de árboles en anchura existen?

Existe un único tipo de recorrido en anchura, que comienza en la raíz y visita cada nivel de izquierda a derecha. Hay dos implementaciones: iterativa y recursiva.

4. ¿Cuántos tipos de recorridos de árboles en profundidad existen?

Existen tres tipos de recorridos en profundidad:

  • Preorden: Raíz -> Hijo Izquierdo -> Hijo Derecho (ABin) / Hermanos (AGen)
  • Inorden: Hijo Izquierdo -> Raíz -> Hijo Derecho (ABin) / Hermanos (AGen)
  • Postorden: Hijo Izquierdo -> Hijo Derecho (ABin) / Hermanos (AGen) -> Raíz

5. ¿Qué condiciones deben cumplir los elementos de un árbol para realizar búsquedas con un coste menor que O(n)?

El árbol debe estar equilibrado y sus elementos ordenados para lograr un coste de búsqueda O(log n).

6. ¿Puede reconstruirse un árbol unívocamente dado su inorden?

No, se necesita el inorden para la relación entre subárboles y el preorden o postorden para ubicar la raíz.

7. ¿Por qué las operaciones de Insertar y Eliminar son de O(1) en la representación vectorial o de celdas enlazadas de árboles binarios?

Se debe a la variable numNodos que indica la posición del último nodo, permitiendo acceso directo sin recorrido. En la eliminación, se intercambia el último nodo con el nodo a eliminar.

8. ¿La eliminación de nodos de un árbol binario se puede conseguir con O(1) cuando se utiliza una representación vectorial con índice al padre, hijo izquierdo e hijo derecho?

Sí, mediante la técnica de compactación, intercambiando el nodo a eliminar con el último nodo insertado.

9. Ventajas de la representación de árboles binarios con celdas enlazadas frente a matrices.

Las celdas enlazadas ofrecen:

  • Eficiencia espacial: Solo se reserva memoria para los nodos existentes.
  • Eficiencia temporal: Inserción, eliminación y búsqueda en O(1).

10. ¿Puede construirse de forma única un árbol binario dado, conociendo su preorden y el peso de cada nodo (número de nodos descendientes suyos)?

No, el peso solo indica la cantidad de hijos, no su posición como izquierdo o derecho.

11. ¿Tiene sentido el concepto de árbol terciario de búsqueda?

Sí, como en los árboles B con m=3 y k=2, que almacenan varios elementos en un nodo, reduciendo el acceso a memoria secundaria y el tiempo de búsqueda.

12. Sean A y B dos árboles binarios diferentes, indique si puede ocurrir simultáneamente que: Pre(A) = Post(B) y Pre(B) = Post(A).

Sí, si los árboles son vacíos o si tienen la misma cantidad de elementos y la misma secuencia en preorden y postorden, pero con ramificaciones diferentes.

13. Las operaciones del TAD Árbol Binario permiten insertar y eliminar hojas pero no nodos internos.

Verdadero, la inserción solo se permite en nodos sin hijos y la eliminación solo en hojas.

14. Para destruir un Árbol Binario completo implementado mediante una representación vectorial, no es necesario eliminar los nodos uno a uno en postorden, esto solo se haría si se trata de un subárbol del mismo.

Falso, se deben eliminar los nodos uno a uno en postorden, ya que la precondición para eliminar un nodo es que sus hijos ya hayan sido eliminados.

15. La eficiencia espacial de la representación de un Árbol Binario mediante un vector de posiciones relativas será mejor cuantos menos nodos falten en el nivel inferior.

Verdadero, la eficiencia espacial es máxima cuando el árbol está lleno, sin nodos nulos.

16. La función contarNodos de un Árbol Binario siempre es de O(n).

Falso, en la representación vectorial es O(1) gracias a la variable numNodos.

17. ¿Por qué no se puede implementar un árbol general con un vector de posiciones relativas?

Porque se desconoce el grado (número máximo de hijos) y la posición relativa de los hijos depende del grado.

18. ¿Se podría usar las listas doblemente enlazadas en los árboles generales mediante listas de hijos?

Sí, pero no en nuestra implementación del TAD, ya que no se puede acceder al hermano izquierdo de un nodo.

19. ¿Puede determinarse un árbol general a partir del inorden y postorden?

No, se necesitan los tres recorridos (preorden, inorden y postorden) para conocer la estructura completa del árbol.

20. ¿Por qué interesa que los árboles B tengan poca altura?

Para minimizar los accesos a memoria secundaria y el tiempo de búsqueda.

21. Dado que interesa reducir al máximo la altura de un árbol B, ¿por qué no aumentamos “indefinidamente” el número de hijos del árbol?

Porque se incrementaría el tiempo de búsqueda, pudiendo llegar a O(n). El número de hijos debe ser equilibrado.

22. ¿Existe alguna operación claramente ineficiente en los árboles generales representados mediante listas de hijos?

La búsqueda de un nodo puede ser ineficiente, ya que requiere recorrer la lista de hermanos.

23. Las operaciones del TAD Árbol General no permiten insertar y eliminar nodos internos, solo nodos hoja.

Falso, se pueden insertar nodos como hijos izquierdos o hermanos derechos, independientemente de si tienen hijos o hermanos.

24. Para reconstruir un Árbol General solo necesitamos su recorrido en inorden y en postorden o preorden, pero no hace falta el grado del árbol ya que cada nodo puede tener un grado diferente.

Falso, se necesitan los tres recorridos para conocer la estructura completa del árbol.

25. La representación del TAD Árbol General mediante listas de hijos es más eficiente en espacio cuanto más bajo es el árbol para un número determinado de nodos.

Verdadero, un árbol más bajo (menos profundo) requiere menos listas y, por lo tanto, es más eficiente en espacio.

26. Se define el desequilibrio de un Árbol General como la máxima diferencia entre las alturas de los subárboles más bajo y más alto de cada nivel. Esta definición y la diferencia de longitudes entre la rama más larga y más corta de dicho árbol son equivalentes.

Falso, la diferencia de longitudes entre la rama más larga y más corta solo considera el subárbol general, mientras que el desequilibrio considera todos los subárboles.

27. La función para calcular la profundidad de un Árbol General es similar a la del Árbol Binario y del mismo coste O(log n).

Falso, el coste es O(n) en ambos casos, ya que se visitan todos los nodos al menos una vez.

28. ¿Qué consiguen los árboles binarios de búsqueda (ABB)?

Permiten búsquedas en O(log n) en el caso promedio (árbol equilibrado).

29. ¿Es siempre la eliminación de elementos en un ABB de orden mayor que O(n)?

No, depende del equilibrio del árbol. En el caso promedio (equilibrado) es O(log n), en el peor caso O(n).

30. ¿Qué condiciones debe cumplir un ABB para que la búsqueda sea menor que O(n)?

El ABB debe estar equilibrado.

31. Al insertar en un Árbol B, si el nuevo elemento no cabe en el nodo que le correspondería, se divide el nodo en dos y se promociona un elemento al nodo padre, y en este caso, se permite que exista algún nodo con un solo elemento, teniendo en cuenta el mínimo permitido según el orden del árbol.

Verdadero, un nodo puede contener un solo elemento después de una promoción.

32. Al insertar en un árbol B, si el nuevo elemento no cabe en el nodo que le correspondería, se divide el nodo en dos y se promociona la mediana al nodo padre. No se permite que existan nodos con menos elementos de la mitad (por defecto) de la capacidad de un nodo.

Falso, se promociona el mayor de los menores o el menor de los mayores, no la mediana.

33. Supongamos un ABB con el elemento x en una hoja cuyo padre tiene el valor y. Entonces, y es el menor elemento mayor que x o bien, y es el mayor elemento menor que x.

Verdadero, si x es hijo izquierdo de y, y es el menor elemento mayor que x. Si x es hijo derecho de y, y es el mayor elemento menor que x.

34. Para conseguir que la anchura del árbol B sea menor, me interesa crear nodos con el mayor tamaño posible.

Falso, a mayor tamaño de nodo, mayor número de claves y, por ende, mayor anchura y altura.

35. La propiedad de búsqueda de un ABB permite encontrar un elemento en un tiempo de O(n) en el caso peor.

Verdadero.

36. La eliminación de elemento en un ABB puede llegar a tener un coste O(n).

Verdadero, en el peor caso (árbol desequilibrado).

37. El recorrido en preorden de un ABB determina unívocamente el ABB del que procede.

Verdadero si el árbol está equilibrado. Si no lo está, se necesita el inorden para determinar la posición de los nodos como hijos izquierdos o derechos.

38. Los nuevos elementos de un árbol B se insertan en las hojas y, si es necesario, se reorganiza el árbol.

Verdadero, si el nodo hoja no tiene espacio, se promociona un elemento al padre y se divide el nodo.

39. En un árbol B de orden m, todos los nodos contienen un mínimo de [m-1/2] claves, y un máximo de m-1.

Verdadero.

40. ¿En qué condiciones puede un árbol ser un APO y ABB simultáneamente?

Cuando está vacío o solo contiene un nodo (la raíz).

41. ¿Influye el orden de inserción de los elementos para el desequilibrio de un APO?

No, los elementos se insertan al final y se flotan para mantener el equilibrio.

42. ¿Influye el número de elementos de un APO a su desequilibrio?

Sí, la cantidad de elementos puede afectar el equilibrio del árbol.

43. ¿Puede reconstruirse un APO de forma unívoca dado su recorrido en preorden?

Verdadero, el preorden permite obtener el número de nodos y la altura, lo que permite reconstruir el APO.

44. ¿Es posible obtener coste O(n) en la eliminación de un nodo cualquiera de un APO?

Falso, la eliminación es de O(log n) en el caso promedio.

45. ¿Es posible obtener coste O(n) en la inserción/eliminación de la raíz de un APO?

Falso, la inserción y eliminación de la raíz son de O(log n) en el caso promedio.

46. Los elementos de un APO se obtienen en orden mediante la extracción sucesiva de estos.

Verdadero, la extracción sucesiva de la cima (elemento mínimo) permite obtener los elementos en orden ascendente.

47. Todo APO min-max cumple estrictamente con las condiciones que hemos definido para un APO, pero no ocurre al contrario.

Falso, un APO min-max tiene niveles min (nodo menor que sus hijos) y niveles max (nodo mayor que sus hijos), lo que no cumple la condición de un APO regular.

48. La propiedad de orden parcial de un APO no implica que siempre va a estar equilibrado.

Verdadero, el equilibrio depende del número de elementos, no de la propiedad de orden parcial.

49. Si un Árbol es un APO, tiene un desequilibrio en valor absoluto menor o igual que 1, pero no todo desequilibrio menor o igual que 1 indica que sea un APO.

Verdadero, un APO siempre tiene un desequilibrio menor o igual que 1, pero no todos los árboles con ese desequilibrio son APOs, ya que deben cumplir la propiedad de orden parcial.

50. El recorrido en anchura de un APO no proporciona el acceso en orden a los elementos almacenados. O se pueden obtener los elementos en orden de un APO.

Verdadero, el recorrido en anchura no garantiza el orden de los elementos.

51. ¿Qué aportan los AVL frente a los ABB?

Los AVL garantizan una altura de O(log n), asegurando un coste logarítmico para inserción, eliminación y búsqueda en el peor caso.

52. Explica por qué se exige un equilibrio perfecto en los AVL.

El equilibrio perfecto (factor de equilibrio de -1, 0 o 1) garantiza un coste logarítmico para las operaciones de búsqueda en el peor caso.

53. ¿Influye el orden de inserción de los datos en la altura de un AVL?

No, el AVL se autoequilibra para mantener su propiedad de equilibrio perfecto.

54. El factor de equilibrio en los AVL.

El factor de equilibrio es la diferencia entre la altura del subárbol izquierdo y la altura del subárbol derecho. Un factor de equilibrio de -1, 0 o 1 indica un árbol equilibrado.

55. El cálculo de la altura de un árbol es de O(n), excepto para los AVL, en cuyo caso el orden del cálculo de la altura es logarítmico.

Verdadero.

56. La propiedad de equilibrio de un AVL permite encontrar un elemento en un tiempo de O(log n) en el caso peor.

Verdadero.

57. La inserción en el mismo orden de un conjunto de elementos en un ABB y un AVL no tendría por qué dar como resultado árboles de la misma altura.

Verdadero, el AVL se autoequilibra, lo que puede resultar en una altura diferente a la de un ABB.

58. Un AVL es un ABB y el recíproco no es cierto.

Verdadero, un AVL es un ABB con la propiedad de equilibrio perfecto, pero no todos los ABB son AVL.

59. Es cierto que todos los AVL son ABB y es cierto que algunos ABB no sean AVL

Verdadero.

60. La propiedad de equilibrio de un AVL no implica que su altura sea la mínima posible.

Falso, la propiedad de equilibrio de un AVL implica una altura mínima para el número de nodos.

61. En un AVL cada nodo tiene un factor de equilibrio de 1, 0 o -1 y ello significa que todas las hojas se van a encontrar en el último nivel o en el penúltimo.

Falso, las hojas pueden estar en cualquier nivel siempre que se cumpla el factor de equilibrio.

62. La propiedad de búsqueda de un ABB permite encontrar un elemento en un tiempo de O(n) en el caso peor.

Verdadero.

63. La condición de equilibrio no perfecto de un AVL asegura que la inserción de un elemento se pueda hacer a un coste de O(log n) en el peor caso.

Falso, es la condición de equilibrio perfecto la que asegura un coste logarítmico para la inserción.

Partición

Preguntas Frecuentes sobre Partición

64. Dado el TAD Partición, decir qué combinación entre estructuras de datos y estrategia es necesaria para que tanto la búsqueda como la unión sean de O(1).

No existe una combinación que permita ambas operaciones en O(1). Un vector de pertenencia ofrece búsqueda en O(1) y unión en O(n), mientras que un bosque de árboles con unión por altura ofrece búsqueda en O(log n) y unión en O(1).

65. ¿Qué beneficio aporta la compresión de caminos en la implementación del TAD Partición?

Permite acercarse a un coste constante para la operación de búsqueda.

66. En el TAD Partición, ¿es posible emplear la unión en altura y la compresión de caminos a la vez?

Sí, es posible y recomendable.

67. ¿Qué se consigue con la técnica de unión por tamaño? ¿y con la técnica de unión por altura?

Ambas técnicas buscan controlar la altura del árbol resultante para optimizar la operación de búsqueda (encontrar).

68. ¿Existe una estructura de datos que permita ejecutar simultáneamente las operaciones de unión y encontrar en tiempo constante?

No, pero la combinación de bosques de árboles con unión por altura y compresión de caminos se acerca a un coste constante para ambas operaciones.

Grafos

Preguntas Frecuentes sobre Grafos

69. ¿Por qué surgen los grafos?

Surgen para representar relaciones entre nodos que no son secuenciales (como en las listas) ni jerárquicas (como en los árboles).

70. Explica las razones por las que no es necesario marcar los nodos visitados al realizar el recorrido de un grafo.

Falso, es necesario marcar los nodos visitados para evitar ciclos y recorridos infinitos.

71. Comente la siguiente afirmación: “Prim y Kruskal resuelven el mismo problema y dan la misma solución”.

Resuelven el mismo problema (árbol de expansión mínimo), pero no siempre dan la misma solución debido a sus diferentes enfoques y la posibilidad de aristas con el mismo coste.

72. ¿Por qué el algoritmo de Kruskal asegura que no se producen ciclos?

Utiliza una partición para evitar la unión de nodos ya conectados, previniendo la formación de ciclos.

73. ¿Es necesario ordenar las aristas en el algoritmo de Kruskal?

Sí, para seleccionar la arista de menor coste en cada iteración.

74. ¿Cuál es la condición que debe cumplir un grafo no dirigido para que Kruskal obtenga un resultado?

Debe ser conexo y ponderado.

75. ¿Por qué Kruskal no devuelve un grafo?

En nuestra implementación, Kruskal devuelve un grafo que representa el árbol de expansión mínimo. Teóricamente, devuelve un grafo conexo, ponderado y acíclico.

76. ¿Qué pasaría si Prim y Kruskal operaran sobre un grafo dirigido?

No funcionarían correctamente, ya que están diseñados para grafos no dirigidos.

77. Dado el algoritmo de Kruskal implementado mediante el TAD Partición, ¿son los mismos árboles los de la partición y los del algoritmo?

No necesariamente, la estructura del árbol en la partición depende del orden de inserción de las aristas.

78. ¿En la representación mediante bosques de árboles con unión por altura, por qué las raíces de los árboles se representan con números negativos?

Para indicar la altura del árbol, que en la raíz es 0 y se representa con un número negativo.

79. Diferencias y similitudes entre Prim y Kruskal.

Ambos generan un árbol de expansión mínimo, pero con enfoques diferentes. Prim parte de un nodo y Kruskal de un grafo vacío. Prim es O(n²) y Kruskal O(a log n).

80. ¿Qué ventajas e inconvenientes plantea el uso de matrices de adyacencia y costes para la representación de grafos?

Ventajas: Eficiencia en la comprobación de adyacencia. Inconvenientes: Desperdicio de memoria en grafos no completos y dificultad para añadir o eliminar vértices si la matriz no es dinámica.

81. ¿Qué ventajas e inconvenientes plantea el uso de listas de adyacencia para la representación de grafos?

Ventajas: Eficiencia en el uso de memoria y facilidad para añadir o eliminar vértices. Inconvenientes: Menor eficiencia para determinar la adyacencia entre vértices.

82. ¿Existe alguna estructura para la representación de grafos que permita añadir y suprimir vértices?

Sí, las listas de adyacencia. Las matrices y vectores también lo permiten si son dinámicas.

83. ¿Por qué no se permiten los costes negativos en Floyd?

Los costes negativos pueden generar ciclos negativos, lo que impediría la terminación del algoritmo.

84. El algoritmo de Dijkstra, ¿funciona correctamente con valores negativos?

No, Dijkstra no funciona con costes negativos, ya que se basa en la selección del nodo con menor coste en cada iteración.

85. ¿Por qué se coloca infinito en la diagonal principal de la matriz de costes en el algoritmo de Floyd?

Para evitar que el coste de ir de un nodo a sí mismo (que es 0) se considere en el cálculo del camino mínimo.