Semana 8 - Árboles binarios de búsqueda y el TAD Conjunto

8.1. Operaciones del TAD Conjunto

Esta semana comenzamos con un nuevo tipo abstracto de datos para almacenar colecciones de elementos: el TAD Conjunto. Para ello, utilizamos el enfoque de siempre: identificamos un modelo al que se le asocian un conjunto de operaciones.

▶️ El TAD Conjunto - operaciones (6:18)

Es esencial conocer la diferencia entre los conjuntos y las listas. Existen varias propiedades que los diferencian. En primer lugar, el contenido de una lista depende del orden en el que insertemos los elementos. Esto implica que los dos fragmentos de programa que aparecen a continuación no son equivalentes:

list<int> l;
l.push_back(1);
l.push_back(2);

list<int> l;
l.push_back(2);
l.push_back(1);

Por el contrario, en los conjuntos, las inserciones son intercambiables. Los fragmentos que vas a ver a continuación sí son semánticamente equivalentes:

set<int> s;
s.insert(1);
s.insert(2);

set<int> s;
s.insert(2);
s.insert(1);

Otra propiedad que disfrutan los conjuntos, pero no las listas, es el hecho de que la operación de inserción es idempotente. Es decir, los siguientes fragmentos son semánticamente equivalentes:

set<int> s;
s.insert(1);
s.insert(1);

set<int> s;
s.insert(1);

Con las listas no ocurre lo mismo. Si se añade un mismo elemento dos veces al final de una lista, la lista contendrá ambas apariciones del mismo elemento.

8.2. Primera implementación del TAD Conjunto: listas ordenadas

Nuestro primer intento de implementación del TAD Conjunto se basa en el TAD Lista que ya hemos visto anteriormente. La idea consiste en mantener una lista que contenga los elementos del conjunto, evitando tener elementos duplicados. Las tres operaciones básicas de los conjuntos (insertar, eliminar y comprobar la pertenencia de un elemento) requieren hacer una búsqueda por la lista¹, cosa que sabemos hacer.

Ya conocéis, además, que la búsqueda es más eficiente si se hace en una lista ordenada, ya que en estos casos puede utilizarse el algoritmo de búsqueda binaria.

▶️ Implementación del TAD Conjunto mediante listas ordenadas (Opcional - 13:56)

📄 Código fuente

Pese a la relativa sencillez de la implementación, las listas ordenadas no resultan demasiado útiles para implementar el TAD Conjunto, porque hay alternativas mejores. En particular, se obtienen implementaciones más eficientes mediante otros mecanismos como, por ejemplo, los árboles binarios de búsqueda y las tablas hash. En la siguiente sección se describen los árboles binarios de búsqueda. Las tablas hash se estudiarán dentro de dos semanas.

8.3. Árboles binarios de búsqueda

Pasamos a ver una de las estructuras de datos más importantes de este curso: los árboles binarios de búsqueda (ABB).

▶️ Árboles binarios de búsqueda - introducción (12:01)

Un comentario sobre el coste: Resulta fácil ver que la búsqueda tiene coste lineal con respecto a la altura del árbol. También resulta intuitivo el hecho de que la altura, en el caso peor, puede llegar a ser lineal con respecto al número de nodos del árbol (esto pasa, en particular, cuando el árbol es degenerado). No obstante, si el árbol es equilibrado, la altura es logarítmica con respecto al número de nodos del árbol.

Hemos visto cómo se buscan elementos en un ABB. Pasamos a estudiar la inserción de elementos.

Ahora veamos cómo se implementa la inserción en C++:

▶️ Inserción en árboles binarios de búsqueda (9:39)

Pasamos al borrado de elementos en un ABB. Esto es más difícil de lo que parece, sobre todo si eliminamos un nodo interno. De nuevo, es importante que intentes el siguiente ejercicio/cuestionario para poder entender mejor el vídeo que viene después.

Ahora sí, vemos la explicación e implementación en C++:

▶️ Eliminación en árboles binarios de búsqueda (15:31)

El vídeo anterior explica que para borrar un nodo con dos hijos hemos de reemplazar el nodo borrado con el menor de los elementos del hijo derecho. Otra posibilidad podría haber sido reemplazarlo con el mayor de los elementos del hijo izquierdo. Para ello tendríamos que bajar al hijo izquierdo y, desde allí, seguir el camino descendente bajando por los hijos derechos de cada nodo, hasta que no sea posible descender más.

A continuación vamos a ver unos resultados importantes sobre los árboles binarios de búsqueda. En particular, vamos a ver la relación entre el orden de inserción en un ABB y el hecho de que esté equilibrado. Luego veremos las propiedades del recorrido en inorden en un ABB.

De este ejercicio se deduce un aspecto importante sobre el coste de estos algoritmos, que depende de si el árbol sobre el que se aplican está equilibrado o no. A su vez, el hecho de que un árbol esté equilibrado depende del orden en el que se hayan insertado sus elementos. Por ejemplo, si insertamos en un ABB vacío los elementos 5, 1 y 7 (en este orden), obtenemos un árbol equilibrado. Por el contrario, si insertamos en un ABB vacío los elementos 1, 5 y 7 (en ese orden) no obtenemos un árbol equilibrado.

8.4. El retorno del TAD Conjunto

¿Por qué hemos estado hablando tanto de los árboles de búsqueda? Porque son un mecanismo muy útil para implementar el TAD Conjunto, que hemos visto al principio de esta semana, y el TAD Diccionario, que veremos la semana que viene. En el caso de los conjuntos, utilizar árboles binarios de búsqueda supera con creces, en términos de coste asintótico, la eficiencia de la implementación basada en listas ordenadas.

▶️ Implementación del TAD Conjunto mediante ABBs (13:46)

📄 Código fuente

8.5. Problemas de laboratorio