CSC 132 Fall 2000

Lab 9

Due: end of lab period 16 November 2000

15 points

"pluck a node from the tree"

For this assignment, you are to implement the "remove" method for the IntTreeBag class. We discussed this class yesterday and it is covered in the textbook on pages 463-475. The remove method is covered on pages 468-472. IntTreeBag has one instance variable, a reference to the root node.

You will need to download three files from the eccentric download folder for Lab 9: IntBTNode.java, IntTreeBag.java and TreeDriver.java. Do not get IntBTNode.java from the textbook website or from Lab 8; there are errors in the code. The IntBTNode documentation is valid and available from Lab 8. Implement the remove method in IntTreeBag.java and submit only that file when you are finished. Do not make any changes to the IntTreeBag class other than this method. IntTreeBag is implemented as a binary search tree (see its add method).

Here is the specification:

public boolean remove(int target)

Parameter: target - the element to remove from the bag
Postcondition: if target was found, one copy of the target is removed.
Returns: true if target was found and removed, false if target is not found.

Before any removal operations can proceed, you have to conduct a search for a node containing the target value. Note that you only need to find one (see postcondition). The search begins at the root, and takes advantage of the fact that the tree is a binary search tree. Conduct this search within remove. If the search succeeds, you need references both to the target node and to its parent. If the search does not succeed, you need only to record the fact that it did not succeed.

TreeDriver.java has been designed to separately test each of the four possible removal situations (see pages 469-470). Here are the four cases.

  1. The target is not found. This is discovered when descending the binary search tree leads to a dead-end (null node) without matching the target value. In this case, return false.
  2. The target is found at the root and the root has no left child. In this case, the right child becomes the new root.
  3. The target is found below the root, but the target node has no left child. In this case, the target node's parent will "adopt" the target node's right child upon removal of the target node. If the target node was a left child, its right child will become its parent's left child. If the target node was a right child, its right child will become its parent's right child.
  4. The target is found and the target node does have a left child. In this case, we want to replace the target node with the node containing the next smaller value -- the rightmost node of the target node's left subtree. This potentially requires changing several links, but there is an easier way. Simply copy the data value from the "rightmost in left subtree" node into the data field of the target node, then remove the "rightmost in left subtree" node. The IntBTNode class provides methods to support both of these operations (getRightmostData, removeRightmost).

 

Implementation hints:

  1. Implement this using iteration rather than recursion.
  2. The remove method will need at least two local variables to be maintained during the search: cursor to keep track of where you are in the tree, and parentOfCursor to keep track of the cursor's parent (to possibly fix links later). Initially, cursor points to the root and parentOfCursor is null. At each step during the search, parentOfCursor will be updated to cursor, and cursor will be updated either to cursor.getLeft() or cursor.getRight() (depending on whether the target value is less than or greater than cursor.getData(). If it is equal, the search is over).
  3. Since IntTreeBag is a client of IntBTNode, you have to use its accessor and modifier methods. The instance variables data, left and right are not directly available.
  4. You must do the search algorithm first!

 

Here is correct output from the driver program:

** testing case 1 : target is not found **
Before remove(22), bag is: 15 18 23 47 52 65
remove returns false, bag is: 15 18 23 47 52 65
** testing case 2 : target at root and no left child **
Before remove(47), bag is: 47 52 57 65
remove returns true, bag is: 52 57 65
** testing case 3a : target is left of its parent but no left child **
Before remove(15), bag is: 15 18 23 47 52 65
remove returns true, bag is: 18 23 47 52 65
** testing case 3b : target is right of its parent but no left child **
Before remove(52), bag is: 15 18 23 47 52 65 76 87
remove returns true, bag is: 15 18 23 47 65 76 87
** testing case 4a : target is left of root and has left child **
Before remove(23), bag is: 15 17 18 22 23 33 47 52 65
remove returns true, bag is: 15 17 18 22 33 47 52 65
** testing case 4b : target is right of root and has left child **
Before remove(65), bag is: 15 18 23 47 52 60 65
remove returns true, bag is: 15 18 23 47 52 60

Each TreeDriver test case starts with a fresh tree, so all test cases are independent of each other. In addition, each test case will catch and absorb any exceptions, so the program will continue running after a badly-mangled test.

The search algorithm plus case 1 combine for 6 points. The other three cases are 3 points each. When finished, submit IntTreeBag.java to your upload folder.

[ Assignments | CSC 132 | Peter Sanderson | Computer Science | SMSU ]

Last reviewed: 15 November 2000

Peter Sanderson ( PeteSanderson@smsu.edu )