## **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

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