CS 22

Clab 12: Binary Search Trees (BST)

If you have not already done so, make a week4 subdirectory in your cs22 directory (mkdir week4) and move into that directory (cd week4). Now copy all the files from my pub subdirectory: ~cfk/pub/cs22/week4/ as shown below. thyme.cs.swarthmore.edu% pwd /home/chas thyme.cs.swarthmore.edu% cd cs22 thyme.cs.swarthmore.edu% mkdir week4 thyme.cs.swarthmore.edu% cd week4 thyme.cs.swarthmore.edu% cp ~cfk/pub/cs22/week4/* . thyme.cs.swarthmore.edu% ls bigdb.txt ltdb.txt perms.scm queens.scm rost1.txt sets.scm thyme.cs.swarthmore.edu%

The queens file is my solution to the queens problem, the sets file is my solution to clab11 exercises, perms is essentially the permutation procedure discussed in the text on pages 123-124.
Don't bother with them now. Take a look at the contents of ltdb.txt and bigdb.txt. To do this you can use cat or more or less.

Now start up drscheme. Put the following in the definitions window and save it in your week4 subdirectory.

(require-library "trace.ss") (define inport (open-input-file "bigdb.txt")) (define bigdb (read inport)) (close-input-port inport) (define inport (open-input-file "ltdb.txt")) (define litdb (read inport)) (close-input-port inport) Now press the execute button and then evaluate bigdb and litdb in the interaction window. They look like a mess but I'll explain them.

Professor K maintains a database of students in his class as a binary search tree (BST) organized by student number (as key value). bigdb.txt is such a BST with student numbers and homework grades generated by a random number generator. From time to time students ask Professor K what their homework average is. The kind hearted professor has asked you to implement some procedures to handle this and some other tasks. Fortunately for you (at this point in the course), Professor K is so wonderful that no students ever drop his course nor will you ever have to change an existing record. All you have to do is implement the procedures requested in Homework 12 . This is still not simple so start this assignment earlier than the previous ones and make sure you use abstraction barriers. findbykey should be fast because it should exploit the BST property. findbyname will have to possibly look at every node and will not be as fast. This assignment is not exactly like any of the programs on pp. 155-159, but a good understanding of the material there will go a long way to helping you with this assignment.

We'll take a look at litdb together and I'll demonstrate a couple of the functions requested.

Then, do the following exercises for BSTs and sets implemented by them.

  1. exercise 2.63 on page 158
  2. exercise 2.64 on page 159
  3. exercise 2.65 on page 160
Here are the three trees from Figure 2.16. (define tre1 '(7 (3 (1 () ()) (5 () ())) (9 () (11 () ())))) (define tre2 '(3 (1 () ()) (7 (5 () ())(9 () (11 () ()))))) (define tre3 '(5 (3 (1 () () ) ()) (9 (7 () ()) (11 () ())))) Here is code from pages 155-159 define (entry tree) (car tree)) (define (left-branch tree) (cadr tree)) (define (right-branch tree) (caddr tree)) (define (make-tree entry left right) (list entry left right)) (define (element-of-set? x set) (cond ((null? set) #f) ((= x (entry set)) #t) ((< x (entry set)) (element-of-set? x (left-branch set))) ((> x (entry set)) (element-of-set? x (right-branch set))))) (define (adjoin-set x set) (cond ((null? set) (make-tree x '() '())) ((= x (entry set)) set) ((< x (entry set)) (make-tree (entry set) (adjoin-set x (left-branch set)) (right-branch set))) ((> x (entry set)) (make-tree (entry set) (left-branch set) (adjoin-set x (right-branch set)))))) ;; EXERCISE 2.63 (define (tree->list-1 tree) (if (null? tree) '() (append (tree->list-1 (left-branch tree)) (cons (entry tree) (tree->list-1 (right-branch tree)))))) (define (tree->list-2 tree) (define (copy-to-list tree result-list) (if (null? tree) result-list (copy-to-list (left-branch tree) (cons (entry tree) (copy-to-list (right-branch tree) result-list))))) (copy-to-list tree '())) ;; EXERCISE 2.64 (define (list->tree elements) (car (partial-tree elements (length elements)))) (define (partial-tree elts n) (if (= n 0) (cons '() elts) (let ((left-size (quotient (- n 1) 2))) (let ((left-result (partial-tree elts left-size))) (let ((left-tree (car left-result)) (non-left-elts (cdr left-result)) (right-size (- n (+ left-size 1)))) (let ((this-entry (car non-left-elts)) (right-result (partial-tree (cdr non-left-elts) right-size))) (let ((right-tree (car right-result)) (remaining-elts (cdr right-result))) (cons (make-tree this-entry left-tree right-tree) remaining-elts))))))))

ask any questions you may have.