Как реализовать набор?

Question

Я хочу реализовать Set в C. Можно ли использовать связанный список при создании SET или мне следует использовать другой подход?

Как вы обычно реализуете свой собственный набор (при необходимости).

Примечание: Если я использую подход «Связанный список», у меня, вероятно, будут следующие сложности для «Установить мои операции»:

• init: O (1);
• уничтожить: O (n);
• вставка: O (n);
• удалить: O (n);
• соединение: O (n * m);
• пересечение: O (n * m);
• разница: O (n * m);
• ismember: O (n);
• issubset: O (n * m);
• setisequal: O (n * m);

O (n * m) может показаться немного большим, особенно для больших данных ... Есть ли способ сделать мой Set более эффективным?

Answer 1

Наборы обычно реализуются либо в виде красно-черных деревьев (для которых элементы должны иметь общий порядок), либо в виде автоматически изменяемого размера хеш-таблицы (для которой требуется хеш-функция).

Последнее, как правило, реализуется за счет двойного размера хэш-таблицы и повторной вставки всех элементов при превышении определенного порога емкости (75% работает хорошо). Это означает, что отдельные операции вставки могут быть O (n), но при амортизации по многим операциям это фактически O (1).

Answer 2

std::set часто реализуется как красное черное дерево: http://en.wikipedia.org/wiki/Red-black_tree

Этот подход значительно улучшит сложность всех перечисленных операций.

Answer 3

В прошлом я использовал красно-черные деревья для построения сетов.

Вот временные сложности из статьи в Википедии.

Пробел O (n)
Поиск O (войти n)
Вставить O (войти n)
Удалить O (log n)

Answer 4

Существует множество способов реализации множества. Здесь - некоторые из них. Кроме того, у MSDN есть очень хорошая статья.

Answer 5

Поскольку у вас уже есть реализованный связанный список, самый простой - это skip list . Если вы хотите использовать сбалансированные деревья, на мой взгляд, самым простым является treap . Это рандомизированные структуры данных, но, как правило, они так же эффективны, как и их детерминированные аналоги, если не больше (и список пропусков можно сделать детерминированным).