Binary Search Trees

 

  1. We have discussed deleting from a Binary Search Tree and completed all cases except “the hard case” where the node to be deleted has two children.  Complete the delete method given in class by doing “the hard case” according to the following outline:
    1. First find the “next” node by going right and then left as far as possible.
    2. Copy the data from the “next” node to the node being deleted.  (Note that you’ve now gotten rid of the data that you were trying to delete, but you now have two copies of the data from the “next” node.)
    3. Finally delete the “next” node by setting its parent’s left pointer to null. This last hint is a slight lie.  There is one case where that isn’t what you do – find that case and handle it properly.
    4. Your testing should use the file few_names.  Begin by inserting all the names in this file.  Then your test should print the file in tree form before and after deleting the following:

Mann, Roland, Carrett, Cato

 

            This is due Thursday after Thanksgiving at 11:59PM.  5% extra credit if you hand in a hardcopy in class and make no further changes.

 

  1. This entire discussion of deleting in problem 1. assumes that there is a unique identity to the node to be deleted.  Perhaps we’d like to handle multiple copies of the same node. There are several possibilities for this.  Here are two ideas for an extra credit assignment.
    1. Change the nodes so that they carry a variable “count”.  Then when you add an item, you will increase count if the item is on the tree and only create a new node if the item is not already on the tree.  Similarly you would delete an item by reducing the count and actually delete the node only when the count went from 1 to 0.  We could also have a deleteAll which would delete the node regardless of the count.
    2. Another possibility is to just allow additions of the same item. But then we’d want to have two deletes.  A “deleteFirst” would delete the first node containing that data that it found.  And a deleteAll which would traverse the tree deleting each node which contained the data it was deleting.  WARNING:   A deleteAll is easy if you have a delete already done if (I said “IF”)  you traverse the tree correctly.