Lab 4, CSC 202
For this lab you will implement a binary search tree and explore the implementation of iterators over lists and trees.
1 Installing a Python Type Checker
Let’s try to get a Python type checker installed. See if these instructions are helpful. What? They’re not? Well, work with me, let’s make them better.
2 Binary Search Tree
For this part of the lab you will implement a binary search tree class that is parameterized on the comes_before operation. More specifically, operations on a binary tree are typically discussed in terms of a "less than" relationship that determines if searching through a tree progress to the left child or the right child. This "less than" relationship is typically realized through the use of the < operator to compare integer values. For this lab you will generalize the tree implementation by using a user provided (at the time of creation) function to determine if one value "comes before" another.
In a file named bst.py , implement the following class and functions.
2.1 To Do
Define a BinTree union, that is either a Node or None. The element field in the Node should be of type any.
Define a frozenBinarySearchTree class that includes a comes_before function and also a BinTree.
Define each of the following functions. Nearly all of them will require a helper function that accepts the comparison function as an argument. Use the type Callable[]
is_empty — given a BinarySearchTree, return True if the tree is empty, False otherwise.
insert — given a BinarySearchTree and a value as arguments, insert adds the value to the tree by using the comes_before function to determine which path to take at each node; inserts into the left subtree if the value "comes before" the value stored in the current node and into the right subtree otherwise. You will almost certainly want to write a helper function that accepts the comparison function as another argument.
This function returns the resulting tree.
lookup — given a BinarySearchTree and a value as arguments, lookup returns True if the value is stored in the tree and False otherwise. Note, however, that the tree was not created with an equality comparison function. Instead, you will use the comes_before function to determine if the value appears in the tree. More specifically, when comparing two values, if neither value "comes before" the other, then the values will be considered equal (i.e., for our purposes, (not (a < b) and not (b < a)) -> a = b).
delete — given a BinarySearchTree and a value as arguments, delete removes the value from the tree (if present) while preserving the binary search tree property that, for a given node’s value, the values in the left subtree come before and the values in the right subtree do not. If the tree happens to have multiple nodes containing the value to be removed, only a single such node will be removed.
This function returns the resulting tree.
2.1.1 Test Cases
In a file named bst_tests.py , write test cases to verify that your implementation works correctly for various comes_before functions, including numeric ordering, alphabetic ordering, and euclidean-distance-from-zero for X/Y points.
3 Performance measurement
In a manner similar to Lab 3, test the performance of insertion and search on binary search trees of floating point numbers in the range 0-1, using the standard < ordering. Generate trees by generating random numbers. Test search by looking for random numbers (which are extremely unlikely to appear in a randomly generated tree). Measure times for trees of size 100K, 200K, etc., up to 1M elements. Graph the results as before.
3.1 Optional
In addition, gather statistics for four randomly generated trees of size 1M on the depth of the various branches. That is: graph the distribution of the branch lengths, so you can see how evenly distributed the tree is.