MIT 6.001                                       Fall, 1997
Instructor: A. Meyer                            T.A.: A Chefter

        Recitation #7, Notes for Fri., 10/10/97

We met in the hall today because physical plant left us locked out of our
classroom.  We had a worthwhile recitation anyway.

We began by observing why the MYSTERY procedure of Quiz 1 took theta(n^2)
steps:

The INSERT procedure takes theta(n) steps to insert into a list of length
n an element larger than any in the list (because the large element must
be inserted at the end of the list).  In the worst case, MYSTERY starts
with a length n list in decreasing order and INSERTs it elements into a
list it builds up starting from the empty list.  Each INSERT costs at most
theta(n) steps, and there are n INSERTs, so the cost is AT MOST
theta(n^2).  On the other hand, n/2 of the INSERTs are into a list of size
at least n/2, so the cost is AT LEAST theta(n/2 * n/2).  Therefore, the
cost really is theta(n^2).

Then we sat on the floor and worked on

IN-HALL-ON-FLOOR EXERCISE:
The section was reminded about the ordered binary tree structure for
representing a set of numbers described in the Tuesday 10/7 lecture, and
in particular was told how to insert a number into such a tree by going
down the tree following the left branch when the inserted node was smaller
than the current node and the right branch when it was larger.  The
exercise then was:

** write the recursive procedure INSERT-INTO-TREE (also called ADJOIN-SET)
   which does this, using

** abstract number-labelled binary trees, with appropriate abstract tree
   operations,

** state the "contract" these abstract tree ops should satisfy, and
   finally

** implement the abstract tree ops.


SOLUTION.  The solution is in SICP pp.156-7.  Here's the version we
developed in class:

We define constructors MAKE-TREE and selectors GET-VAL, GET-LEFT,
GET-RIGHT. The contract for these selectors and constructors is:

(get-val   (make-tree val left right)) => val
(get-left  (make-tree val left right)) => left
(get-right (make-tree val left right)) => right


We also need to define an EMPTY-TREE and an observer EMPTY-TREE?,
with the following contract:

(empty-tree? empty-tree))		 => #t
(empty-tree? (make-tree val left right)) => #f

Now we can write the ADJOIN-SET procedure:

(define (adjoin-set val tree)
  (cond ((empty-tree? tree)
         (make-tree val empty-tree empty-tree))
        ((= val (get-val tree)) tree) ;val is already there, so do nothing
        ((< val (get-val tree))
         (make-tree (get-val tree) 
                    (adjoin-set val (get-left tree)) 
                    (get-right tree)))
        (else                         ; val > (get-val tree)
         (make-tree (get-val tree) 
                    (get-left tree)
                    (adjoin-set val (get-right tree))))))


Here is an implementation of tree data structure:

(define empty-tree nil)
(define empty-tree? null?)
(define make-tree list)
(define get-val car)
(define get-left cadr)
(define get-right caddr)