Programming project 10

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

Part 1: Non-recursive BST

We discussed a binary search tree implementation (in 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 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, 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 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 your tree implementation by comparing that it creates trees that are identical to the one created by

Submission: Upload your file to the submission server.

Part 2: Immutable BST

In this project we work on an implementation of an immutable binary search tree in 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
>>> s2 = s1 + 13 + 5 + 29 + 21
>>> s2
5(1) 7(0) 13(1) 21(3) 29(2)
>>> s1
>>> 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:

You can use the script to execute some set operations and see what the results are. Use the unit tests in for more stringent testing.

Submission: Upload your file to the submission server.