Sets are as fundamental to computer science as they are to mathematics. Whereas mathematical sets are unchanging, the sets manipulated by algorithms can grow, shrink, or otherwise change over time. We call such sets * dynamic*. The next five chapters present some basic techniques for representing finite dynamic sets and manipulating them on a computer.

Algorithms may require several different types of operations to be performed on sets. For example, many algorithms need only the ability to insert elements into, delete elements from, and test membership in a set. A dynamic set that supports these operations is called a * dictionary.* Other algorithms require more complicated operations. For example, priority queues, which were introduced in Chapter 7 in the context of the heap data structure, support the operations of inserting an element into and extracting the smallest element from a set. Not surprisingly, the best way to implement a dynamic set depends upon the operations that must be supported.

In a typical implementation of a dynamic set, each element is represented by an object whose fields can be examined and manipulated if we have a pointer to the object. (Chapter 11 discusses the implementation of objects and pointers in programming environments that do not contain them as basic data types.) Some kinds of dynamic sets assume that one of the object's fields is an identifying * key *field. If the keys are all different, we can think of the dynamic set as being a set of key values. The object may contain

Operations on a dynamic set can be grouped into two categories: * queries*, which simply return information about the set, and

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 *key*[*x*] = *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 fields 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 uses a pointer to an element *x*, not a key value.)

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

MAXIMUM(*S*) A query on a totally ordered set *S* that returns 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 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 the next smaller element in *S*, or NIL if *x* is the minimum element.

The queries SUCCESSOR and PREDECESSOR are often extended 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.