Операции в динамических множествах

Операции динамического множества можно разбить на две категории: запросы (queries) и модифицирующие операции (modifying operation). Запросы просто возвращают информацию о множестве, а модифицирующие операции изменяют множество. В каждом конкретном приложении требуется реализация только некоторых из операций. Практически операции реализуются в виде методов класса множества.

Примеры некоторых запросов приводятся ниже:

1) size возвращает количество элементов в D,

2) isEmpty выдает признак пустого множества, если в D нет элементов,

3) findElement(х) возвращает элемент с ключом, равным х,

4) findAllElements(х) возвращает все элементы с ключами, равными х,

5) minimum возвращает указатель на элемент в D с наименьшим ключом,

6) maximum возвращает указатель на элемент в D с наименьшим ключом.

Перечислим некоторые методы для модифицирующих операций:

1) clear удаляет все элементы из множества,

2) insertItem(p) пополняет заданное множество одним элементом, на который указывает р (обычно предполагается, что выполнена предварительная инициализация полей вставляемого элемента),

3) removeItem(х) удаляет из заданного множества элемент с ключом, равным х,

4) sortingElements сортирует множество D.

Деревья