Semana 9 - Diccionarios y recorridos iterativos de árboles binarios

Esta semana presentamos el TAD Diccionario y una de sus implementaciones, basada en árboles binarios de búsqueda. Existen otras implementaciones, basadas en tablas hash, que estudiaremos la semana que viene.

También aprovecharemos esta semana para profundizar en los recorridos sobre árboles binarios. Nuestro objetivo será recorrer en inorden los nodos de un árbol binario de manera iterativa, mediante iteradores.

9.1. Operaciones del TAD Diccionario

Los diccionarios (maps en inglés) son unos de los tipos abstractos de datos más utilizados para almacenar colecciones de elementos. Cada valor almacenado en un diccionario va asociado a una clave, que es la que utilizamos para posteriormente buscar dicho valor. Comenzamos describiendo las operaciones básicas:

▶️ El TAD Diccionario - operaciones (11:29)

Los diccionarios son la representación abstracta de las tablas de una base de datos relacional. En este tipo de bases de datos, las tablas son conjuntos de filas, cada una de ellas identificada unívocamente mediante una clave. Las bases de datos optimizan la búsqueda de filas a partir de identificadores o claves (o de otros índices que especifique el/la usuario/a). Eso mismo es lo que hace un diccionario.

9.2. Implementación del TAD Diccionario mediante árboles binarios de búsqueda

Pasamos ahora a implementar las operaciones presentadas en la sección anterior. Queremos realizar búsquedas por clave de manera eficiente. Por tanto, parece razonable utilizar el mismo enfoque que hemos utilizado para el TAD Conjunto de la semana pasada, es decir, utilizar árboles binarios de búsqueda.

En el siguiente vídeo se describe cómo hacer esto. La implementación resultante es muy similar a la del TAD Conjunto, con la diferencia de que ahora se comparan claves, en lugar de elementos. Al final del vídeo se introduce una nueva operación operator[], que es similar a la operación at, pero trata de manera diferente los casos en los que la clave a buscar no se encuentra en el diccionario.

▶️ Implementación del TAD Diccionario mediante ABBs (12:52)

📄 Código fuente

if (dicc.contains(palabra)) {
    dicc.at(palabra)++;
} else {
    dicc.insert({palabra, 1});
}

dicc[palabra]++;

9.2.1. Relaciones de orden en árboles binarios de búsqueda

Las mayoría de clases que hemos visto en este curso son paramétricas. Por ejemplo, tenemos SetTree<T>, donde T representa el tipo de los elementos del conjunto. En la mayoría de ejemplos que hemos visto, este tipo T ha sido int o string. Es decir, hemos trabajado con conjuntos de enteros o de cadenas de texto. Con los diccionarios pasa algo similar. El tipo MapTree<K, V> es paramétrico con respecto al tipo de las claves K y el tipo de los valores V. Hasta ahora hemos tratado con tipos básicos como claves (int y string). Pero, ¿qué pasa si tenemos un diccionario cuyas claves son objetos definidos por el/la programador/a? Observa el siguiente código:

💻 Diccionarios con claves compuestas (1)

¡Se obtiene un error de compilación al descomentar la segunda parte del código! El siguiente vídeo explica por qué se produce este error y cómo solucionarlo. A partir del minuto 7:10 se cuentan algunos detalles de implementación, que son más técnicos, y no es necesario conocerlos.

▶️ Relaciones de orden en ABBs (8:29)

📄 Código fuente (TAD Diccionario)

📄 Código fuente (TAD Conjunto)

9.3. Recorridos iterativos e iteradores sobre árboles binarios

Detenemos un poco nuestro estudio de los diccionarios para volver a un aspecto de los recorridos en un árbol binario que tenemos pendiente. Vamos a centrarnos en los recorridos en inorden de un árbol binario. Hasta ahora teníamos una implementación recursiva bastante concisa:

void inorder(const NodePointer &node) {
  if (node != nullptr) {
    inorder(node->left, func);
    visitar node->elem;
    inorder(node->right, func);
  }
}

El objetivo de esta sección es obtener una implementación equivalente, pero que no utilice recursión. Es decir, una implementación que recorra el árbol mediante un bucle.

¿Para qué queremos una implementación iterativa? Si recordáis, cuando estudiábamos el TAD Lista habíamos estudiado los iteradores, que nos permiten recorrer una lista o cualquier otro TAD secuencial. Sería útil poder utilizar iteradores también para recorrer conjuntos o diccionarios. El recorrido que haría el iterador sería similar al recorrido en inorden del árbol correspondiente. Sin embargo, no es fácil implementar las funcionalidades de los iteradores a partir de una implementación recursiva como la anterior. Es más fácil inspirarse en una implementación iterativa. Al fin y al cabo, el recorrido de un iterador es como un bucle, donde cada operación de avanzar el iterador es similar a una iteración de ese bucle.

Por desgracia, recorrer un árbol binario de manera iterativa es bastante más complicado que recorrer una lista. ¿Por qué?. Cada vez que recorríamos una lista, teníamos un puntero al "nodo actual". Pasar al siguiente nodo era relativamente fácil; cada nodo tiene un puntero al siguiente elemento en el recorrido. Pero ahora tenemos árboles, que no son tan "lineales". Supongamos que estamos situados en un nodo determinado, y que ahora queremos pasar al siguiente del recorrido en inorden. ¿Dónde está el nodo siguiente? ¿Es uno de los hijos? ¿Es su padre?. Depende.

Con esta información, ahora vamos a ver cómo implementar un recorrido en inorden en un árbol binario de manera iterativa. Para ello vamos a necesitar una pila auxiliar.

▶️ Recorrido en inorden iterativo (1) (10:01)

📄 Código fuente

Para los propósitos de este curso, basta con conocer el algoritmo de recorrido iterativo. No obstante, resulta legítimo preguntarse cómo se ha llegado a ese algoritmo, y si realmente el algoritmo equivale a hacer un recorrido en inorden. Pues bien, es posible derivar este algoritmo iterativo partiendo de su versión recursiva y utilizando una serie de transformaciones elementales. Este mecanismo, además, puede ser aplicado a una gran clase de funciones en las que se hagan dos llamadas recursivas. El siguiente vídeo explica, paso a paso, cómo se transforma la versión recursiva del recorrido en inorden en una versión iterativa:

▶️ Recorrido en inorden iterativo (2) (Opcional - 16:22)

Pues bien, ya tenemos un algoritmo iterativo de recorrido en inorden. El último paso consiste en implementar las operaciones de los iteradores para recorrer árboles binarios:

▶️ Iteradores en árboles binarios (5:26)

📄 Código fuente (TAD Árbol Binario)

📄 Código fuente (TAD Conjunto)

📄 Código fuente (TAD Diccionario)

9.4. Problemas de laboratorio