Programming project 10

Download the archive pp10.zip. It contains all the files for this project.

Part 1: Non-recursive BST

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.

Part 2: Immutable BST

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:

1. The method upper_neighbor(x) returns the upper neighbor of \(x\) in the Set (\(x\) may or may not be an element of the set). The upper neighbor is defined as the smallest element \(y\) in the set such that \(y > x\). If no such element exists, the methods must raise a KeyError(x).
2. The method range(low, high) returns a list of all elements \(x\) in the set with low <= x < high in sorted order (low and high are not necessarily elements of the set).
3. The method split(x) "splits" the set and returns two new sets (as a pair), while the original set remains unchanged. The first result set contains all the elements of the set that are less than or equal to \(x\), the second result set contains all the elements of the set that are larger than \(x\). The value \(x\) is not necessarily an element of the set.

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:

• _upper_neighbor(x): Your implementation must work in time \(O(h)\), where \(h\) is the height of the tree. There is a recursive solution, there is also a solution without recursion that uses only a single walk down the tree.
• _range(low, high): Your method must have running time \(O(h + k)\), where \(h\) is the height of the tree, and \(k\) is the length of the returned list. Use recursion.
• _split(x): The method must run in time \(O(h)\), where \(h\) is the height of the tree. So you cannot simply collect the elements and build two new trees: You must compose the new trees from subtrees of the original tree.

  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.