CS61A Homework 7

Due by 11:59 PM on (that is, the end of) Saturday, 7/14

This homework must be submitted online. We do not require a paper copy. If you would like a reader to give you written feedback on your homework, submit a paper copy to the homework box.

To turn in the electronic copy, submit all of your answers in a file named hw7.py. Follow the instructions here to submit the electronic copy.

If you would like, you can use the template file hw7.py. To copy this file to your lab account you can run the command:

      cp ~cs61a/lib/hw/hw07/hw7.py .

to copy it into your current directory.

In this and future homeworks, we have three different categories of questions:

It is our hope that these categories will help guide you in deciding how to divide your time when working on the homeworks.

For the first question of this homework we will work with the binary search tree data abstraction as defined in bst.py. For the third question, we will use a new general search tree data abstraction, provided in gst.py, which uses code from itree.py.

Core Questions

Q1. In this question, we will generalize the idea of binary search trees to handle any method of sorting items. We will generalize the method bst_find to bst_gen_find to handle items more general than simple numbers by using an additional argument compare_fn. compare_fn is a comparison function that takes two values and compares them by returning -1 if the first argument is "less than" the second, 0 if the two are "equal", and 1 if the first argument is "greater than" the second argument. Hint: We have provided the generalized version of bst_insert as bst_gen_insert, which also takes compare_fn as an argument.

Q2. Create a class called VendingMachine that represents a vending machine for some product. A VendingMachine object does not actually return anything but strings describing its interactions. See the class doctest for examples. (In Nanjing, there are even vending machines for live crabs.)

Tip: If you need to a concatenate a string and an integer together, you can use the str constructor to convert the integer to a string. So, for example, str(3) will return the string '3'.

Reinforcement Questions

Q3. Generalize the binary search trees from lecture to search trees with more than two children. We can define a general search tree (GST) as one whose labels are tuples of keys such that

We have provided you a data abstraction for GSTs (which is not a standard term) in gst.py. Using the abstraction provided, fill in the definition of gst_find in hw7.py to search for a key in a GST.

Extra for Experts

Q4. Write a function bst_remove that returns the result of removing a value from a binary search tree, if it is present (maintaining the search-tree property, of course). The function returns the original tree if the value is not present. The time spent should be proportional to the depth of the tree. Hint: This is easy if the node whose label matches the value being deleted contains at most one non-empty child. The tricky part is figuring out what to do when that node has two non-empty children.