Árboles crecientes aleatorios, su uso en el análisis de estructuras de datos
Ponente: Laura Eslava
Institución: McGill University, Canadá
Tipo de Evento: Investigación
Institución: McGill University, Canadá
Tipo de Evento: Investigación
| Cuándo |
01/09/2015 de 17:00 a 18:00 |
|---|---|
| Dónde | Unidad Multidisciplinaria de Docencia e Investigación (UMDI), Aula 1. UNAM Campus Juriquilla, Querétaro |
| Agregar evento al calendario |
vCal
iCal
|
Una secuencia de árboles crecientes (T(n), n en N) consiste de árboles enraizados T(n) con n vértices y tal que T(n) contiene a T(n-1) para todo n en N. De esta manera, una secuencia (T(n), n en N) se puede considerar como la historia de un árbol cuyo número de vértices crece con el tiempo y, por lo tanto, ésta surge naturalmente en algoritmos de estructura de datos.
En esta plática nos enfocaremos en tres algoritmos que dan lugar a los árboles binarios de búsqueda, árboles recursivos y árboles de estructura de datos para conjuntos disjuntos. Indicaremos cómo es que un enfoque probabilístico ayuda a analizar la eficiencia de dichos algoritmos y cómo es que estas tres clases de árboles están íntimamente relacionadas.
