PDF de programación - Estructuras de datos y algoritmos 6. Implementación de mapas, árboles y grafos

Estructuras de datos y algoritmos
1. Introducción
2. Estructuras de datos lineales
3. Estructuras de datos jerárquicas
4. Grafos y caminos
5. Implementación de listas, colas y pilas
6. Implementación de mapas, árboles y grafos

UNIVERSIDAD
DE CANTABRIA

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN
4

© Michael González Harbour

3/dic/09

1

UNIVERSIDAD
DE CANTABRIA

6. Implementación de mapas, árboles y grafos
• 6.1. Mapas y conjuntos implementados con tablas de troceado
• 6.2. Árboles
• 6.3. Árboles binarios
• 6.4. Árboles binarios equilibrados y conjuntos ordenados
• 6.5. B-árboles
• 6.6. Colas de prioridad
• 6.7. Grafos

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

3/dic/09

2

6.1. Mapas y conjuntos implementados
con tablas de troceado
Las tablas de troceado (o tablas hash) permiten realizar
operaciones de búsqueda muy eficientes en promedio
• permiten consultar o eliminar elementos conociendo su nombre

UNIVERSIDAD
DE CANTABRIA

o identificador

• el tiempo es constante en la mayor parte de los casos: O(1)
• son muy apropiadas por tanto para los mapas, o diccionarios
El principio de funcionamiento es almacenar los datos en una tabla
• se convierte el nombre o identificador a un número entero, que

sirve como índice de la tabla

• para que la tabla no sea excesivamente grande, el número

entero, llamado clave, se compacta a un rango pequeño
- habitualmente mediante la operación módulo (%)

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

3/dic/09

3

UNIVERSIDAD
DE CANTABRIA

Implementación mediante tablas hash
La clase del elemento debe disponer de un método hashCode()
para convertir un objeto de esa clase en un dato numérico llamado
clave
public int hashCode()
Los datos se guardan en un array cuyo índice es el tipo clave
El principal problema es la resolución de colisiones
• cuando dos datos tienen la misma clave
La función hashCode debe distribuir las claves de modo muy
homogéneo

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

3/dic/09

4

Algunas funciones de troceado para
números enteros
Queremos trocear el identificador id
Primer método: función módulo
• id % max, donde max es el tamaño de la tabla
• el inconveniente es que sólo se usa la parte menos significativa

UNIVERSIDAD
DE CANTABRIA

del identificador

• si hay muchos identificadores con la misma parte menos

significativa, no se obtienen resultados homogéneos

Ejemplo: id=13267456, max=100

1 3 2 6 7 4 5 6

5 6

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

3/dic/09

5

Algunas funciones de troceado para
números enteros
Segundo método: troceado en n grupos de cifras

UNIVERSIDAD
DE CANTABRIA

Clave

=

⎛
⎜
⎝

⎛
⎝

id
⎞
------------ mod max
⎠
maxi

⎞
⎟
⎠

mod max

n
1–
∑
0=

i

La ventaja es que se utiliza todo el número
• el resultado puede (o no) ser más homogéneo
Ejemplo: id=13267456, max=100, n=4

1 3 2 6 7 4 5 6

1 3

+

2 6

+

7 4

+

5 6

%100=

6 9

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

3/dic/09

6

Algunas funciones de troceado para
textos
Para textos occidentales, se usa el hecho de que los caracteres se
pueden representar mediante un número pequeño de 7 u 8 bits
Por ejemplo, el texto "hola" es una secuencia de {’h’,’o’,’l’,’a’}
• se podría representar mediante su conversión a cifras de 7 bits

UNIVERSIDAD
DE CANTABRIA

clave=’h’*1283+’o’*1282+’l’*1281+’a’*1280

• Pero para cadenas largas, este cálculo excedería el valor que se

puede guardar en un entero

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

3/dic/09

7

Algunas funciones de troceado para
textos (cont.)
Usaremos la siguiente propiedad de los polinomios

UNIVERSIDAD
DE CANTABRIA

A3X3 A2X2 A1X1 A0X0

+

+

+

se puede evaluar también como
)X A2+

A3

(

(

(

)X A1+

)X A0+

En la segunda ecuación
• se evita el cálculo de xi
• se evita un resultado intermedio demasiado grande
• el cálculo se hace de izquierda a derecha, en el orden del string

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

3/dic/09

8

Algunas funciones de troceado para
textos (cont.)
En el cálculo del polinomio anterior, podemos hacer la operación
módulo con el tamaño de la tabla a cada paso
• Así conseguiremos resultados intermedios pequeños
Si Cod(i) es el código numérico del carácter i:, la función
quedará como

UNIVERSIDAD
DE CANTABRIA

Clavei

=

(

Clavei

1–

⋅

128 Cod i( )

+

) mod max

partiendo de un valor inicial Clave=0

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

3/dic/09

9

Algunas funciones de troceado para
textos (cont.)
Otra alternativa más eficiente es tener en cuenta que las
operaciones con enteros admiten en muchos lenguajes (incluido
Java) el desbordamiento, haciendo una operación módulo
automática con el número de valores que caben en un entero
• Ello permite hacer una sola operación módulo al final
• También podemos usar un número menor para multiplicar la

clave, dado que el número de letras distintas suele ser pequeño

UNIVERSIDAD
DE CANTABRIA

Clavei

=
Clave

Clavei
=

⋅

37 Cod i( )

+

1–

Claven mod max

• En este caso, hay que tener en cuenta que el resultado puede ser
negativo, para ponerlo en positivo, sumarle max

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

3/dic/09

10

UNIVERSIDAD
DE CANTABRIA

Ejemplo de función de troceado para
strings
public static int hashCode(String s, int max) {
int clave=0;
for (int i=0; i<s.length(); i++) {
clave=(clave*37+ s.charAt(i));
}
clave = clave % max;
if (clave<0) {
clave=clave+max;
}
return clave;
}

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

3/dic/09

11

Métodos para la resolución de
colisiones
Los tres métodos más simples son:
• encadenamiento o troceado abierto
• por exploración, o troceado cerrado

- exploración lineal
- exploración cuadrática
- otras exploraciones

UNIVERSIDAD
DE CANTABRIA

Su eficiencia es distinta, y depende del grado de ocupación de la
tabla
• troceado abierto: se puede funcionar bien con una ocupación

del 100%, pero no más

• troceado cerrado: conviene nunca superar el 75% de ocupación

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

3/dic/09

12

Resolución de colisiones:
troceado abierto

UNIVERSIDAD
DE CANTABRIA

Tabla Hash

0
1
2
3
4
5
6
7
8
9

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

3/dic/09

13

Troceado abierto (cont.)
Cada elemento de la tabla hash es una lista enlazada simple.
• Cada elemento del mapa se guarda en la lista correspondiente a

UNIVERSIDAD
DE CANTABRIA

su clave

Este método sólo es eficiente cuando la cantidad de colisiones es
pequeña, y las listas son cortas
• Para ello se necesita que la tabla tenga un tamaño mayor o igual
que el número de elementos a almacenar
• y que, además, la función hash sea muy homogénea

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

3/dic/09

14

Operaciones para el troceado abierto
asignaValor:

UNIVERSIDAD
DE CANTABRIA

- Calcular la clave de troceado
- Buscar el dato origen en la lista de esa clave
- Si se encuentra, cambiar el destino
- Si no, añadir la pareja (origen-destino) a la lista, por ejemplo al
principio (ya que es más eficiente en una lista enlazada simple)

borra:

- Calcular la clave de troceado
- Buscar el dato origen en la lista de esa clave
- Si se encuentra, eliminar el elemento de la lista
- Si no se encuentra, indicar que no existe

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

3/dic/09

15

Operaciones para el troceado abierto
(cont.)
obtenValor:

- Calcular la clave de troceado
- Buscar el dato origen en la lista de esa clave
- Si se encuentra, devolver el destino asociado
- Si no se encuentra, indicar que no existe

UNIVERSIDAD
DE CANTABRIA

hazNulo:

- Hacer nulas todas las listas de la tabla

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

3/dic/09

16

UNIVERSIDAD
DE CANTABRIA

Implementación de un mapa mediante
troceado abierto
Por simplicidad, no utilizaremos una extensión de AbstractMap
• nos obligaría a implementar EntrySet, que es complicado
Haremos una implementación de los métodos básicos
• constructor
•put
•get
•remove
•containsKey

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

3/dic/09

17

Implementación de un mapa mediante
troceado abierto

UNIVERSIDAD
DE CANTABRIA

/**
* Clase que representa un mapa con troceado abierto
*/public class MapaAbierto<K,V>
{
// atributos privados
private ListaEnlazadaSimple<Entry<K,V>>[] tabla;
private static class Entry<K,V> {
K clave;
V valor;
public Entry(K clave, V valor) {
this.clave=clave;
this.valor=valor;
}

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

3/dic/09

18

Implementación de un mapa mediante
troceado abierto (cont.)
public boolean equals(Object otra) {
if (otra instanceof Entry) {
return this.clave.equals
(((Entry<K,V>)otra).clave);
} else {
return false;
}
}
}

UNIVERSIDAD
DE CANTABRIA

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

3/dic/09

19

UNIVERSIDAD
DE CANTABRIA

Implementación de un mapa mediante
troceado abierto (cont.)
/**
* Constructor; se le pasa el tamaño de la tabla*/
public MapaAbierto(int tamano) {
tabla =
new ListaEnlazadaSimple[tamano];
for (int i = 0; i < tamano; i++) {
tabla[i] =
new ListaEnlazadaSimple<Entry<K,V>>();
}
}
// valor para la tabla hash
private int valor