In this lab you will add a method to remove elements from the BST which we wrote in class and thoroughly test your additions. Begin by creating a new Gradle project and downloading the BST.java file from class into it. Removal from a BST is the most complex operation on a data structure we have seen so far. The rules to do so are as follows:
- Node to be removed is a leaf. This is the easiest case, simply remove the node. If the node is the root, be sure to set it to null.
- Node to be removed has one child. In this case, set appropriate child of the parent to the child of the removed node. If the node being removed is the root, update the root to be the child of the removed node.
- Node to be removed has two children. To solve this, you must replace the node’s value with the value of the next greatest node in the tree (its successor). Remember, the next highest value in the tree can be found by getting its right child, then following left children as far as possible (i.e., it’s the minimum value of the node’s right subtree). Once you have replaced this value, you may remove the previously found successor node from its right subtree.
Remember to consider any additional cases which may arise, such as if the tree is empty. With the first two rules, simply updating references to a node’s children is sufficient. In the last one, doing so will delete a subtree so be careful to replace values in that case. To examine each of these cases further, use the data structure visualizer. I also recommend drawing some trees and doing the removal by hand to ensure you understand the process. I would expect this to be an exam question :).
Below is one suggestion for writing the remove method(s). You may do so however you like as long as the method works properly and you follow good practices.
I suggest adding two methods to your BST class:
|
1 2 3 4 5 6 |
// A publicly available method to remove a value from the BST. public void remove(int value) // This method searches the BST to find the appropriate node, then, if it exists, removes it. // Returns the root node after removal. private boolean remove(BSTNode curr, int value) |
You may choose to write additional utility methods, such as, for example, one which finds the minimum value of a subtree. It is a good idea to model your method after the insert and search methods we have already written. A skeleton as follows is reasonable.
|
1 2 3 4 5 6 7 8 9 10 |
private BSTNode remove(BSTNode curr, int value) { if (value < curr.value) curr.left = remove(curr.left, value); else if (value > curr.value) curr.right = remove(curr.right, value); else { // The node has been found, do the removal. } return curr; } |
Once you have finished writing your remove method, create a driver class which tests each case of the removal. Be sure the removal works both in cases where you are and are not removing the root!
After your driver class is complete, show your completed work to the lab TA.