Lab 5: BSTMap

In this lab, you need to complete the BSTMap class, a map structure based on Binary Search Trees (BST). You will implement the get and remove functions in BSTMap.h.

1. Open lab folder in VSCode

Follow the instructions from Lab 1 to open the lab folder in VSCode.

The new files in this lab are

2. Get the value in BSTMap given a key

The function get in BSTMap.h returns the value of a given search key in the BSTMap. For example, suppose we have a map m = {"sumomo": 1, "momo": 2, "uchi": 1, "mo": 2, "no": 2}. A call to m.get("momo") should return 2 and a call to m.get("uchi") will return 1.

🍕 Tips: You need to create a private recursive function, e.g. getHelp for the get function. You can look at findHelp and putHelp for inspiration. Avoid “arms length base cases”, i.e., don’t check if left or right is null!

3. Remove a key-value pair from the BSTMap given a key

The function remove in BSTMap.h deletes the key-value pair in the BSTMap given a key. For example, suppose we have a map m = {"sumomo": 1, "momo": 2, "uchi": 1, "mo": 2, "no": 2}. A call to m.remove("momo") should remove the pair "momo": 2 and the resulting m = {"sumomo": 1, "uchi": 1, "mo": 2, "no": 2}. Another call to m.remove("uchi") will remove the pair "uchi": 1 and make m = {"sumomo": 1, "mo": 2, "no": 2}.

🍣 Tips: You need to create a private recursive function, e.g. removeHelp.

❗️ Requirements: In class, we discussed the remove algorithm for 3 cases. In this lab, you should promote the successor for the 3rd case when a node has two children. The autograder will mark implementations promoting the predecessor as incorrect.

4. Build and test

A sample doctest test case is given in main.cpp. You should add your own tests for more comprehensive testing. The test cases will not be used for grading. You can run make clean test to run the doctest cases.

5. Submitting the code

After testing the program locally, you should submit BSTMap.h to the autograding system. There will be 10 test cases in total to evaluate your implementation. For each passing test case, you will get 3 points if there is no memory error and 2 points if there are memory errors.

You may refer to the instructions from Lab 1 for more instructions.