.jpg)
Árboles
Tabla de contenidos
.png)
Sesión 3 (teoría): Árboles (II)
.png)
Transparencias
-trans.png)
Lecturas
-
Estructuras de datos en Java de Mark A. Weiss: capítulo 20 sobre Colas con Prioridad y Montículos Binarios.
-
Data Structures and Algorithms in Java by Michael T. Goodrich and Roberto Tamassia (4th edition): apartado 6.3 sobre Montículos (Heaps)
.png)
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.
.png)
Recursos adicionales
-
Montículo binario, applet desarrollado por Kubo Kovac. Muestra mediante animaciones el funcionamiento de diversas estructuras de datos basadas en árboles, como montículos binarios o árboles binarios de búsqueda.