¿Cómo implementar un conjunto?

Question

Quiero implementar un conjunto en C. ¿Está bien utilizar una lista vinculada, al crear el SET, o debería usar otro enfoque?

¿Cómo se suele implementar su propio conjunto (si es necesario).

NOTA: Si utilizo el enfoque de lista enlazada, probablemente tendrá las siguientes complejidades de Set mis operaciones:

• init: O (1);
• destroy: O (n);
• inserte: O (n);
• eliminar: O (n);
• unión: O (n * m);
• intersección: O (n * m);
• diferencia: O (n * m);
• ismember: O (n);
• issubset: O (n * m);
• setisequal: O (n * m);

O (n * m) parece que puede ser un poco grande especialmente para datos enormes ... ¿Hay alguna manera de implementar mi Set más eficiente?

Answer 1

He usado árboles rojos y negros en el pasado para construir juegos.

Aquí están las complejidades de tiempo del artículo de Wikipedia.

espacio O (n)
Buscar O (log n)
Insertar O (log n)
Eliminar O (log n)

Answer 2

std::set se suele implementar como un árbol negro rojo: http://en.wikipedia.org/wiki/Red-black_tree

Este enfoque le dará mucho mejor la complejidad de las operaciones enumeradas.

Answer 3

Hay muchas formas de implementar conjuntos. Here son algunos de ellos. Además de MSDN tiene muy buen artículo sobre él.

Answer 4

Como usted ya tiene una lista enlazada en práctica, lo más fácil es a skip list. Si desea utilizar árboles equilibrados, el más fácil en mi opinión es un treap. Estas son estructuras de datos aleatorias, pero en general son tan eficientes como sus contrapartes deterministas, si no más (y una lista de omisiones puede hacerse determinista).

Answer 5

Los conjuntos se implementan típicamente como árboles rojo-negro (que requiere que los elementos tengan un orden total), o como una tabla hash de cambio de tamaño automático (que requiere una función hash).

Esto último se implementa normalmente teniendo la tabla doble de tamaño y reinsertando todos los elementos cuando se supera un cierto umbral de capacidad (75% funciona bien). Esto significa que las operaciones de inserción individuales pueden ser O (n), pero cuando se amortizan en muchas operaciones, en realidad es O (1).