A BST Phone Directory with Removal (25 points)

In order to maintain this tree, you need to be able to do the usual BST operations such as insert and search (here called "Lookup"). However, Cosmodemonic has had high employee turnover lately (the telecommunications industry just isn't what it once was). Therefore you also need to be able to delete entries from the tree. This must be done in a way that preserves the BST properties, which is a bit of a challenge. You also need to provide a method to print out the contents of the tree in alphabetical order.

Input consists of lines of the form "A   <name>" (add an entry; <name> is a string containing the last name of the person), or "R   <name>" (remove the entry for the person with last name <name>; note that the specified name may not be in the directory, in which case you do nothing). The Personnel Department of the Cosmodemonic Telegraph Company has a policy that no two people working there can have the same last name, which simplifies your task somewhat.

Sample Input (sample.dat):

A Mills
A Gomez
A Keaton
A Lindsey
A Thomson
A Pilcher
R Davis
A Waters
A Davis
R Keaton
A Quilty
A Yeager
A Farmer
A North
R Farmer
R Pilcher
R Thomson

Directory
---------
Davis
Gomez
Lindsey
Mills
North
Quilty
Waters
Yeager

You have a bit of help in this endeavor. Some of the design and initial programming work has been done already by your predecessor. The implementation file BST.java and the file Directory.java containing the main method are provided. You are to complete the BST file (be sure to fill in the lines for running times for methods you write) and add a bit of code to Directory file to include removal. Copies of these files are available in the ~csci311/HW06 directory. Copies of the input files sample.dat and input.dat are also available there.

Email your instructor the following files in a message with the subject line CSCI 311 BST Handin:

• your program's output for the input provided in the file input.dat,
• your Directory file (discuss the overall running time for the main method in a comment), and
• your BST file, including running times for the methods you wrote.

Various Hints

The code you have been provided is based on a recursive definition of a BST: a BST is either empty, or it is a node with a key, a left child that is a BST, and a right child that is a BST. With this definition, you can write recursive functions to complete this assignment, and you won't need to keep parent pointers or keep track of parent nodes in your code.

A hint about LookUp(): LookUp() is provided only to give you a model to use in writing Remove(). If you don't think about it carefully, you might think that calling LookUp() to see if an item to be removed is currently in the tree makes sense. However, you can get the same effect by searching in Remove(): If you don't ever get to a node with the desired value, there is nothing to do. Hence calling LookUp() first duplicates work you will do anyway. And if you make Remove() recursive and call LookUp() at the start of every call, you'll do a lot of extra work that will kill your efficiency.

Hints about Remove():

[This is a simplified, easier-to-understand version of the procedure presented on pp. 295-298 in the course text.]

Remove() is the most complicated function you will need to write. As usual, do the design first to simplify things. Note that if you delete a node from a BST, there are three cases you need to consider. The first step in all cases is to find the node that you need to delete (remember, you need to deal with the case when a request is made to delete something that isn't in the tree). Once you find the node to delete, the three cases are as follows:

• The node you are deleting has no children. This is easy: you can just delete the node. Note that the skeletal code provided allows you to do this by setting the data member isEmpty to true.
• The node you are deleting has exactly one child. This is still pretty easy: you replace the node you are deleting with its child. You need to determine whether the child is a left child or a right child, but that's easy. The best way to replace the node is to copy the contents of the child node into it. If you free the node from which you copied the data in order to avoid a data leak, be sure to set left and right to null so you don't recursively delete anything you want to keep.
• The node you are deleting has two children. This is the more complicated one, but once you understand it, it's not all that difficult. You need to do the following steps:
  • Find the smallest value in the right subtree (note that you have a method to determine this). This is the successor of the node being deleted. Save this value in a temporary location.
  • Call Remove() on the right subtree with the value from the previous step as the argument. This will remove that value from the right subtree. (How do you know this will happen? Think about how many children the node holding the smallest value in a subtree can have.)
  • Replace the data item at the node with the value temp.
  Draw a picture of what happens in this case to convince yourself that it works.

I recommend you write Remove() as a recursive function following the model of the methods you are given.

Hint about Print(): Print() is easily implemented via a (recursive) tree traversal. It's a good idea to use incremental development in completing this assignment; completing the Print() method first is probably a good idea. It can be very helpful in debugging.