1 665c255d 2023-08-04 jrmu (define (entry tree) (car tree))
 2 665c255d 2023-08-04 jrmu (define (left-branch tree) (cadr tree))
 3 665c255d 2023-08-04 jrmu (define (right-branch tree) (caddr tree))
 4 665c255d 2023-08-04 jrmu (define (make-tree entry left right)
 5 665c255d 2023-08-04 jrmu   (list entry left right))
 6 665c255d 2023-08-04 jrmu 
 7 665c255d 2023-08-04 jrmu (define (element-of-set? x set)
 8 665c255d 2023-08-04 jrmu   (cond ((null? set) #f)
 9 665c255d 2023-08-04 jrmu 	((= x (entry set)) #t)
10 665c255d 2023-08-04 jrmu 	((< x (entry set))
11 665c255d 2023-08-04 jrmu 	 (element-of-set? x (left-branch set)))
12 665c255d 2023-08-04 jrmu 	((> x (entry set))
13 665c255d 2023-08-04 jrmu 	 (element-of-set? x (right-branch set)))))
14 665c255d 2023-08-04 jrmu 
15 665c255d 2023-08-04 jrmu (define (adjoin-set x set)
16 665c255d 2023-08-04 jrmu   (cond ((null? set) (make-tree x '() '()))
17 665c255d 2023-08-04 jrmu 	((= x (entry set)) set)
18 665c255d 2023-08-04 jrmu 	((< x (entry set))
19 665c255d 2023-08-04 jrmu 	 (make-tree (entry set)
20 665c255d 2023-08-04 jrmu 		    (adjoin-set x (left-branch set))
21 665c255d 2023-08-04 jrmu 		    (right-branch set)))
22 665c255d 2023-08-04 jrmu 	((> x (entry set))
23 665c255d 2023-08-04 jrmu 	 (make-tree (entry set)
24 665c255d 2023-08-04 jrmu 		    (left-branch set)
25 665c255d 2023-08-04 jrmu 		    (adjoin-set x (right-branch set))))))
26 665c255d 2023-08-04 jrmu 
27 665c255d 2023-08-04 jrmu ;; 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. 
28 665c255d 2023-08-04 jrmu 
29 665c255d 2023-08-04 jrmu (define (lookup given-key set-of-records)
30 665c255d 2023-08-04 jrmu   (if (null? set-of-records)
31 665c255d 2023-08-04 jrmu       #f
32 665c255d 2023-08-04 jrmu       (let ((record (entry set-of-records))
33 665c255d 2023-08-04 jrmu 	    (record-key (key record)))
34 665c255d 2023-08-04 jrmu 	(cond ((= given-key record-key) 
35 665c255d 2023-08-04 jrmu 	       record)
36 665c255d 2023-08-04 jrmu 	      ((< given-key record-key)
37 665c255d 2023-08-04 jrmu 	       (lookup given-key (left-branch set-of-records)))
38 665c255d 2023-08-04 jrmu 	      ((> given-key record-key) 
39 665c255d 2023-08-04 jrmu 	       (lookup given-key (right-branch set-of-records)))))))