Progamming Assignment #5: Make-Up

Due: 4pm on May 13th

Part I: makeup for assignment 1

This part is to just complete part 3 of the quadtree project as assigned - for a maximum of 60 points.
To turn this in, use: submit 5 quad1.tar
5 extra points can be earned by implementing Samet's deletion method.
An additional 15 points can be earned by implementing an AVL tree rather than a binary search tree for finding the names.
- You must augment the data structure, so that there's a flag for the balance factor,
- also modify the insertion and deletion routines to do rotations if necessary to rebalance the tree.
- Also, you must provide a printing routine DISPLAY-AVL that shows the structure of your AVL tree, clearly listing the balance factor and children of each node.

Part II: makeup for assignments 2-4

To make up for the lisp assignments, you must implement a quadtree in lisp! The basic data structure is provided in the file quad.lisp here, and in the account dt01. You don't need to do a command decoder - just enter the functions in standard lisp form (i.e., function name on the inside, and no commas). Also, use strings for the names of citys (written inside of double quotes).

To turn this in, use: submit 6 quad2.tar
Points: The same as for the original assignment (up to 65 total, including extra-credit).
Display function We don't have a nice drawing program, so instead, you must print a pre-order traversal of the quad-tree. This function will thus be more like list-names, which is an in-order traversal of the bstree. Order the children as follows: NE, NW, SE SW.
string comparison use the functions:
```
 string< string= string> 
```

Using the lisp data structure the commands below will add the nodes chicago, mobile, and toronto to an empty structure. note that you should write functions which test the appropriate conditions before performing these operations. Note also, the use of the let command to get a local variable to use within the body of the let.

* (add "chicago" 35 40)

(let ((new (make-qtnode :name "chicago" :xcoord 35 :ycoord 40)))
  (setq *qtroot* new)
  (setq *bstroot* new)
  )

* (add "mobile" 50 10)

(let ((new (make-qtnode :name "mobile" :xcoord 50 :ycoord 10)))
  (setf (qtnode-se *qtroot*) new)
  (setf (qtnode-rlink *bstroot*) new)
  )

* (add "toronto" 60 75)

(let ((new (make-qtnode :name "toronto" :xcoord 60 :ycoord 75))
      (next (qtnode-rlink *bstroot*)))
  (setf (qtnode-ne *qtroot*) new)
  (setf (qtnode-rlink next) new)
  )

David Traum
Wed Apr 30th 1997