Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 2.66

From Drewiki
Jump to: navigation, search

Problem

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.

Solution

In my solution, I chose to represent records as (number . symbol) cons pairs. The datum procedure accesses the datum associated with each key.

(define false #f)
 
(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))
 
(define (key record) (car record))
 
(define (datum record) (cdr record))
 
(define (make-record key datum) (cons key datum))
 
(define (lookup given-key set-of-records)
  (if (null? set-of-records)
      false
      (let ((record (entry set-of-records)))
        (let ((k (key record)))
          (cond ((equal? given-key k) record)
                ((< given-key k)
                 (lookup given-key (left-branch set-of-records)))
                (else
                 (lookup given-key (right-branch set-of-records))))))))

Including the list->tree procedure in the tests makes creating databases easier.

Tests:

(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))))))))
 
(define database
  (list->tree (list (make-record 1 'a)
                    (make-record 5 'e)
                    (make-record 10 'j)
                    (make-record 26 'z))))
 
(lookup 1 database)

Output:

(1 . a)
(lookup 3 database)

Output:

#f
(lookup 10 database>

Output:

(10 . j)
(lookup 15 database)

Output:

#f
(lookup 5 database)

Output:

(5 . e)
(lookup 26 database>

Output:

(26 . z)
Personal tools