CSE522-Assignment 1 Part 2 Code Reuse in BSTs Solved

Define delete in class AbsTree

 

Preliminaries:  Refer  to BST_Part2.java posted at Resources à Assignments.  It provides the starting point for Part 2.

 

A protected field AbsTree parent field has been added to class AbsTree.   Revise the insert method so that the parent field is correctly set when a value is inserted into the tree.   Define three procedures,  min(), max(), and find(n) which return, respectively, the AbsTree node with the minimum value, the AbsTree node with the maximum value, and the AbsTree node containing the value n.  If n is not present in the tree, find(n) should return null.

 

Defining delete:   Define the delete method so that it works for ordinary trees as well as duptrees.    Similar to insert, the code for delete should be kept in class AbsTree and should capture what is common to trees and duptrees.   The differences in delete’s behavior between Tree and DupTree should be expressed in terms of one or more protected abstract methods which are implemented in the classes Tree and DupTree.  

 

The four cases of delete described in Part 1 also apply here.  Additionally,  when a value n in a duptree has a count 1, the method delete(n) should decrement the count field associated with n but should not delete the node. If a value n is associated with a count == 1, the method delete(n) should remove the node containing value n from the duptree.   

 

Watch the posted screen-cast, A1_Part2.mp4, for a clarification of delete’s behavior.

 

Run your program under JIVE and save the object and sequence diagrams in files called obj2.png and seq2.png, respectively, at the point when all insert and delete operations have been performed by main, but main has not yet exited.  Choose the “Objects with Tables” option for the Object Diagram.

 

Note:  Print out error messages on the Console when the value to be deleted is either not present in the tree or is present at the root of the tree with count == 1 and  both subtrees are null.