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
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
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'.
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
- A node whose datum is None represents an empty general search tree.
- Otherwise, there is at least one key in the datum of a node and the keys are stored in a tuple sorted in ascending order.
- A non-empty node with N keys has N+1 children, which are also general search trees.
- The N+1 children are stored in a tuple in a specific order: If x is key number k in a node's datum, then all the keys in the children GST at position numbers k and below (of the children tuple) are less than x and all those in children GST at position numbers k+1 (of the children tuple) and above are greater than x.
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.