Conjuntos En La Informatica

Los conjuntos pueden implementarse usando diversas estructuras de datos. Con una estructura de datos ideal se comprueba si un objeto se encuentra en el conjunto, además de activarse otras operaciones útiles tales como la iteración sobre todos los objetos del conjunto, la realización de uniones o intersecciones entre dos conjuntos, o la toma del complemento de un conjunto en algún dominio limitado. Cualquier estructura de datos en cadena asociativa puede usarse para implementar un conjunto, dejando que los juegos de claves sean los elementos del conjunto, e ignorando los valores. Gracias a su parecido con las series asociativas, los conjuntos se implementan habitualmente por los mismos medios, es decir, un árbol binario de búsqueda auto-balanceable para conjuntos ordenados (con O (log n) para la mayoría de operaciones), o una tabla hash para conjuntos no ordenados (que tienen O(1) en el caso promedio, pero O (n) en el peor caso, para la mayoría de operaciones). Es posible usar una tabla de hash lineal ordenada para crear conjuntos deterministamente ordenados. Otros métodos generalizados incluyen las cadenas (array). En particular, un subconjunto de enteros 1..n puede ser implementado de manera eficaz como en una matriz de bits con n bits, que además ofrece operaciones de unión e intersección muy eficaces. El filtro Bloom implementa un conjunto por probabilidad, por medio de una muy compacta representación, pero arriesgando una pequeña probabilidad de falsos positivos en interrogantes. Sin embargo, casi ninguna de estas estructuras de datos ofrece operaciones de conjuntos como de unión o de intersección de manera fiable. Para dichas operaciones existen otras estructuras de datos de conjunto más especializadas.

...