sicp-ex-2.66

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 if we have no nil key (if we have nil key, then we need to change "branches of leaf" to differentiate whether we reach the branches of leaf or nil-key parent). Based on left-branch,right-branch definition, they will just extract nil. So (eq? parent '()) can't occur since (null? set-of-records) doesn't meet.

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

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