Dynamic Set

Operations on dynamic sets

Operations on a dynamic set can be grouped into two categories: queries, which simply return information about the set, and modifying operations, which change the set. Here is a list of typical operations. Any specific application will usually require only a few of these to be implemented. SEARCH.S; k/ A query that, given a set S and a key value k, returns a pointer x to an element in S such that x:key D k, or NIL if no such element belongs to S.

INSERT(S, x): A modifying operation that augments the set S with the element pointed to by x. We usually assume that any attributes in element x needed by the set implementation have already been initialized.

DELETE(S, x): A modifying operation that, given a pointer x to an element in the set S, removes x from S. (Note that this operation takes a pointer to an element x, not a key value.)

MINIMUM(S): A query on a totally ordered set S that returns a pointer to the element of S with the smallest key.

MAXIMUM(S): A query on a totally ordered set S that returns a pointer to the element of S with the largest key.

SUCCESSOR(S, x): A query that, given an element x whose key is from a totally ordered set S, returns a pointer to the next larger element in S, or NIL if x is the maximum element.

PREDECESSOR(S,x): A query that, given an element x whose key is from a totally ordered set S, returns a pointer to the next smaller element in S, or NIL if x is the minimum element.

In some situations, we can extend the queries SUCCESSOR and PREDECESSOR so that they apply to sets with nondistinct keys. For a set on n keys, the normal presumption is that a call to MINIMUM followed by n - 1 calls to SUCCESSOR enumerates the elements in the set in sorted order.

We usually measure the time taken to execute a set operation in terms of the size of the set.