PDF de programación - Capítulo 1 - Diccionarios

Capítulo 1
Diccionarios1

If debugging is the process of removing bugs,
then programming must be the process of putting
them in.

Edsger W. Dijkstra

Resumen: En este tema se introducen los diccionarios y se presentan dos implemen-
taciones distintas. La primera utiliza árboles de búsqueda, mientras que la segunda
se basa en tablas dispersas abiertas. También estudiaremos como recorrer los datos
almacenados en la tabla usando iteradores, y algunas propiedades deseables en las
funciones de localización.

1. Motivación

Podemos ver un texto como una secuencia (lista) de palabras, donde cada una de ellas
es un string. El problema de las concordancias consiste en contar el número de veces
que aparece cada palabra en ese texto.

Implementar una función que reciba un texto como lista de las palabras (en forma de
cadena) y escriba una línea por cada palabra distinta del texto donde se indique la palabra
y el número de veces que aparece. La lista debe aparecer ordenada alfabéticamente.

2.

Introducción

Los diccionarios son contenedores que almacenan colecciones de pares (clave, valor), y
que permiten acceder a los valores a partir de sus claves asociadas. Podemos verlas como
una extensión de los arrays incorporados en los lenguajes de programación pero en los que
los índices en vez de estar acotados por un rango de enteros determinado (en lenguajes
como C/C++, Java o C# entre 0 y n-1, siendo n el tamaño del array) permiten indicar
un tipo de índice distinto a los enteros y cuyo rango de valores tampoco está acotado.

De ahí es de donde surge la idea de diccionario, en donde hay una entrada para cada
una de las palabras contenidas en él (de tipo cadena, y no un simple entero) y cuyo valor
es, por ejemplo, una lista con las distintas deniciones.

1Marco Antonio Gómez y Antonio Sánchez Ruiz-Granados son los autores principales de este tema.

1

2

Capítulo 1. Diccionarios

Es por esto que los diccionarios están parametrizados por dos tipos distintos: el utilizado

para la clave y el utilizado para el valor.

Aunque la sintáxis concreta puede variar, conceptualmente, pues, un diccionario es

como un array donde se puede utilizar como índices otra cosa distinta a enteros:

Dictionary<string, List<string>> v;

List<string> definiciones;
definiciones.push_back("Libro en el que se recogen...");
definiciones.push_back("Catálogo numeroso de noticias...");

v["diccionario"] = definiciones;

cout << v["diccionario"].front() << endl;

En este tema veremos dos implementaciones distintas, una basada en árboles binarios
(los conocidos como árboles de búsqueda) y otra basada en tablas dispersas (hash tables).
Ambas tienen complejidades mejores que O(n), pero ambas exigen ciertas condiciones a
los tipos que pueden utilizarse como clave.

Como última aclaración antes de empezar, decir que a pesar de que en el tema veremos
dos implementaciones distintas del TAD diccionario, cada una de ellas será independiente.
Es decir no nos planteamos aquí la posibilidad de que exista una clase abstracta a modo
de interfaz Dictionary de la que hereden ambas o algún otro diseño de clases que venga
a reejar que ambas implementaciones representan el mismo TAD de origen.

2.1. Especicación

Desde un punto de vista matemático, los diccionarios son aplicaciones t : C → V que

asocian a cada clave c ∈ C un determinado valor v ∈ V .

Las operaciones publicas del TAD diccionario son:
EmptyDictionary :→ Dictionary [Generadora]
Construye un diccionario vacío, es decir, sin elementos.
insert : Dictionary, Key, V alue → Dictionary [Generadora]
Añade un nuevo par (clave, valor) al diccionario. Si la clave ya existía en el diccio-
nario inicial, se sobrescribe su valor asociado. Es decir, los diccionarios no permiten
almacenar más de un valor por cada clave. Si se desea algo así, o bien se utiliza
otro TAD distinto o bien se utiliza una lista de valores como tipo para el valor del
diccionario igual que se hizo en el ejemplo del apartado 2.
erase : Dictionary, Key → Dictionary [Modicadora]
Elimina un par a partir de la clave proporcionada. Si el diccionario no contiene ningún
par con dicha clave, no se modica.
contains : Dictionary, Key → Boolean [Observadora]
Permite averiguar si la clave está o no en el diccionario (es decir, si tiene un valor
asociado).
at : Dictionary, Key− → V alue [Observadora parcial]
Devuelve el valor asociado a la clave proporcionada, siempre que la clave exista en
el diccionario.

Estructura de Datos y Algoritmos

2. Introducción

3

empty : Dictionary → Boolean [Observadora]
Indica si el diccionario está vacío o no.

Las operaciones generadoras presentan una peculiaridad que no ha aparecido hasta
ahora: un Insert puede anular el resultado de un Insert anterior. Eso implica que hay
más de una forma de construir el mismo diccionario. Por ejemplo, los siguientes diccionarios
(con enteros como claves y caracteres como valor) son equivalentes:

Insert(EmptyDictionary, 3, ’a’)

Insert(Insert(EmptyDictionary, 3, ’b’), 3, ’a’)

Insert(Insert(Insert(EmptyDictionary, 3, ’c’), 3, ’b’), 3, ’a’)

2.2.

Implementación con acceso basado en búsqueda

Usando las estructuras de datos que ya conocemos, podemos implementar las tablas
como colecciones de parejas (clave, valor), en las que el acceso por clave se implementa
mediante una búsqueda en la estructura correspondiente. A continuación planteamos dos
posibles implementaciones usando listas y árboles de búsqueda.

Una manera sencilla de implementar las tablas es mediante una lista de pares (clave,
valor). Dependiendo de si la lista está ordenada o no, tendríamos los siguientes costes
asociados a las operaciones:

Operación
EmptyDictionary
insert
erase
contains
at
empty

Lista desordenada Lista ordenada basada en vectores

O(1)
O(n)
O(n)
O(n)
O(n)
O(1)

O(1)
O(n)
O(n)

O(log n)
O(log n)

O(1)

La operación más habitual cuando se utilizan tablas es at, que consulta el valor asociado
a una clave, por lo que usar una implementación basada en una lista desordenada no
parece la elección más acertada. Aún así, incluimos esta implementación en la tabla por
su simplicidad y como base con la que poder comparar.

Un dato que puede llamar la atención es el coste lineal de la operación insertar cuando
usamos listas desordenadas. Este coste se produce porque antes de insertar el nuevo par
(clave, valor) es necesario comprobar si la clave ya estaba en la tabla para, en ese caso,
modicar su valor asociado. La operación de inserción tiene coste O(n) porque la búsqueda
tiene coste O(n).

Podemos mejorar el coste de las operaciones usando una lista ordenada basada en vecto-
res. Con esta nueva implementación las operaciones at y contains pasan a ser logarítmicas,
ya que se pueden resolver usando búsqueda binaria. Sin embargo, las operaciones insert
y erase siguen siendo lineales, ya que para insertar o borrar un elemento en un vector
debemos desplazar todos los que hay a la derecha.

¾Mejorarían los costes si usamos una lista enlazada ordenada? Pues en realidad no,
porque el algoritmo de búsqueda binaria no se puede aplicar a listas enlazadas, ya que
necesita acceder al elemento central de un intervalo en tiempo constante.

Se necesita, pues, otra estrategia distinta que permita hacer reducir la complejidad de

las operaciones.

Facultad de Informática - UCM

4

Capítulo 1. Diccionarios

3. Árboles de búsqueda

La implementación de los diccionarios mediante lo que se conoce como árboles de
búsqueda intenta conseguir las ventajas de la búsqueda binaria (y sus complejidades loga-
rítmicas) eliminando las desventajas de las inserciones lineales. Para eso evita almacenar
todos los elementos seguidos en memoria.

Para ser capaces de entenderla tenemos que dar primero un pequeño paso atrás y
hablar de los árboles binarios ordenados. En el ejercicio ?? del tema anterior nos pedían
implementar la siguiente función en los árboles binarios:
/∗∗
D e v u e l v e t r u e
de l o s á r b o l e s o r d e n a d o s :
d e l h i j o i z q u i e r d o y menor que l o s d e l h i j o d e r e c h o y t a n t o e l
h i j o i z q u i e r d o como e l d e r e c h o son o r d e n a d o s .
∗/
template <class T>
bool Arbin::esOrdenado() const;

e l á r b o l b i n a r i o cumple l a s p r o p i e d a d e s
l o s

e l e m e n t o s

s i

l a r a i z

e s mayor que t o d o s

Para que ésta operación tenga sentido, es evidente que el tipo T debe poderse ordenar
(en C++ eso se traduce a que tienen implementada la comparación mediante el operador
<). Entenderemos que un árbol está ordenado si su recorrido en inorden está ordenado en
orden estrictamente mayor2. De lo anterior se deduce inmediatamente que la raíz del árbol
es mayor que todos los elementos del hijo izquierdo y menor que todos los elementos del
hijo derecho; además tanto el hijo izquierdo como el hijo derecho deben estar, a su vez,
ordenados.

Con un árbol ordenado, saber si un elemento está en el árbol no requiere un recorrido
por todos los nodos del mismo, sino un recorrido que recuerda a la búsqueda binaria. En
efecto, durante el proceso de búsqueda se mira si la raíz contiene el elemento y en caso
contrario, se busca únicamente en el hijo izquierdo o derecho dependiendo del resultado de
la comparación del elemento buscado y el contenido en la raíz.

La ventaja de los árboles frente a los vectores ordenados, además, es que la inserción
de un nuevo elemento no tiene coste lineal, pues no necesitaremos desplazar todos los
elementos para hacer hueco en el vector; basta con encontrar en qué lugar del árbol debe ir
el elemento para mantener el árbol ordenado y crear el nuevo nodo. Por su parte el borrado,
aunque más difícil de ver de forma intuitiva, también presenta un escenario similar (no hay
que desplazar todos los elementos a la izquierda para borrar el elemento).

Parece fácil ver que si los elementos están distribuidos uniformemente, es decir si cada
nodo tiene aproximadamente el mismo número de nodos en el subárbol izquierdo y el
subárbol derecho, la talla del árbol es del