2.66.rkt

#lang sicp

(define (entry tree) (car tree))

(define (left-branch tree) (cadr tree))

(define (right-branch tree) (caddr tree))

; every entry has a key and a value
(define (entry-key entry) (car entry))
(define (entry-value entry) (cdr entry))

(define (make-entry key value)
  (cons key value))

(define (make-tree entry left right)
  (list entry left right))

; sorted by (numeric) key
(define (adjoin-set key value set)
  (cond ((null? set) (make-tree (make-entry key value) '() '()))
        ((= key (entry-key (entry set))) (error "key exists"))
        ((< key (entry-key (entry set)))
         (make-tree (entry set)
                    (adjoin-set key value (left-branch set))
                    (right-branch set)))
        ((> key (entry-key (entry set)))
         (make-tree (entry set)
                    (left-branch set)
                    (adjoin-set key value (right-branch set))))))

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

(define tree (adjoin-set 1 3 '()))

(define tree2 (adjoin-set 5 6 tree))

(define tree3 (adjoin-set 7 8 tree2))

(entry-value (entry tree3))
(entry-value (entry (right-branch tree3)))
(entry-value (entry (right-branch (right-branch tree3))))

(lookup 7 tree3)