Universidad Carlos III de Madrid

Ingeniería de Telecomunicación

Enero-Mayo 2010 / January-May 2010

Árboles

Objectives Section Objetivos de aprendizaje

Objetivos de Aprendizaje para Árboles

  • Definir el concepto de árbol (Bloom 1*)

  • Definir los componentes de un árbol: nodo, arista (Bloom 1)

  • Definir las posibles relaciones entre los nodos: ascendientes, descendientes, padre, hijo, hermano (Bloom 1)

  • Diferenciar los tipos de nodos: internos y externos, raíz, hojas (Bloom 1)

  • Definir las propiedades de un árbol: altura, anchura, tamaño (Bloom 1*)

  • Definir el concepto de árbol binario de búsqueda (Bloom 1*)

  • Definir el concepto de árbol equilibrado (Bloom 1)

  • Definir el concepto de montículo binario (Bloom 1*)

  • Poner ejemplos de estructuras de datos adecuadas para ser modeladas mediante árboles. (Bloom 2)

  • Representar mediante un árbol una información dada que pueda interpretarse jerárquicamente (por ejemplo, una fórmula matemática, una oración gramatical, un árbol genealógico, etc.) (Bloom 2*)

  • Dado un árbol determinado, calcular su altura (Bloom 2)

  • Dado un árbol binario de búsqueda, dibujar el árbol resultante después de aplicar un conjunto determinado de operaciones de inserción (Bloom 2)

  • Describir las operaciones efectuadas por el algoritmo de búsqueda binaria para recuperar un determinado dato en un árbol dado (Bloom 2*)

  • Explicar cómo se inserta un dato en un árbol binario de búsqueda (no equilibrado) (Bloom 2*)

  • Dado el código de un método que trabaja sobre un árbol, identificar el efecto del mismo para un escenario de valores concretos (conocidos el estado inicial del árbol y los parámetros de entrada del método) (Bloom 2*)

  • Implementar el algoritmo para calcular la altura de un árbol. (Bloom 3)

  • Implementar el algoritmo para determinar el número de nodos de un árbol. (Bloom 3)

  • Implementar un algoritmo que implique recorrer un árbol genérico en modo pre-orden (por ejemplo, imprimir el contenido de todos los nodos). (Bloom 3)

  • Implementar un algoritmo que implique recorrer un árbol genérico en modo post-orden (por ejemplo, imprimir el contenido de todos los nodos). (Bloom 3)

  • Implementar un algoritmo que implique recorrer un árbol binario en modo in-orden (por ejemplo, imprimir el contenido de todos los nodos). (Bloom 3)

  • Implementar el algoritmo de inserción en un árbol binario de búsqueda (no equilibrado). (Bloom 3)

  • Implementar el algoritmo de búsqueda (binaria) en un árbol de búsqueda binario. (Bloom 3)

  • Implementar un programa que utilice un árbol para almacenar una información dada que pueda interpretarse jerárquicamente (por ejemplo, una fórmula matemática, una oración gramatical, un árbol genealógico, etc.). (Bloom 3)

  • Implementar el algoritmo de inserción en un montículo binario. (Bloom 3)

  • Implementar el algoritmo de eliminación en un montículo binario. (Bloom 3)

  • Dadas dos secuencias de operaciones de inserción (no equilibradas), determinar cuál de los 2 árboles de búsqueda binarios resultantes será más eficiente en el caso general. (Bloom 4)

  • Identificar el árbol como estructura de datos más conveniente para modelar la información en problemas que involucren datos organizados con algún tipo de jerarquía. (Bloom 4)

  • Resolver problemas sencillos que involucren datos organizados jerárquicamente, incluyendo: selección de un árbol como estructura de datos más adecuada para modelar la información, definición de la estructura de datos de acuerdo con alguna de las alternativas vistas, e implementación de algoritmos de procesamiento sobre dicha estructura (inserción, búsqueda, determinación de características básicas como la altura). (Bloom 5)

  • Comparar y justificar la adecuación de diferentes implementaciones en función de las características de la información a modelar (por ejemplo, implementación basada en nodos vs. Implementación basada en arrays para el caso de montículos). (Bloom 6)

Lecture Section Sesión 1 (teoría): Árboles (I)

Material

Lab Section Sesión 2 (laboratorio): Árboles (I)

Material

Material (con soluciones)

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

Material

Lab Section Sesión 4 (laboratorio): Árboles (II)

Material

Material (con soluciones)