Download the archive pp10.zip. It contains all the files for this project.
We discussed a binary search tree implementation (in bst.py). It uses recursion to implement insertion and deletion of nodes in the tree. This is natural and elegant, but has a drawback: When the tree is too unbalanced, we may encounter a runtime stack overflow.
Your task is to create a new implementation in nrbst.py that does not use recursion for insertion and deletion. Instead of using recursion, use a reference to a node to walk down the tree, and to modify the tree when you found the place of insertion or deletion.
In the file nrbst.py, modify only the methods of the _Node class marked with the NotImplementedError exception. You can create additional private methods of the _Node class, but do not modify the existing methods or the dict class.
You can use the script treetest.py to execute a number of tree operations. Change the import statement at the top to use either the bst or your new nrbst module.
Test that nrbst can handle very unbalanced trees, where bst will crash with a stack overflow error.
Note that string conversion of your tree (which uses the _description method of the _Node class) is still recursive and will fail on large unbalanced trees. This is okay, since we use this method only for debugging.
The unit tests test_nrbst.py test your tree implementation by comparing that it creates trees that are identical to the one created by bst.py.
Submission: Upload your file nrbst.py to the submission server.
In this project we work on an implementation of an immutable binary search tree in bst.py. Start by reading the code: the binary search tree (with node class _Node) is used to implement a Set data type, but this set is immutable (like Python's frozenset). Once a Set object has been created, the collection of elements in the set can no longer be changed. However, we can use the + and - operators to create new sets:
>>> from ibst import Set >>> s = Set() >>> s1 = s + 7 >>> s  >>> s1 7(0) >>> s2 = s1 + 13 + 5 + 29 + 21 >>> s2 5(1) 7(0) 13(1) 21(3) 29(2) >>> s1 7(0) >>> s3 = s2 - 5 >>> s3 7(0) 13(1) 21(3) 29(2)
Your task is to implement three additional operations for Set, namely upper_neighbor, range, and split:
I have already written the methods of the Set class. The actual work is done by private methods of the _Node class marked with the NotImplementedError exception. You need to implement these private methods. Do not change any other method of the _Node class, do not change the Set class at all. (You can add new private methods to the _Node class.)
Here are the requirements:
This works as follows: the method "splits" the subtree rooted at the self node and returns the roots of the two new trees. Use recursion: You need to create a new root node for one of the output trees, attach one of the subtrees of self to it, and recursively split the other subtree of self. (There is also the special case x == self.key which is handled without going into recursion.)
You can use the script setclient.py to execute some set operations and see what the results are. Use the unit tests in test_ibst.py for more stringent testing.
Submission: Upload your file ibst.py to the submission server.