Adding Deletion to Your Search Tree

Back in Week 9 Lesson 1, we discussed how to implement deletion in a binary search tree. In this optional part of Homework 7, you'll implement deletion in your TreeSet<T> class template. By convention, in C++ standard library containers, the deletion method is called erase, so you'll be adding a method with the following signature to your TreeSet<T> class template:

bool erase(const T& key);

Basic Erase (No Rebalancing)

Just like insert, your code for erase will be simplified if before calling your recursive deletion helper function, you check whether the key is present in the tree using your existing exists method. If the key is not present, erase should simply return false. If the key is present, erase should call your recursive deletion helper function to remove the node containing key from the tree, and then return true. (This ordering makes the logic for updating the sizes of nodes easier, because you know that the key is present and thus that the size will definitely decrease by one.)

You'll need to add the following private static helper functions to your TreeSet<T> class template:

static void nodeErase(Node*& here, const T& key);

A recursive helper function that searches for the node containing key and removes it from the tree.

• If the node to be deleted has no children, simply delete it and set the passed pointer to nullptr.
• If the node to be deleted has one child, delete it and set the passed pointer to point to the child.
• If the node to be deleted has two children, find and remove the node's in-order successor (the node with the smallest key in the right subtree via removeMin below); replace the to-be-erased node with that node, giving it the children of the current node; and then delete the to-be-erased node.

static Node* removeMin(Node*& here);

A helper function that finds and removes the node with the minimum key in the subtree rooted at here, returning a pointer to that node.

Adding Balancing After Deletion (Optional)

If you've implemented weight-balanced insertion as part of the optional work in this assignment, you can also extend your deletion code to maintain the weight-balance property after deletions. All you need to do is add balanceLeft and balanceRight to both or your helper functions. Call balanceLeft when the left subtree may be too small, and balanceRight when the right subtree may be too small. (Specifically, after deleting a node from the left subtree, call balanceLeft, and after deleting a node from the right subtree, call balanceRight.)

There is an algorithm for deletion in randomized BSTs, but it needs a different deletion approach involving a joinLR helper function. You can look that up if you're interested, but implementing it would be a step further down the rabbit hole than we'd reasonably expect for this assignment. But if you really want, you can try implementing it!

Testing Deletion

You'll want to add tests for deletion to your treeset-test.cpp file. Here are some ideas for tests you could write:

• Test deleting a leaf node.
• Test deleting a node with one child.
• Test deleting a node with two children.
• Test deleting the root node.
• Test deleting a non-existent node.

The sample solution does support erase (including both weight-balanced and randomized versions), so you can leave your tests in place when you submit your homework if you like.

Say What You Did…

Don't forget to include a description of what you did in your Fun.md file!

(When logged in, completion status appears here.)