my attempt to do the exercises in sicp.

Monday, July 28, 2008

sicp exercise 2.66

;; Exercise 2.66.  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.

(define false #f)
(define true  #t)

(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 (element-of-set? key set)
  (cond ((null? set) false)
        ((= key (key (entry set))) true)
        ((< key (key (entry set))) (element-of-set? (left-branch set)))
        ((> key (key (entry set))) (element-of-set? (right-branch set)))))

(define (make-record key data)
  (cons key data))
(define (key record)
  (car record))
(define (data record)
  (cdr record))

(define (lookup given-key records)
  (element-of-set? given-key records))

No comments: