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