Structure and Interpretation of Computer Programs

(define (intersection-set set1 set2)

  (if (or (null? set1) (null? set2))

      ’()    

      (let ((x1 (car set1)) (x2 (car set2)))

        (cond ((= x1 x2)

               (cons x1

                     (intersection-set (cdr set1)

                                       (cdr set2))))

              ((< x1 x2)

               (intersection-set (cdr set1) set2))

              ((< x2 x1)

               (intersection-set set1 (cdr set2)))))))

To estimate the number of steps required by this process, observe that at each step we reduce the

intersection problem to computing intersections of smaller sets -- removing the first element from 

set1

 or 

set2

 or both. Thus, the number of steps required is at most the sum of the sizes of 

set1

and 

set2

, rather than the product of the sizes as with the unordered representation. This is   (n)

growth rather than   (n

2

) -- a considerable speedup, even for sets of moderate size.

Exercise 2.61.  Give an implementation of 

adjoin-set

 using the ordered representation. By

analogy with 

element-of-set?

 show how to take advantage of the ordering to produce a

procedure that requires on the average about half as many steps as with the unordered representation. 

Exercise 2.62.  Give a   (n) implementation of 

union-set

 for sets represented as ordered lists. 

Sets as binary trees

We can do better than the ordered-list representation by arranging the set elements in the form of a

tree. Each node of the tree holds one element of the set, called the ‘‘entry’’ at that node, and a link to

each of two other (possibly empty) nodes. The ‘‘left’’ link points to elements smaller than the one at

the node, and the ‘‘right’’ link to elements greater than the one at the node. Figure 2.16 shows some

trees that represent the set {1,3,5,7,9,11}. The same set may be represented by a tree in a number of

different ways. The only thing we require for a valid representation is that all elements in the left

subtree be smaller than the node entry and that all elements in the right subtree be larger.

Figure 2.16:  Various binary trees that represent the set { 1,3,5,7,9,11 }.

Figure 2.16:  Various binary trees that represent the set { 1,3,5,7,9,11 }.

---

The advantage of the tree representation is this: Suppose we want to check whether a number x is

contained in a set. We begin by comparing x with the entry in the top node. If x is less than this, we

know that we need only search the left subtree; if x is greater, we need only search the right subtree.

Now, if the tree is ‘‘balanced,’’ each of these subtrees will be about half the size of the original. Thus,

in one step we have reduced the problem of searching a tree of size n to searching a tree of size n/2.

Since the size of the tree is halved at each step, we should expect that the number of steps needed to

search a tree of size n grows as   (

log

 n).

38

 For large sets, this will be a significant speedup over the

previous representations.

We can represent trees by using lists. Each node will be a list of three items: the entry at the node, the

left subtree, and the right subtree. A left or a right subtree of the empty list will indicate that there is no

subtree connected there. We can describe this representation by the following procedures:

39

(define (entry tree) (car tree))

(define (left-branch tree) (cadr tree))

(define (right-branch tree) (caddr tree))

(define (make-tree entry left right)

  (list entry left right))

Now we can write the 

element-of-set?

 procedure using the strategy described above:

(define (element-of-set? x set)

  (cond ((null? set) false)

        ((= x (entry set)) true)

        ((< x (entry set))

         (element-of-set? x (left-branch set)))

        ((> x (entry set))

         (element-of-set? x (right-branch set)))))

Adjoining an item to a set is implemented similarly and also requires   (

log

 n) steps. To adjoin an

item 

x

, we compare 

x

 with the node entry to determine whether 

x

 should be added to the right or to

the left branch, and having adjoined 

x

 to the appropriate branch we piece this newly constructed

branch together with the original entry and the other branch. If 

x

 is equal to the entry, we just return

the node. If we are asked to adjoin 

x

 to an empty tree, we generate a tree that has 

x

 as the entry and

empty right and left branches. Here is the procedure:

(define (adjoin-set x set)

  (cond ((null? set) (make-tree x ’() ’()))

        ((= x (entry set)) set)

        ((< x (entry set))

         (make-tree (entry set) 

                    (adjoin-set x (left-branch set))

                    (right-branch set)))

        ((> x (entry set))

         (make-tree (entry set)

                    (left-branch set)

                    (adjoin-set x (right-branch set))))))

The above claim that searching the tree can be performed in a logarithmic number of steps rests on the

assumption that the tree is ‘‘balanced,’’ i.e., that the left and the right subtree of every tree have

approximately the same number of elements, so that each subtree contains about half the elements of

its parent. But how can we be certain that the trees we construct will be balanced? Even if we start

---