TAD Árbol: Recorridos y Árbol Binario de Búsqueda
Respondé todas las preguntas y presioná Calificar para ver tu puntaje.
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.
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.
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.
contiene(x)
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$.
izquierdo
null
¿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.
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).
Comparable<T>
compareTo
¿Por qué? Verdadero. El método compareTo provee el orden natural necesario para decidir hacia qué rama descender durante inserciones y búsquedas.
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.
Puntaje: