BST (Basic)
Github Classroom
You can clone the starter files for this lab at this GitHub Classroom link. Be sure to open the assignment in VSCode and setup up your virtual environment following these instructions.
BST Definition
Recall from lecture that a BST (binary search tree) is a node-based data structure that maintains the following properties:
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
In this lab, you will implement a basic (unbalanced) BST in Python.
Nodes and Items
For this lab, you will use a similar node abstraction as in class. Each node has a left and right child, as well as an item value, which itself has key and value fields.
Task: Check out the Node and Item classes in bst.py and familiarize yourself with their structure.
Insertion
Most of the code that you will write in this lab should be familiar from lecture. The insert operation is no exception, which should use the insertion_helper to recursively compare the key of the new item with
the keys of other nodes in the tree to find where it should be inserted.
Task: Implement the insert and insertion_helper methods in bst.py.
Hint: At the bottom of bst.py, you can see an example of how create and work with a BST object.
Feel free to modify the calls here and run bst.py to test your implementation as you work on it!
TA Checkpoint: Test your insert method by running the tests in test_bst.py.
Make sure that the test for only insert pass (since you haven’t implemented delete or range_query).
Show a TA your insert and insertion_helper code and briefly explain how it works.
Deletion
The delete operation is a bit more complex than insert. You will need to handle three cases:
- The node to be deleted has no children.
- The node to be deleted has one child.
- The node to be deleted has two children.
Feel free to check out the lecture notes from February 21st for a reminder on how to handle these cases!
Task: Implement the delete and deletion_helper methods in bst.py.
TA Checkpoint: Show a TA your visualization of the treap and explain how the priority function affects the tree.
Make sure that the test for only delete pass (since you haven’t implemented range_query).
Show a TA your delete and deletion_helper code and briefly explain how it works.
Range Query
The range_query operation generates all of the keys in the tree between two keys k_lower and k_upper.
You should implement range_query as an iterator using Python’s yield keyword.
When you want to yield a single item, you can use yield [item].
When you want to yield all the items from another iterator or a list, you can use yield from [iterator]. This may be useful for recursive calls to your helper function!
Task: Implement the range_query_helper method in bst.py.
Final TA Checkpoint: Show a TA your range_query_helper code and briefly explain how it works.
Make sure all of the tests in test_bst.py pass.
Show a TA your range_query_helper code and briefly explain how it works.