binary trees are fast af

 ;; returns false if key not in records, else key 
 (define (lookup given-key set-of-records)  
   (if (null? set-of-records) #f 
       (let ((parent (entry set-of-records))) 
         (cond ((eq? parent '()) #f) 
               ((= given-key parent) parent) 
               (else 
                (lookup given-key 
                        (if (< given-key parent) 
                            (left-branch set-of-records) 
                            (right-branch set-of-records))))))))

LisScheSic

My implementation shares the same basic ideas with meteorgan's.

Based on the book adjoin-set definition, only branches of leaf can be nil. Based on left-branch,right-branch definition, they will just extract nil. So (eq? parent '()) can't occur.

meteorgan

The solution is similar to element-of-set?

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

 (define (lookup given-key set-of-records) 
   (if (null? set-of-records) 
       false 
       (let ((node-entry (entry set-of-records))) 
         (let ((node-key (key node-entry))) 
           (if (= given-key node-key) 
               node-entry 
               (lookup given-key 
                       ((if (< given-key node-key) left-branch right-branch) set-of-records)))))))

chessweb

A record looks like this: ((key value) left-branch right-branch)

 (define (lookup given-key set-of-records)   
   (cond 
     ((null? set-of-records)  
      #f) 
     ((= given-key (entry (car (set-of-records)))) 
      (cadar set-of-records)) ; evaluates to value  
     ((< given-key (entry (car (set-of-records)))) 
      (lookup given-key (left-branch set-of-records))) 
     ((> given-key (entry (car (set-of-records)))) 
      (lookup given-key (right-branch set-of-records)))))

sicp-ex-2.66