Tema 5: Árboles AVL

La altura H(T) de un árbol binario T con subárboles izquierdo T_i y derecho T_d es:

• 0 si el árbol T está vacío y 1 + min (H(T_i), H(T_d)) en otro caso.

• 1 + min (H(T_i), H(T_d)) en cualquier caso.

• 1 + max (H(T_i), H(T_d)) en cualquier caso.

• 0 si el árbol T está vacío y 1 + max (H(T_i), H(T_d)) en otro caso.

¿Cuál es el peor árbol AVL posible de una altura dada?

I. El que tiene un menor número de nodos.

II. El que tiene todos los nodos no hoja con factor de equilibrio no nulo.

• I. sí II. sí

• I. sí II. no

• I. no II. sí

• I. no II. no

Respecto a la evitación de la degeneración de un árbol binario de búsqueda, ¿cuál de las siguientes respuestas considera verdadera?

• La reestructuración completa de un árbol binario de búsqueda requiere excesivas reorganizaciones

• Las reorganizaciones necesarias para la reestructuración completa de un árbol binario de búsqueda pueden mantenerse bajo contro

• Las reorganizaciones en un árbol AVL afectan a todo el árbol.

• Las operaciones de mantenimiento en un árbol AVL son O(n).

Determinar cuál de las siguientes afirmaciones es cierta:

I. Un árbol AVL es siempre más adecuado que un árbol binario de búsqueda.

II. Un árbol binario de búsqueda que por construcción es perfectamente balanceado es el que presenta mejor coste computacional en la búsqueda.

• I: sí, II: sí

• I: sí, II: no

• I: no, II: sí

• I: no, II: no

Si T es un árbol binario no vacío con subárboles izquierdo T_i y derecho T_d, T es AVL si y sólo si:

• Ninguna de las otras respuestas es verdadera..

• T_i y T_d son AVL

• .T_i y T_d son AVL y H(T_i) ‐ H(T_d) = ­‐1, 0, +1

• H(T_i) ‐ H(T_d) = -­1, 0, +1.

Indicar cuál de las siguientes afirmaciones es cierta cuando el número de elementos es muy elevado:

I. El coste promedio de la búsqueda en un árbol binario de búsqueda es siempre mejor que en una lista encadenada.

II. El coste promedio de la búsqueda en un árbol AVL es siempre mejor que en una lista encadenada.

• I: sí, II: sí.

• I: sí, II: no

• I: no, II: sí

• I: no, II: no

En un árbol AVL, el factor de equilibrio del nodo crítico:

• Antes de la inserción es -­1 ó +1 y después es ‐2 ó +2

• Antes de la inserción es ‐2 ó +2 y después es ‐1 ó +1

• Antes de la inserción es 0 y después es ­‐1 ó +1

• Antes de la inserción es -­1 ó +1 y después es 0.

Antes de la inserción, el nodo discriminante (hijo del crítico) de un árbol AVL debe tener un factor de equilibrio:

• +2 ó -2

• 0

• Ninguna de las otras respuestas es verdadera

• +1 ó -1

En un árbol AVL, se necesita una rotación cuando:

• Aumenta la altura del subárbol de mayor altura

• Aumenta la altura del subárbol de menor altura

• El factor de equilibrio pasa de 0 a ­‐1 ó +1

• Ninguna de las otras respuestas es verdadera

Respecto a las longitudes de los caminos de búsqueda:

• Ninguna de las otras respuestas es verdadera

• Las del AVL no exceden en más del 45% a las del árbol óptimo

• Son similares en el AVL y en el árbol óptimo

• Las del AVL superan en más de un 50% a las del árbol óptimo