Actividades

La mejor forma de entender las estructuras complejas es trabajando con ellas. En esta sección presentamos algunas actividades que le permitirán poner en práctica los conocimientos adquiridos y verificar si los entendió correctamente. Realice los ejercicios tantas veces como lo desee y vuelva a los temas que considere necesario reforzar.

En las actividades de esta sección se utilizarán las siguientes abreviaturas y convenciones:

RSD ( K ) : Rotación Simple Derecha sobre el nodo con clave K.
RSI ( K ) : Rotación Simple Izquierda sobre el nodo con clave K.
RDD ( K ) : Rotación Doble Derecha sobre el nodo con clave K.
RDI ( K ) : Rotación Doble Izquierda sobre el nodo con clave K.

Tenga en cuenta que si al insertar un elemento no se produce desbalanceo, se anota sólo el valor insertado. Ejemplo: 140. Si se produce un desbalanceo, se anota el valor insertado y además, qué rotación se aplicó y sobre qué nodo. Ejemplo: 150 y RSD (80)

Seleccione la respuesta correcta

Pregunta

1.- El tiempo de ejecución correspondiente a insertar un valor en un árbol AVL con n elementos es SIEMPRE:

Respuestas

O ( n )

O ( n log (n) )

O ( log (n) )

O ( n2 )

Retroalimentación

Pregunta

2.- Se ha insertado el valor 67 al siguiente árbol AVL. ¿Qué rotación debe aplicarse para rebalancearlo?

arbol-insertar

Respuestas

RSD ( 66 )

RDD ( 66 )

RSI ( 80 )

RSI ( 70 )

Retroalimentación

Pregunta

3.- ¿Cuál de las siguientes opciones indica qué sucedió en el árbol AVL en cada paso de la inserción de las claves 140, 125, 150, 20, y 15 ?

arbol

Sugerencia

Realice las inserciones indicadas y verifique con cuál de las opciones coincide.

Respuestas

140 , 125 , 150 y RSD (80), 20 , 15 y RSI (30)

140 , 125, 150 y RSD (120), 20, 15 y RSI (30)

140, 125, 150 y RSD (130), 20, 15 y RSI (30)

Retroalimentación

Utilice la aplicación de construcción de árboles AVL ubicada en esta sección

Pregunta

Insertar la siguiente secuencia creciente de valores: 4, 7, 10, 12, 20, 30.

1.- ¿Cuántas rotaciones se realizaron?

Respuestas

Retroalimentación

Pregunta

2.- ¿ Qué tipo de rotaciones se aplicaron ?

Respuestas

RSI

RDI

RSD

RDD

Retroalimentación