Tema 3. Representación de Conjuntos

1

OBJETIVOS • Estudiar los conjuntos desde un punto de vista algorítmico (conjuntos dinámicos). • Estudiar técnicas de representación de conjuntos (algoritmos de manipulación). • Estudiar los tipos de datos: diccionario, cola de prioridad. • Aprender a seleccionar el tipo de datos y la implementación más adecuados al problema 2 a resolver.

ÍNDICE 1. Conceptos Generales 2. Representaciones básicas:listas 3. Árboles Binarios de Búsqueda 4.Tablas de Dispersión 5. Árboles Parcialmente Ordenados (Heaps) 6. Conjuntos Disjuntos (Mfsets)

3

BIBLIOGRAFÍA • T.H. Cormen, C.E. Leiserson, R.L. Rivest Introduction to Algorithms. MIT Press, 1990. – Parte III: Introducción y capítulos 12 y 13 – Parte V: Capítulos 19 y 22

• G. Brassard, P. Bratley. Fundamentos de Algoritmia. Prentice Hall, 1997. Sección 1.9. • Aho A.V., Hopcroft J.E., Ullman J.E. Estructuras de datos y Algoritmos. Addison-Wesley, 1988. Capítulos 4 y 5

4

1. CONCEPTOS GENERALES • Elementos de un conjunto (dinámico). Típicamente: – clave: campo de identificación – información satélite: asociada al objeto

• Algunos conjuntos se caracterizan porque en el conjunto de claves se puede establecer una relación de orden total. – En este caso se puede definir el elemento mínimo de un conjunto, o el sucesor.

5

Operaciones sobre conjuntos • Consultoras: – Buscar, Mínimo, Máximo, Predecesor, Sucesor

• Modificadoras: – Insertar, Borrar

6

Operaciones sobre conjuntos (cont.) – BUSCA(S,k): dado un cjto S y una clave k devuelve la posición x tal que clave[x]=k, o un valor especial si x∉S. – INSERTA(S,x): añade a S el elemento apuntado por x. – BORRA(S,x): borra el elemento apuntado por x de S

7

Operaciones sobre conjuntos (cont.) – MÍNIMO(S): devuelve el elemento de S con la clave más pequeña – MÁXIMO(S): devuelve el elemento de S con la clave más grande. – SUCESOR(S,x): devuelve el elemento de clave inmediatamente superior a la de x o un valor especial si x es el máximo – PREDECESOR(S,x): devuelve el elemento de clave inmediatamente inferior a la de x o un 8 valor especial si x es el mínimo

Algunos tipos de conjuntos dinámicos

• Pilas y Colas – Se inserta y se borra un elemento predeterminado – Pila: política LIFO – Cola: política FIFO

• Diccionarios – Operaciones Inserta, Borra y Busca

• Colas de prioridad – Operaciones Inserta, Elimina_Max

9

2. Implementaciones básicas • Vector de bits • Listas enlazadas – – – –

doblemente enlazadas ordenadas circulares otras...

10

Ejemplo. • Lista doblemente enlazada. Notación – Una lista L tiene el atributo primero para acceder al principio de la misma (primero[L]) – Si x es un elemento de la lista: • clave[x] es la clave

• suc[x] apunta a su sucesor • pred[x] apunta a su predecesor – Si pred[x]=NIL x no tiene predecesor, es el primer elemento de la lista – Si suc[x]=NIL x no tiene sucesor, es el último elemento de la lista 11

Ejemplo. Buscar Buscar(L,k) /* Encuentra el primer elemento con clave k en L y devuelve su posición. Si no lo encuentra devuelve NIL*/

x:=primero[L]; mientras xNIL y clave[x]k x:=suc[x] devuelve x El coste es O(n), con n=|L| (en el peor caso hay que recorrer toda la lista).

12

Ejemplo. Insertar Inserta(L,x) /* Dado un elemento x lo inserta en cabeza de lista L*/

suc[x]:=primero[L]; Si primero[L]NIL entonces pred[primero[L]]:=x primero[L]:=x pred[x]:=NIL El coste es O(1).

13

Ejercicio. Borrar Borra(L,x) /* Dado un elemento x lo borra de la lista L */

Si pred[x]NIL entonces suc[pred[x]]:=suc[x] sino primero[L]:=suc[x] Si suc[x]NIL entonces pred[suc[x]]:=pred[x] El coste es O(1). Si queremos borrar un elemento con una clave determinada primero hay que Buscar. Coste O(n)

14

Estudio comparativo de costes Operación

Lista

BUSCA(S,k)

O(|S|)

Lista ordenada O(|S|)

INSERTA(S,x)

O(1)

O(|S|)

BORRA(S,x)

O(|1|)

O(|1|)

MÍNIMO(S) / MÁXIMO(S)

O(|S|)

O(1)

PREDECESOR(S,x) / SUCESOR(S,x)

O(|S|)

O(|S|)

15

3) ÁRBOLES BINARIOS DE BÚSQUEDA Un árbol binario es de búsqueda si: • Todos los elementos del subárbol izquierdo son menores que el de la raíz • Todos los elementos del subárbol derecho son mayores que el de la raíz • Propiedad: Si se listan los elementos según recorrido en

inorden resulta una secuencia ordenada. Ejercicio: ¿Cuál es la diferencia entre la propiedad de los ABB y la de Heaps?, ¿Puede utilizarse la propiedad de Heaps para listar de forma ordenada las claves de un árbol con n nodos en tiempo O(n)? 16

EJEMPLOS Ejemplos: Representación del conjunto S={5,2,7,4,8,3} 5 3 2

2 7

4

3 8

7 5

8

4 Ejercicio: Dibujar árboles binarios de búsqueda de alturas 2,3,4,5,6 para el conjunto de claves {1,4,5,10,16,17,21} 17

IMPLEMENTACIÓN x

Der[x]

5

Izq[x]

3 2

7 4

8

18

IMPLEMENTACIÓN DE OPERACIONES SOBRE CONJUNTOS

• • • • •

Busca (S,k) Mínimo(S) y Máximo(S) Sucesor(S,x) y Predecesor(S,x) Inserta(S,x) Borra(S,x)

19

BÚSQUEDA DE UNA CLAVE EN UN ABB {x es un puntero a la raíz de un ABB y k es una clave}

ABB_BUSCAR(x,k) {Devuelve un puntero al nodo con clave k si existe o Nil si no existe}

Si

x=nil ∨ k=clave[x]

Coste O(h) entonces devuelve x Si k