(define (atom? x) (not (pair? x)))
(define (entry tree-node) (car tree-node))
(define (left-branch tree-node) (cadr tree-node))
(define (right-branch tree-node) (caddr tree-node))
(define (make-tree-node root left right) (list root left right))


(define (make-table)
  (make-tree-node nil nil nil))

(define (lookup key table)
  (define (current-entry) (entry table))
  (define (current-entry-key) (car (current-entry)))
  (define (current-entry-value) (cadr (current-entry)))
  (cond ((equal? table nil) nil)
	((equal? (current-entry) nil) nil)
	((equal? (current-entry-key) nil) nil)
	((equal? (current-entry-key) key) (current-entry-value))
	((< key (current-entry-key)) (lookup key (left-branch table)))
	(else (lookup key (right-branch table)))))

(define (insert! key value table)
  (define (current-entry node) (car node))
  (define (current-entry-key node) (car (current-entry node)))
  (define (current-entry-value node) (cadr (current-entry node)))
  (define (assoc key records)
    (let ((mynewnode (make-tree-node (list key value) nil nil)))
      (cond ((null? (current-entry records)) (set-car! records (list key value)))
	    ((equal? key (current-entry-key records)) nil)
	    ((< key (current-entry-key records))
	     (cond ((null? (left-branch records))
		    (set-cdr! records (list mynewnode (caddr records))))
		   (else (assoc key (left-branch records)))))
	  (else 
	   (cond ((null? (right-branch records))
		  (set-cdr! (cdr records) (list mynewnode)))
		 (else (assoc key (right-branch records))))))))
  (let ((record (assoc key table)))
    (cond (record (display "key inserted: ") table)
	  (else (display "key already exists: ") nil))))

(define mytable (make-table))

(insert! 10 'ten mytable)
(insert! 5 'five mytable)
(insert! 13 'thirteen mytable)
(insert! 3 'three mytable)
(insert! 6 'six mytable)
mytable
(lookup 10 mytable)
(lookup 5 mytable)
(lookup 6 mytable)
(lookup 13 mytable)
(lookup 3 mytable)
mytable
(lookup 0 mytable)
(insert! 3 'three mytable)