Given a collection C of elements, there are three fundamental queries one might ask:
Given a collection C, one often simply wants to know whether the collection already contains a given value, t. The response to such a query is
true if an element exists in the collection that matches the desired target t, or
false if this is not the case.
When complex elements are stored in a collection, the definition of a "matching" element can be based on a key value for the element or a subset of that element's attributes. For example, when searching a collection of information for the department of motor vehicles, one might only need to provide the driver's license number to retrieve the full information for that licensed driver.
It is common to store additional pieces of information for complex structures. One can associate additional information with each key element k in the collection, which can be retrieved (or manipulated) as needed.
For the algorithms discussed in this chapter we assume the existence of a set U that contains values e∈U being sought. The collection C contains elements drawn from U, and the target element being sought, t, is a member of U. If t is instead a key value, then we consider U to be the set of potential key values, k∈U, and the ...