← Volver a actividades
Autoevaluación

Autoevaluación: TAD Árboles Binarios y Árboles Binarios de Búsqueda (BST)

TAD Árbol: Recorridos y Árbol Binario de Búsqueda

Respondé todas las preguntas y presioná Calificar para ver tu puntaje.

1. ¿Cuál es el invariante esencial que define a un Árbol Binario de Búsqueda (BST)?
Correcto Incorrecto Sin responder

Respuesta correcta: Para cada nodo, todos los valores en su subárbol izquierdo son menores que él, y todos los de su subárbol derecho son mayores.

¿Por qué? El invariante de orden del BST establece que para cualquier nodo, toda clave en el subárbol izquierdo es menor y toda clave en el subárbol derecho es mayor.

2. ¿Qué tipo de recorrido sobre un BST visita los nodos en orden estrictamente ascendente (de menor a mayor)?
Correcto Incorrecto Sin responder

Respuesta correcta: In-Order (Inorden)

¿Por qué? El recorrido In-Order visita recursivamente: primero el subárbol izquierdo (menores), luego la raíz (nodo actual), y finalmente el subárbol derecho (mayores), produciendo la secuencia ordenada.

3. En el peor de los casos, si insertamos elementos que ya vienen ordenados (por ejemplo: 1, 2, 3, 4, 5) en un BST simple sin auto-balanceo, el árbol se degenera en una lista enlazada con complejidad de búsqueda O(N).
Correcto Incorrecto Sin responder

Respuesta correcta: Verdadero

¿Por qué? Verdadero. Al insertar elementos en orden monótono en un BST no balanceado, cada nuevo nodo se inserta siempre como hijo derecho, generando una estructura lineal de altura N y arruinando el beneficio logarítmico.

4. En un BST perfectamente balanceado con N nodos, ¿cuál es la complejidad temporal de la operación de búsqueda contiene(x)?
Correcto Incorrecto Sin responder

Respuesta correcta: O(log N)

¿Por qué? Al estar balanceado, cada comparación en un nodo descarta la mitad de los elementos restantes del árbol, reduciendo el espacio de búsqueda a la altura del árbol $h = \lfloor \log_2 N \rfloor$.

5. Para encontrar el elemento mínimo en un BST, alcanza con descender iterativa o recursivamente por los punteros izquierdo hasta alcanzar un nodo cuyo hijo izquierdo sea null.
Correcto Incorrecto Sin responder

Respuesta correcta: Verdadero

¿Por qué? Verdadero. Debido al invariante de orden, el valor más pequeño de todo el árbol o subárbol siempre reside en el nodo más a la izquierda posible.

6. ¿Para qué suele utilizarse frecuentemente el recorrido Post-Order (subárbol izquierdo, subárbol derecho, raíz)?
Correcto Incorrecto Sin responder

Respuesta correcta: Para liberar memoria, eliminar subárboles de abajo hacia arriba o evaluar expresiones matemáticas representadas en árboles de sintaxis.

¿Por qué? Post-Order procesa primero los hijos antes que el padre, lo cual es ideal cuando el cálculo del padre depende enteramente del resultado consolidado de sus descendientes (como calcular el tamaño de carpetas o evaluar operadores aritméticos).

7. En Java, para que una clase genérica pueda usarse como clave en un BST sin requerir comparadores externos, debe implementar la interfaz Comparable<T> y definir compareTo.
Correcto Incorrecto Sin responder

Respuesta correcta: Verdadero

¿Por qué? Verdadero. El método compareTo provee el orden natural necesario para decidir hacia qué rama descender durante inserciones y búsquedas.

8. ¿Cuál es la relación matemática entre el número de aristas de un árbol de N nodos y su cantidad de vértices?
Correcto Incorrecto Sin responder

Respuesta correcta: Tiene exactamente N - 1 aristas.

¿Por qué? Todo árbol (como grafo conexo y acíclico) de N nodos contiene exactamente N - 1 aristas, dado que cada nodo excepto la raíz posee exactamente un único padre.