2.3.3 · Representing sets

One set interface can exploit several structural promises.

Compare unordered lists, ordered lists, and binary search trees while keeping membership and adjoin questions separate from representation-specific traversal.

Guiding question

Which operations become cheaper when a set representation promises order or a search-tree shape?

Implement membership and adjoin for an unordered-list set
Use increasing order to stop membership early and insert in place
Follow one branch at each binary-search-tree comparison
Convert a tree set to an ordered sequence without changing membership meaning
Compare balance and search cost across finite tree shapes

An unordered-list set can place a new element at the front after checking for duplicates. An ordered-list set pays attention to increasing order: if the current element is already larger than the target, membership can stop and adjoin can insert before it. The abstract questions are the same, but the representation invariant changes the process.

A binary search tree stores smaller entries on the left and larger entries on the right. Each comparison chooses one branch instead of scanning every entry. tree->list performs an in-order traversal and recovers an ordered sequence. The balanced hand-built tree demonstrates the search rule, while a one-sided tree exposes a linear path.

SICP code883 of 1,048,576 UTF-8 bytes

(begin
  (define (unordered-member? value set)
    (cond ((null? set) #f)
          ((equal? value (car set)) #t)
          (else (unordered-member? value (cdr set)))))
  (define (unordered-adjoin value set)
    (if (unordered-member? value set)
        set
        (cons value set)))
  (define (ordered-member? value set)
    (cond ((null? set) #f)
          ((= value (car set)) #t)
          ((< value (car set)) #f)
          (else (ordered-member? value (cdr set)))))
  (define (ordered-adjoin value set)
    (cond ((null? set) (list value))
          ((= value (car set)) set)
          ((< value (car set)) (cons value set))
          (else
           (cons (car set)
                 (ordered-adjoin value (cdr set))))))
  (list (unordered-adjoin 3 '(1 3 5))
        (unordered-adjoin 4 '(1 3 5))
        (ordered-member? 4 '(1 3 5 7))
        (ordered-adjoin 4 '(1 3 5 7))))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The list-set program returns ((1 3 5) (4 1 3 5) #f (1 3 4 5 7)). The tree program returns (#t #f (1 3 4 5 7 8 9)).

Trace focus

Compare the unordered scan with the ordered early stop before 5. In ordered-adjoin, find the single insertion point. In the tree, record whether each comparison selects the left or right branch, then contrast that path with the complete in-order traversal used by tree->list.

Try it yourself

Change the program and compare the result.

Implement adjoin-tree and insert 6 into the sample tree. Confirm membership and the ordered tree->list result, then create a deliberately one-sided tree and compare its linear search path with the logarithmic path of a balanced tree.

Show hint

Reuse the same three comparison cases as tree-member?, rebuilding only the branch that receives the new value.

Complete this lesson

0 of 20 lessons complete in this chapter0%