Lab 4, CSC 202
1 Installing a Python Type Checker
2 Binary Search Tree
2.1 To Do
2.1.1 Test Cases
3 Performance measurement
3.1 Optional
8.16.900

Lab 4, CSC 202🔗

For this lab you will implement a binary search tree and explore the implementation of iterators over lists and trees.

Invitation Link

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🔗

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.