Universidad Carlos III de Madrid

Ingeniería de Telecomunicación

Enero-Mayo 2010 / January-May 2010

Árboles

Lecture Section Sesión 3 (teoría): Árboles (II)

Slide Section Transparencias

pdf

Readings Section Lecturas

Homework Section Actividades para casa

Repaso

Repasa la materia de esta clase y lee los textos recomendados.

Ejercicio

Implementar el algoritmo de inserción en árboles binarios de búsqueda.

Cuestión

Si se crean dos árboles de búsqueda binarios, arbol1 y arbol2, insertando mediante el método programado previamente 10.000 objetos Integer con valores de 1 a 10.000:

  • arbol1: invocando al método de inserción con los valores en orden secuencial, de menor a mayor

  • arbol2: invocando al método de inserción con los valores en orden aleatorio

¿En general, cuál de los dos árboles será más eficiente para buscar un elemento cualquiera?

Ejercicio

Implementar el algoritmo de eliminación en un montículo binario.

Cuestión

Supón que se implementa una cola con prioridad mediante un montículo, utilizando la prioridad como criterio de ordenación. ¿Puede asegurarse que dos elementos con la misma prioridad se recuperarán en el orden en que llegaron? Si no es así, ¿cómo lo solucionarías?

Preparación de la sesión de laboratorio

Lectura de los ejercicios propuestos para la sesión de laboratorio.

Additional Resources Section Recursos adicionales