[1] If we want to be more formal, we can specify consistent with the interpretations given above to mean that the operations satisfy a collection of rules such as these:
  • For any set S and any object x, is_element_of_set(x,S) is true (informally: Adjoining an object to a set produces a set that contains the object).
  • For any sets S and T and any object x, is_element_of_set(x,union_set(S,T)) is equal to is_element_of_set(x,S) || is_element_of_set(x,T) (informally: The elements of union(S,T) are the elements that are in S or in T).
  • For any object x, is_element_of_set(x,null) is false (informally: No object is an element of the empty set).
[2] Halving the size of the problem at each step is the distinguishing characteristic of logarithmic growth, as we saw with the fast-exponentiation algorithm of section 1.2.4 and the half-interval search method of section 1.3.3.
[3] We are representing sets in terms of trees, and trees in terms of lists—in effect, a data abstraction built upon a data abstraction. We can regard the functions entry, left_branch, right_branch, and make_tree as a way of isolating the abstraction of a binary tree from the particular way we might wish to represent such a tree in terms of list structure.
[4] Examples of such structures include B-trees and red-black trees. There is a large literature on data structures devoted to this problem. See Cormen, Leiserson, and Rivest 1990.
[5] Exercises 2.632.65 are due to Paul Hilfinger.
2.3.3 Example: Representing Sets