Project five has two foci:
1. Gaining a deeper understanding of binary search trees (BST)
2. Implementing a tree ADT (treap)
1 The Treap Class
You will implement a Treap class, which, as you have learned in lecture, is a binary search tree. The treap’s
priority will follow that of a max heap. The Treap class will support:
• a default constructor.
• a copy constructor.
• an overloaded assignment operator.
• a destructor.
• method to determine if the treap is empty.
• method to get the height of the treap.
• method to search for a key in the treap.
• method to insert a value into the treap with a unique key.
• method to remove a value from the treap.
You are allowed to add private member variables and/or methods in Treap.hpp, but you may not add any
public methods. In addition to the existing include’s, you may use any function from the standard and math
libraries, if desired. Note that the (human) grader will check whether you have actually implemented a
treap and not some other data structure like an array or vector. You will not receive ANY point for this
treap assigment if you do not, well, implement the treap.
Please comment your code and write tests in the student_tests.cpp file using the Catch testing framework.
We will be using an automatic grader to help you determine your assignment’s completeness and correctness.
A portion of each assignment grade will be determined by the number of passing tests as determined by the
autograder, with our evaluation filling in the rest. This means you know before you turn in your submission
that all is well. You can submit to the autograder as many times as you like, but it is rate limited (5 submissions
every hour) to keep you from using it as your compiler.
For this assignment you should upload a zip file containing only the files to the autograder: Treap.hpp,
Treap.txx and student_tests.cpp. There is a build target called “submission” configured by default to
create this file with the correct contents in your build directory.