Conjuntos

Estructuras de Datos y Algoritmos

Tema 4
Conjuntos

Objetivos
●

●

●

Estudiar nuevos TADs que modelan conjuntos
dinámicos de elementos: diccionarios, colas de
prioridad, conjuntos disjuntos
Analizar distintas representaciones y algoritmos
asociados para dichos TADs.
Analizar qué TAD y qué representación es más
adecuada para resolver un problema dado.

Contenido1.Introducción
2.Conjuntos dinámicos: diccionario, cola de prioridad y
conjuntos disjuntos
3.Listas enlazadas
4.Árbol binario de búsqueda
5.Tabla Hash
6.Montículo (heaps)
7.MF-Set
8.Tries
9.Árboles balanceados: Árboles AVL, Árboles 2-3, BÁrboles, B-Árboles +

Bibliografía
●

“Introduction to Algorithms”. Cormen, Leiserson y Rivest.

●

“Fundamentos de Algoritmia”. Brassard y Bratley.●

“Computer algorithms”. Horowitz, Sahni y Rajasekaran.

●

“Estructuras de datos y Algoritmos”, Aho, Hopcroft y Ullman

●

[Weiss95] “Estructuras de datos y algoritmos” , Weiss, Mark
Allen. Ed. Addison-Wesley, U.S.A., 1995,

Introducción
●

●
●

●

En ocasiones necesitamos almacenar
colecciones de elementos.
Un conjunto no posee elementos repetidos.
Podemos efectuar lasoperaciones típicas de:
pertenencia, igualdad o inclusión, unión,
intersección, diferencia, etc.
En ocasiones nos interesa manipular la colección
de elementos: conjuntos dinámicos.

Conjuntos dinámicos
●

●

Conjuntos en los que sus elementos pueden
variar a lo largo del tiempo.
Los elementos se representan por:
●
●

●

Una clave: valor que identifica al elemento
Informaciónsatélite: información asociada al
elemento

Puede existir una relación de orden total entre
las claves (ej.: enteros, reales, cadenas)
●

Entonces es posible definir mínimo, máximo,
predecesor, sucesor.

Conjuntos dinámicos
Operaciones sobre conjunto dinámico C
●

Consultoras
●

C.vacío(): indica si el conjunto es vacío o no

●

C.buscar(k): devuelve el elemento x con clave k●

C.mínimo(): devuelve el elemento x con clave mínima

●

C.máximo(): devuelve el elemento x con clave máxima

●

●

C.predecesor(x): devuelve el elemento de clave
inmediatamente inferior a la de x
C.sucesor(x): devuelve el elemento de clave inmediatamente
superior a la de x

Conjuntos dinámicos
Operaciones sobre conjunto dinámico C
●

Modificadoras
●

C.insertar(x): añadeel elemento x

●

C.eliminar(x): elimina el elemento x

●

C.eliminarMin(): elimina el elemento con clave mínima

●

C.eliminarMax(): elimina el elemento con clave máxima

Conjuntos dinámicos
Algunos TADs que modelan conjuntos dinámicos
●

Diccionarios

●

Colas de prioridad

●

Conjuntos disjuntos

Conjuntos dinámicos
Diccionario
●

Todos sus elementos poseen unaclave y un valor.

●

Operaciones soportadas:
●
●

●

Consultoras: C.buscar(k)
Modificadoras: C.insertar(x), C.eliminar(x)

Ejemplos: traductores, tabla de símbolos de un
compilador, arrays asociativos, etc.

Conjuntos dinámicos
Diccionario
●

Interfaz Diccionario
public interface Diccionario {
void insertar(C clave, V valor);
V buscar(C clave);
void eliminar(C clave);
}Conjuntos dinámicos
Cola de prioridad
●

●

Sus elementos poseen una prioridad, que determina el
orden de acceso.
Operaciones soportadas:
●
●

●

Consultoras: C.máximo() (ó C.mínimo())
Modificadoras: C.insertar(x), C.eliminarMax() (ó
C.eliminarMin())

Ejemplos: colas de procesos en un sistema multitarea,
simulación de eventos, protocolos de comunicación con
prioridad, etc.Conjuntos dinámicos
Cola de prioridad
●

Interfaz ColaPrioridad
public interface ColaPrioridad {
public void insertar(E x);
public E maximo();
public E eliminarMax();
}

Conjuntos dinámicos
Conjuntos disjuntos
●

Sus elementos se agrupan en conjuntos disjuntos.

●

Típicamente modelan el particionado de otro conjunto.

●

Operaciones soportadas:
●
●

●...