1 665c255d 2023-08-04 jrmu ;; Exercise 3.26.  To search a table as implemented above, one needs to scan through the list of records. This is basically the unordered list representation of section 2.3.3. For large tables, it may be more efficient to structure the table in a different manner. Describe a table implementation where the (key, value) records are organized using a binary tree, assuming that keys can be ordered in some way (e.g., numerically or alphabetically). (Compare exercise 2.66 of chapter 2.) 
 2 665c255d 2023-08-04 jrmu 
 3 665c255d 2023-08-04 jrmu 
 4 665c255d 2023-08-04 jrmu (define (make-tree key value left right)
 5 665c255d 2023-08-04 jrmu   (list key value left right))
 6 665c255d 2023-08-04 jrmu (define (key tree)
 7 665c255d 2023-08-04 jrmu   (car tree))
 8 665c255d 2023-08-04 jrmu (define (value tree)
 9 665c255d 2023-08-04 jrmu   (cadr tree)
10 665c255d 2023-08-04 jrmu (define (left-branch tree)
11 665c255d 2023-08-04 jrmu   (caddr tree))
12 665c255d 2023-08-04 jrmu (define (right-branch tree)
13 665c255d 2023-08-04 jrmu   (cadddr tree))
14 665c255d 2023-08-04 jrmu 
15 665c255d 2023-08-04 jrmu (define (make-table)
16 665c255d 2023-08-04 jrmu   (make-tree '*table* '() '()))
17 665c255d 2023-08-04 jrmu 
18 665c255d 2023-08-04 jrmu (define (assoc key tree)
19 665c255d 2023-08-04 jrmu   (cond ((null? tree) (error "assoc passed empty tree"))
20 665c255d 2023-08-04 jrmu 	((= key (entry tree)) tree)
21 665c255d 2023-08-04 jrmu 	((< key (entry tree)) ...)
22 665c255d 2023-08-04 jrmu 	(else ...)))
23 665c255d 2023-08-04 jrmu   
24 665c255d 2023-08-04 jrmu 
25 665c255d 2023-08-04 jrmu (define (insert! key value table)
26 665c255d 2023-08-04 jrmu   (