Представление множеств в ЭВМ

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

Применительно к множествам определение представления подразумевает описание способа хранения информации о принадлежности элементов множеству и описание алгоритмов для вычисления объединения, пересечения и других введенных операций. Выбор представления зависит от целого ряда факторов: особенностей представляемого объекта, состава и относительной частоты использования операций в конкретной задаче и т.д.

Деревья двоичного поиска – основная структура данных для представления множеств, чьи элементы упорядочены посредством некоторого отношения линейного порядка, которые, как правило, обозначают символом “<”. Эти структуры особенно полезны, когда исходное множество такое большое, что не рационально использовать его элементы непосредственно в качестве индексов массивов. Предполагается, что все элементы множеств являются элементами некоторого универсального множества – универсума, примером которого служит множество возможных идентификаторов в программе на языке Pascal. На деревьях двоичного поиска можно реализовать операторы INSERT, DELETE, MEMBER, и MIN, причём время их выполнения в среднем имеет порядок 0(log n) для множеств, состоящих из n элементов. Дерево двоичного поиска – это двоичное дерево, узлы которого помечены элементами множеств, или, другими словами, узлы дерева содержат или хранят элементы множества.