PDF de programación - TEMA 4 - El tipo conjunto

DLSI (Univ. Alicante)

TEMA 4

El tipo conjunto

PROGRAMACIÓN Y ESTRUCTURAS DE

DATOS

DLSI (Univ. Alicante)

Tema 4. Tipo conjunto

Tipo conjunto

1. Definiciones generales
2. Diccionario

2.1. Tabla de dispersión
2.2. Trie
2.3. Árboles de búsqueda digitales

3. Cola de prioridad

3.1. Montículo
3.2. Cola de prioridad doble

3.2.1. Montículo doble

3.3. Árbol izquierdista o leftist

2

DLSI (Univ. Alicante)

1. Tipo Conjunto

DEFINICIONES

Tema 4. Tipo conjunto

Un conjunto es una colección de elementos, cada uno de los cuales
puede ser un conjunto, o un elemento primitivo que recibe el
nombre de átomo

Todos los miembros del conjunto son distintos

El orden de los elementos no es importante (distinto de las listas)

Notación de Conjuntos

Se representa encerrando sus miembros entre llaves {1,2,5}
Relación fundamental, la de pertenencia: ∈ {x / x ∈ Naturales} , {x / x < 8}
Existe un conjunto especial sin elementos: ∅
A ⊂ B si todo elemento de A también lo es de B
Conjunto Universal: formado por todos los posibles elementos que puede contener

DLSI (Univ. Alicante)

1. Tipo Conjunto

SINTAXIS

Tema 4. Tipo conjunto

MODULO GENERICO ModuloConjunto
MODULO Conjunto USA Boolean, Natural
SINTAXIS

Crear ( ) Conjunto
Insertar( Conjunto, Ítem ) Conjunto
Eliminar( Conjunto, Ítem ) Conjunto
Pertenece( Conjunto, Ítem ) Boolean
EsVacíoConjunto( Conjunto ) Boolean
Cardinalidad( Conjunto ) Natural
Unión( Conjunto, Conjunto ) Conjunto
Intersección( Conjunto, Conjunto ) Conjunto
Diferencia( Conjunto, Conjunto ) Conjunto

C, D: Conjunto;

x, y: Ítem;

VAR

3

4

DLSI (Univ. Alicante)

1. Tipo Conjunto

SEMÁNTICA (I)

Tema 4. Tipo conjunto

EsVacíoConjunto( Crear ) Cierto
EsVacíoConjunto( Insertar( C, x ) ) Falso
Insertar( Insertar( C, x ), y )

si ( x == y ) entonces Insertar( C, x ) //no se permiten elementos repetidos
sino Insertar( Insertar( C, y ), x )

//da igual el orden de inserción de los elem.

// ¿y si permitieran elementos repetidos?

Eliminar( Crear, x ) Crear
Eliminar( Insertar( C, x ), y )

si ( x == y ) entonces C
sino Insertar( Eliminar( C, y ), x )

Pertenece( Crear, x ) Falso
Pertenece( Insertar( C, x ), y )

si ( x == y ) entonces Cierto
sino Pertenece( C, y )
Cardinalidad( Crear ) 0
Cardinalidad(Insertar(C,x)) 1+Cardinalidad(C)
Unión( Crear, C ) C
Unión( Insertar( C,x ), D )

si ( Pertenece( D, x ) ) entonces Unión( C, D )
sino Insertar( Unión( C, D ), x )

DLSI (Univ. Alicante)

1. Tipo Conjunto

SEMÁNTICA (II)

Tema 4. Tipo conjunto

Diferencia( Crear, C ) Crear
Diferencia( Insertar( C,x ), D )

si ( Pertenece( D, x ) )
entonces Diferencia( C, D )
sino Insertar( Diferencia( C, D ), x )

Intersección( Crear, D ) Crear
Intersección( Insertar( C,x ), D )

si ( Pertenece( D, x ) )
entonces Insertar( Intersección( C, D ), x )
sino Intersección( C, D )

5

6

DLSI (Univ. Alicante)

1. Tipo Conjunto
IMPLEMENTACIÓN

Tema 4. Tipo conjunto

Mediante un vector

-Vector de bits/enteros (cada componente corresponde a
un elemento del conjunto universal)

0

0

10

1
0
0 1 2 3 4 5

-Vector de elementos

1

9

0

24

Almacenar los elementos conforme se inserten
(mediante listas, árboles, ...):

Espacio proporcional al conjunto representado

DLSI (Univ. Alicante)

1. Tipo Conjunto

EJERCICIO

Tema 4. Tipo conjunto

Rellenar la siguiente tabla de complejidades (peor caso):

m=elem. conjto.
n=elem. conjto. Univ.

Vector de Bits

Lista
ordenada

Lista
desordenada

Búsqueda

Inserción

Unión

7

8

DLSI (Univ. Alicante)

2. DICCIONARIO

DEFINICIÓN

Tema 4. Tipo conjunto

Subtipo del CONJUNTO, con las operaciones:

CREAR
INSERTAR
BORRAR
BÚSQUEDA

9

DLSI (Univ. Alicante)

2. DICCIONARIO

IMPLEMENTACIÓN

Tema 4. Tipo conjunto

Implementaciones sencillas:

• Mediante listas o vectores

Búsqueda, Inserción y Borrado:
O (n)
Listas:
O (1)
Vector Bits:
Vector Elementos: O (n)

• Mediante TAD Tabla de Dispersión (HASHING)

10

DLSI (Univ. Alicante)

Tema 4. Tipo conjunto

2.1. TABLA DE DISPERSIÓN (HASHING)

DEFINICIÓN

HASHING: Utilizaremos la información del elemento a almacenar

para buscar su posición dentro de la estructura

Operaciones:

Búsqueda. O(1)
Inserción. O(1)
O(1)
Borrado.

11

DLSI (Univ. Alicante)

Tema 4. Tipo conjunto

2.1. TABLA DE DISPERSIÓN (HASHING)

MÉTODO

Dividir el conjunto en un número finito “B” de clases
Se usa función de dispersión H, tal que H(x) será un valor entre 0 y B-1

Formas de dispersión:
Abierta: No impone tamaño límite al conjunto
Cerrada: usa un tamaño fijo de almacenamiento (limita el tamaño)

12

DLSI (Univ. Alicante)

Tema 4. Tipo conjunto

2.1. Tabla Hash. Dispersión Cerrada

DEFINICIÓN

Los elementos se almacenan en tabla de tamaño fijo (TABLA DE

DISPERSIÓN)

La tabla se divide en B clases, y cada una podrá almacenar S

elementos

La Función de dispersión se implementa mediante una función

aritmética

H(x)= x MOD B

13

DLSI (Univ. Alicante)

Tema 4. Tipo conjunto

2.1. Tabla Hash. Dispersión Cerrada

INSERCIÓN

Caso COLISIÓN: x1, x2 (SINÓNIMOS/ H(x1) = H(x2))

ESTRATEGIA DE REDISPERSION:

• Elegir sucesión de localidades alternas dentro de la tabla, hasta
encontrar una vacía

H(x), h1(x), h2(x), h3(x), ...

• Si ninguna está vacía: no es posible insertar

14

DLSI (Univ. Alicante)

Tema 4. Tipo conjunto

2.1. Tabla Hash. Dispersión Cerrada

INSERCIÓN. EJEMPLO

Ejemplo. Insertar en una tabla de dispersión cerrada de tamaño B=7, con
función de dispersión H(x)= x MOD B, y con estrategia de redispersión la
siguiente posición de la tabla, los siguientes elementos: 23, 14, 9, 6, 30, 12,
18, 25

14

23

0

1

2

3

4

5

6

14

23

9

0

1

2

3

4

5

6

0

1

2

3

4

5

6

23, 14
un sólo
intento

9
dos
intentos

14

23

9

6

6
un sólo
intento

0

1

2

3

4

5

6

14

23

9

30

6

0

1

2

3

4

5

6

14

23

9

30
12

6

0

1

2

3

4

5

6

14

18
23

9

30
12

6

0

1

2

3

4

5

6

14
18

23

9

30
12

6

30
tres
intentos

12
un sólo
intento

18
cinco
intentos

25
tabla
llena

Nº TOTAL DE INTENTOS
HASTA LA CLAVE 18:

14

15

DLSI (Univ. Alicante)

Tema 4. Tipo conjunto

2.1. Tabla Hash. Dispersión Cerrada

BÚSQUEDA. BORRADO

BÚSQUEDA DE ELEMENTOS
Buscar en sucesión de localidades alternas dentro de la tabla, hasta encontrar
una vacía:

H(x), h1(x), h2(x), h3(x), ...

BORRADO DE ELEMENTOS
Hay que distinguir durante la búsqueda:

- Casillas vacías
- Casillas suprimidas

Durante la inserción las casillas suprimidas se tratarán como espacio disponible.

16

DLSI (Univ. Alicante)

Tema 4. Tipo conjunto

2.1. Tabla Hash. Dispersión Cerrada

ANÁLISIS (I)

ESTRATEGIA DE REDISPERSIÓN LINEAL (“siguiente posición”):

- No eficiente. Larga secuencia de intentos

hi(x) = ( H(x) + 1 • i ) MOD B

/ c=1 hi(x) = (hi-1(x) + 1) MOD B

ESTRATEGIA DE REDISPERSIÓN ALEATORIA:

hi(x) = ( H(x) + c • i ) MOD B

/ c>1 hi(x) = (hi-1(x) + c) MOD B

Sigue produciendo AMONTONAMIENTO: siguiente intento sólo en

función del anterior

c y B no deben tener factores primos comunes mayores que 1

E.R. CON 2ª FUNCION DE HASH:

k (x) = (x MOD (B-1)) + 1

hi(x) = ( H(x) + k(x) • i ) MOD B hi(x) = (hi-1(x) + k(x)) MOD B

B debe ser primo

17

DLSI (Univ. Alicante)

Tema 4. Tipo conjunto

2.1. Tabla Hash. Dispersión Cerrada

ANÁLISIS (II)

LA MEJOR FUNCIÓN DE DISPERSIÓN:

- Que sea fácil de calcular

- Que minimice el nº de colisiones

- Que distribuya los elementos de forma azarosa

- Debe hacer uso de toda la información asociada a las etiquetas

18

DLSI (Univ. Alicante)

Tema 4. Tipo conjunto

2.1. Tabla Hash. Dispersión Cerrada

ANÁLISIS (III)
Estrategia de redispersión aleatoria

c y B no deben tener factores primos comunes mayores que 1 para
que busque en todas las posiciones de la tabla

Ejemplo c=4; B=6
hi(x) = ( H(x) + c • i ) MOD B = (hi-1(x) + c) MOD B

H(10)=10 MOD 6=4
h1(10)=(4+4 •1) MOD 6=(4+4) MOD 6=2
h2(10)=(4+4 •2) MOD 6=(2+4) MOD 6=0
h3(10)=(0+4) MOD 6=4; h4(10)=(4+4) MOD 6=2

Ejemplo ¿c=6; B=9? ¿c=2; B=9?

Estrategia de redispersión con 2ª función hash

X X X
0 1 2 3 4 5

B debe ser primo para que busque en todas las posiciones de la tabla

c=k(x) 1…B-1
// k (x) = (x MOD (B-1)) + 1
hi(x) = ( H(x) + k(x) • i ) MOD B = (hi-1(x) + k(x)) MOD B

B=7; k(x)=1…6
B=11;k(x)=1…10

19

DLSI (Univ. Alicante)

Tema 4. Tipo conjunto

2.1. Tabla Hash. Dispersión Cerrada

EJERCICIOS

1) Insertar en una tabla de dispersión cerrada de tamaño B=7, con función
de dispersión H(x)= x MOD B, y con estrategia de redispersión segunda
función hash, los siguientes elementos: 23, 14, 9, 6, 30, 12, 18

20

DLSI (Univ. Alicante)

2.1. Tabla Hash. Dispersión Abierta

Tema 4. Tipo conjunto

DEFINICIÓN

- Elimina el problema del CLUSTERING SECUNDARIO (colisiones entre
claves no sinónimas)

- Las colisiones se resuelven utilizando una lista enlazada

0

1

2

3

4

5

6

14

23

18

12

6

30

9

25

21

Tema 4. Tipo conjunto

DLSI (Univ. Alicante)

2.1. Tabla Hash
FACTOR DE CARGA (I)

α =

n
B

n = nº elem. de la tabla. B = tamaño de la tabla

HASH CERRADO: 0 ≤ α ≤ 1
HASH ABIERTO: α ≥ 0
casilla).

(No hay límite en el nº de elementos en cada

Teorema:

En Hash Abierto con factor de carga α:

• el nº esperado de pruebas en inserción o búsqueda sin éxito es ‘1+α’, y

• el nº esperado de pruebas para borrado o búsqueda con éxito es ‘1+1/2 • (1 + α)’

22

DLSI (Univ. Alicante)

2.1. Tabla Hash
FACTOR DE CARGA (II)

Tema 4. Tipo conjunto

Teorema:

En Hash Cerrado con resolución lineal de colisiones, con factor de carga α:

• el nº esperado de pruebas en inserción o búsq