Preguntas sobre Árboles AVL y Binarios

Si en el árbol AVL equilibrado de la figura izquierda se practica una extracción en el subárbol derecho del nodo A y una rotación simple izquierda para restablecer el equilibrio, ¿qué característica relevante destacaría en el árbol AVL reequilibrado frente al AVL equilibrado antes de la extracción?

• La altura del árbol reequilibrado ha disminuido respecto a la altura del árbol equilibrado antes de la extracción y por tanto se puede propagar hacia la raíz el desequilibrio.

• Los factores de equilibrio de los nodos A y B en el árbol reequilibrado son distintos de los factores de equilibrio de los nodos A y B en el árbol equilibrado antes de la extracción.

• La suma de los factores de equilibrio de los nodos A y B en el árbol reequilibrado es menor que la suma de los factores de equilibrio de los nodos A y B en el árbol equilibrado antes de la extracción.

• La altura del árbol reequilibrado ha disminuido respecto a la altura del árbol equilibrado antes de la extracción aunque bajo ninguna circunstancia se puede propagar hacia la raíz el desequilibrio.

Respecto a los árboles binarios, ¿qué respuesta considera verdadera?

• Cada nodo almacena: La información propia, la de sus predecesores y uno dos o tres enlaces que referencian a sus hijos.

• Cada nodo almacena: La información propia y uno dos o tres enlaces que referencian a sus hijos.

• La implementación más común para los árboles binarios es una estructura encadenada en memoria externa.

• La implementación más común para los árboles binarios es una estructura encadenada en memoria dinámica.

En un árbol Rojo-Negro, los hijos de un nodo negro deben ser...

• de color rojo o negro.

• de color negro.

• de color rojo.

Al recorrer en inorden el árbol de la figura, ¿en qué secuencia se tratan los nodos?

• P, D, A, G, E, H, L, J, R.

• A, E, H, G, J, L, D, R, P.

• A, D, E, G, H, J, L, P, R.

• P, D, R, A, G, L, E, H, J.

Respecto de los recorridos en un contenedor, ¿qué respuesta considera verdadera?

• En un árbol se hace según la relación predecesor/sucesor que se establece entre parejas de nodos por lo que sólo hay una línea posible de recorrido.

• En una estructura lineal se hace según su ordenación natural de primero a último, según la relación de sucesión.

• En una estructura lineal se hace según la relación predecesor/(sucesor derecho, sucesor izquierdo) por lo que hay más de una línea posible de recorrido.

• En un árbol se hace según la relación padre/hijo que se establece entre parejas de nodos por lo que sólo hay una línea posible de recorrido.

En un árbol binario, ¿qué respuesta considera verdadera?

• Un árbol binario es un conjunto finito de m nodos (m≥0), tal que: Si m=0, el árbol está vacío. Si m>0 entonces existe más de un nodo raíz. El resto de los nodos se reparten entre dos árboles binarios.

• Si se restringe a dos el grado máximo de un nodo, surge el árbol binario.

¿Qué encuentra significativamente diferente entre el tratamiento de los desequilibrios durante la inserción y la extracción?

• En la inserción nunca se produce propagación y en la extracción sí se puede producir.

• Nada, tanto en la inserción como en la extracción siempre se produce propagación.

• En la inserción siempre se produce propagación y en la extracción sólo con cierta frecuencia.

• Ninguna de las otras respuestas es verdadera.

En el esquema donde un árbol binario resulta equivalente a uno no binario, ¿qué respuesta considera verdadera?

• A cada nodo del árbol no binario le corresponde un nodo del binario, pero no a la inversa.

• Puede ser extendido fácilmente para encontrar la forma binaria equivalente de un bosque. Basta considerar los hijos izquierdos de las raíces de los distintos árboles como hermanos.

• Puede ser extendido fácilmente para encontrar la forma binaria equivalente de un bosque. Basta considerar los hijos derechos de las raíces de los distintos árboles como hermanos.

• Puede ser extendido fácilmente para encontrar la forma binaria equivalente de un bosque. Basta considerar las raíces de los distintos árboles como hermanas.

El árbol que se muestra en las figuras no es un árbol AVL por tener un nodo con factor de equilibrio no permitido, ¿qué figura muestra marcado con x el nodo desequilibrado?

• B.

• D.

• C.

• A.

Respecto a la extracción en los árboles binarios de búsqueda como contenedores, ¿qué respuesta considera verdadera?

• Si el nodo a extraer tuviera los dos subárboles vacíos, basta con que el nodo pasara a ocupar el lugar del nodo raíz.

• Cuando ninguno de los subárboles del nodo a extraer esté vacío lo más adecuado es sustituir el valor del nodo a extraer por el valor más lejano y así alterar el árbol lo menos posible.

• Si el nodo a extraer tuviera los dos subárboles no vacíos, basta con que los hijos pasaran a ocupar el lugar de su padre.

• Si el nodo a extraer tuviera uno de sus hijos vacío, basta con que el otro hijo pase a ocupar el lugar de su padre.