BST 2 (Treaps)
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.
Treap Definition
Recall that a Treap is a node-based data structure with the following properties:
- Each node has both an
item(withkeyandvaluefields) and apriority. - The tree satisfies the binary search tree (BST) property: the key of each node is greater than all keys in its left subtree and less than all keys in its right subtree.
- The tree is a min heap and satisfies the heap property: the priority of each node is less than the priority of its children.
In this lab, you will implement a Treap in Python exploiting the same BST structure that you used in the previous lab. Then, you will extend that base implementation to include aggregate sum information about the subtree from each node.
Task: Fill in bst.py with your implementation from last week’s lab so that we can build on our BST representation. If you did not complete the last lab, ask a TA for code to use.
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.
This time, each node also has a priority field, indicating where the node should lie with respect to the heap property.
Task: Check out the TreapNode class in treap.py and familiarize yourself with its structure (and how it differs from the Node type that you used in the previous lab).
Rotation
The core balancing operations of our treap are rotate_CW (clockwise) and rotate_CCW (counter-clockwise).
These operations are used to maintain the heap property of the tree when nodes are inserted.
Task: Implement the rotate_CW and rotate_CCW methods in treap.py.
Insertion
The insert and insertion_helper methods are very similar to the methods that you wrote in the last lab, except that you will need to maintain the heap property as you insert nodes
using the rotate_CW and rotate_CCW methods. Feel free to reference the provided bst.py file in the stencil code for solution code to these functions.
Task: Implement the insert and insertion_helper methods in treap.py using rotate_CW and rotate_CCW and the BST insert methods as a guide.
Hint: As you work on this portion of the lab, you can run visualizer.py to visualize an example treap as you insert nodes to make sure that the heap/BST properties are maintained.
Feel free to adjust the treap T at the end of the file to test different inputs. This may help you debug your code!
Range Query
Now, what about the range_query operation? Note that the operations that we implemented for the BST only relied on the BST property of the tree.
This means that clearly, range_query should still work the same way as it did in the previous lab.
TA Checkpoint: Test your Treap implementations by running the tests in test_treap.py using pytest.
SummingTreap
We can now extend the Treap to include aggregate sum information about the subtree from each node in a new class called SummingTreap.
Each TreapNode is now a SummingTreapNode that has an additional sum field, which stores the sum of the values of all nodes in the subtree rooted at that node (including the node itself).
Task: Check out the SummingTreapNode class in summing_treap.py.
Task: Implement the update_sum method in summing_treap.py to update the sum field of a node based on the sum fields of its children.
Hint: You should use get_sum to get the sum of the children of a node, and not recursively search the tree! This is what allows us to query sums efficiently.
Task: Implement the insert_helper, rotate_CW, and rotate_CCW methods in summing_treap.py by
calling their respective Treap.insert_helper, Treap.rotate_CW, and Treap.rotate_CCW methods and then updating the sum of nodes appropriately.
TA Checkpoint: Test your SummingTreap implementations by running the tests in test_summing_treap.py using pytest, and show your TA your implementation.
Note that tests involving range_sum will not yet pass, since you will implement those next!
Range Sum
Finally, we can implement the range_sum method in SummingTreap to query the sum of the values of all nodes in the tree with keys in the range [low, high].
Task: Implement the range_sum_helper, range_sum_le, and range_sum_ge methods in summing_treap.py.
Final TA Checkpoint: Test your SummingTreap implementations by running the tests in test_summing_treap.py using pytest, and show your TA your implementation.
At this point, all of your tests should pass!