SICP Exercise 2.66: Looking up Data

Implement the lookup procedure for the case where the set of records is structured as a binary tree, ordered by the numerical values of the keys.

First, let's define our record structure. To keep it simple, a record will be a list, with the numerical value of the key held at the head of the list. This means we can define key as follows:

(define (key record)
  (car record))

Then we can simply take element-of-set? and make the following modifications to it:

• Instead of checking whether the entry matches the required value, it will check whether the value returned by applying key to the entry matches the requested key.
• If it finds the requested entry then, instead of returning true, it will return the entry itself.
• The recursive calls will need to pass the requested key through.
• To save us having to extract the key of the entry of the current node each time, if the current node isn't null then we'll extract it once.

Here's element-of-set? again as a reminder:

(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)))))

...and here's my version of lookup:

(define (lookup given-key set-of-records)
  (if (null? set-of-records)
      #f
      (let ((entry-key (key (entry set-of-records))))
        (cond ((= given-key entry-key) (entry set-of-records))
              ((< given-key entry-key)
               (lookup given-key (left-branch set-of-records)))
              ((> given-key entry-key)
               (lookup given-key (right-branch set-of-records)))))))

Right, let's put it to the test:

         
> (define records (list->tree '((1 one) (2 two) (4 four) (5 five) (7 seven) (10 ten))))
> records
'((4 four) ((1 one) () ((2 two) () ())) ((7 seven) ((5 five) () ()) ((10 ten) () ())))
> (lookup 1 records)
'(1 one)
> (lookup 4 records)
'(4 four)
> (lookup 7 records)
'(7 seven)
> (lookup 3 records)
#f

SICP Exercise 2.65: Unioning and Intersection Binary Search Trees

Use the results of exercises 2.63 and 2.64 to give Θ(n) implementations of union-set and intersection-set for sets implemented as (balanced) binary trees.

Okay, so in exercise 2.63 we established that the procedure tree->list-2 is an Θ(n) procedure, and in exercise 2.64 we established that list->tree is also an Θ(n) procedure. This means that we can convert a balanced binary tree to a list and back again in Θ(n). Further to this, we can convert a balanced binary tree to a list, transform that list into another list, and then convert the resulting list to a balanced binary tree and, provided the transformation of the list is no worse than Θ(n), we can do all this in Θ(n).

If we assume that we're dealing with binary search trees, and not just binary trees, as the authors imply, then we know that tree->list-2 will produce an ordered list. We also know that, given an ordered list, list->tree will produce a balanced binary search tree. So one way of achieving our goal would be to take the balanced binary search trees to be unioned or intersected, convert them to ordered lists using tree->list-2, perform the union or intersection on the ordered lists, and then convert the resulting set back to a balanced binary search tree using list->tree.

If only we had some way of performing union-set and intersection-set on ordered list representations with Θ(n) growth. Oh look! We produced such a union-set in exercise 2.62, and the authors give us such an intersection-set in the "Sets as ordered lists" section. It's almost like that was planned...

Okay, so what we'll do is we'll convert these previously defined procedures to inner procedures in the corresponding union-set and intersection-set procedures for binary trees:

(define (union-set set1 set2)
  (define (union s1 s2)
    (cond ((null? s1) s2)
          ((null? s2) s1)
          (else (let ((x1 (car s1))
                      (x2 (car s2)))
                  (cond ((= x1 x2) (cons x1 (union (cdr s1) (cdr s2))))
                        ((< x1 x2) (cons x1 (union (cdr s1) s2)))
                        ((< x2 x1) (cons x2 (union s1 (cdr s2)))))))))
  (let ((list1 (tree->list-2 set1))
        (list2 (tree->list-2 set2)))
    (list->tree (union list1 list2))))

(define (intersection-set set1 set2)
  (define (intersect s1 s2)
    (if (or (null? s1) (null? s2))
        '()    
        (let ((x1 (car s1)) (x2 (car s2)))
          (cond ((= x1 x2) (cons x1 (intersect (cdr s1) (cdr s2))))
                ((< x1 x2) (intersect (cdr s1) s2))
                ((< x2 x1) (intersect s1 (cdr s2)))))))
  (let ((list1 (tree->list-2 set1))
        (list2 (tree->list-2 set2)))
    (list->tree (intersect list1 list2))))

Okay, so let's see these in action:

> (define odd-set (list->tree '(1 3 5)))
> (define even-set (list->tree '(2 4 6)))
> (define low-set (list->tree '(1 2 3 4)))
> (define high-set (list->tree '(3 4 5 6)))
> odd-set
'(3 (1 () ()) (5 () ()))
> even-set
'(4 (2 () ()) (6 () ()))
> low-set
'(2 (1 () ()) (3 () (4 () ())))
> high-set
'(4 (3 () ()) (5 () (6 () ())))
> (intersection-set odd-set odd-set)
'(3 (1 () ()) (5 () ()))
> (intersection-set odd-set even-set)
'()
> (intersection-set even-set odd-set)
'()
> (intersection-set low-set high-set)
'(3 () (4 () ()))
> (union-set odd-set odd-set)
'(3 (1 () ()) (5 () ()))
> (union-set odd-set even-set)
'(3 (1 () (2 () ())) (5 (4 () ()) (6 () ())))
> (union-set even-set odd-set)
'(3 (1 () (2 () ())) (5 (4 () ()) (6 () ())))
> (union-set low-set high-set)
'(3 (1 () (2 () ())) (5 (4 () ()) (6 () ())))

SICP Exercise 2.64: Constructing Balanced Trees

The following procedure list->tree converts an ordered list to a balanced binary tree. The helper procedure partial-tree takes as arguments an integer n and list of at least n elements and constructs a balanced tree containing the first n elements of the list. The result returned by partial-tree is a pair (formed with cons) whose car is the constructed tree and whose cdr is the list of elements not included in the tree.

(define (list->tree elements)
  (car (partial-tree elements (length elements))))

(define (partial-tree elts n)
  (if (= n 0)
      (cons '() elts)
      (let ((left-size (quotient (- n 1) 2)))
        (let ((left-result (partial-tree elts left-size)))
          (let ((left-tree (car left-result))
                (non-left-elts (cdr left-result))
                (right-size (- n (+ left-size 1))))
            (let ((this-entry (car non-left-elts))
                  (right-result (partial-tree (cdr non-left-elts)
                                              right-size)))
              (let ((right-tree (car right-result))
                    (remaining-elts (cdr right-result)))
                (cons (make-tree this-entry left-tree right-tree)
                      remaining-elts))))))))

1. Write a short paragraph explaining as clearly as you can how partial-tree works. Draw the tree produced by list->tree for the list (1 3 5 7 9 11).
2. What is the order of growth in the number of steps required by list->tree to convert a list of n elements?

(a) Describe How partial-tree Works
Before we give our short paragraph let's first note what quotient does as it's used here without any description. It's official definition in the Scheme R5RS specification can be found here. However, its functionality can be summarized as returning the result of dividing the first numeric operand by the second numeric operand and, if this is not an integer value, rounding it down to the nearest integer towards zero.

Okay, so given the assumptions about the operands to partial-tree listed above let's now describe how partial-tree works...

In the terminating case, when n=0, partial-tree simply returns a pair containing a representation of an empty binary tree and the unaltered list of elements it was called with (as these elements were not added to the binary tree generated). However, in the non-terminating case partial-tree first calculates the number of elements that should go into the left sub-tree of a balanced binary tree of size n, then invokes partial-tree with the elements and that value which both produces such a sub-tree and the list of elements not in that sub-tree. It then takes the head of the unused elements as the value for the current node, the tail as the potential elements for the right sub-tree and calculates how many elements should go into the right sub-tree of a balanced binary tree of size n. To build the right sub-tree it then invokes partial-tree with the unused elements and the required size of the right sub-tree to build it and get any remaining elements. Finally it builds the balanced tree with the generated components and returns this tree along with any remaining elements.

Note that a more succinct way of putting this would be to say that, for the non-terminating case, partial-tree splits the list into four: elements preceding the (n/2)^th position, the element at the (n/2)^th position, elements between the (n/2)^th position (exclusive) and the n^th position (inclusive) in the list and elements after the n^th position in the list. It then builds binary trees for the first and third of these lists using recursive calls to partial-tree, puts these sub-trees together, along with the element at the (n/2)^th position, to produce a tree and returns this along with the fourth list. However, while this captures the effect of the procedure, it doesn't describe the actual implementation.

I'd like to add a further note to this part of the exercise. The authors state that "list->tree converts an ordered list to a balanced binary tree". I'd like to correct this a little... list->tree will convert any list into a balanced binary tree; however, if the list is ordered then list->tree will convert it into a balanced binary search tree.

As for the tree produced by list->tree for the list (1 3 5 7 9 11), well here's the procedure in action:

> (list->tree '(1 3 5 7 9 11))
'(5 (1 () (3 () ())) (9 (7 () ()) (11 () ())))

If, as in the book, we omit empty lists from the tree diagram, then this gives us the following tree:

(b) Order of Growth
First, lets make the assumption that all of the list and pair operations (i.e. car, cdr, cons and list) are Θ(1) operations. I include list in this as make-tree uses it.

Now, excluding the recursive calls, partial-tree performs a fixed set of these operations for each list it processes. As a result we can say that, excluding recursive calls partial-tree runs in constant time (i.e. Θ(1)). We also know that, due to the way in which partial-tree operates, it makes recursive calls such that uses each index in the range 1..n exactly once. Now if you perform n invocations of an Θ(1) operation that gives you an order of growth of Θ(n).

Finally, list->tree simply makes a single call to partial-tree using the length of the list of elements as n. If we make a further assumption that length is, in the worst case, Θ(n) (i.e. if it has to iterate through the list and count all the elements), then this means that list->tree is Θ(n).