OPTION A (Basic): Soft Deletion in Trees

You are going to be changing the general tree class template, FHtree, of the lectures by adding a single member to it:

 boolean deleted; // true if the node has been removed from the tree

The idea is that when a client asks this class to delete a node, all we will do is set this boolean to true and return without further ado.

You will have to rename the classes from FHtreeNode and FHtree (from the lectures) to FHsdTreeNode and FHsdTree, respectively, to distinguish them from the normal-deletion implementations in those lectures.

That's it in a nutshell. The purpose of this new, deleted, member is to avoid ever physically removing a node when the client wants to delete it. Instead we just set deleted = true and it will be considered "gone".

Some might be easier, some not. For example, remove() may be simpler and shorter than before, since, once it finds the node, all it has to do is set deleted = true -- no actual unlinking of the nodes, destruction of objects, etc. Other methods, like find(), will be more subtle. Finding a node means more than matching the data ( if (x.equals(root.data)) ... ). Even though we might find the data, x, in the tree, this does not mean x is really there. It may have been deleted at some point in the past. Remember: now, deleting it leaves it physically in the tree with the deleted flag set. You have to add a second test, if (deleted) ..., before you know whether or not you have really found x. Same thing with display(), size(), etc. They will only report on the virtual tree, not the physical one that is stored in memory. If a node is deleted, it may not be counted or displayed by the various methods.

On the other hand, there will be some new methods that don't have general tree counterparts. sizePhysical() will report on the size of the tree, counting both deleted and non-deleted nodes (so it will basically be exactly our old size() method. displayPhysical() will likewise show everything, including deleted nodes (it will not be required to show the deleted status for this assignment, although that's a nice touch). displayPhysical(), also, can be engineered to reuse the code of the old display() method since that method, by virtue of its ignorance of the newly added deleted flag, already shows all the nodes.

In soft deletion, trees don't normally ever shrink; they keep getting larger. Even though the client may be adding and removing the same number of objects, the add()s will always add nodes, but the remove()s will never take nodes away, just mark them as deleted. This is the meaning and expected behavior of soft deletion. It is used when normal deletion (which we can now call hard or physical deletion to emphasize the difference) has some disruptive effect on the tree and we want to avoid such physical disruption for some reason.

Finally, we will need a collectGarbage() method that goes through the entire tree and physically removes all deleted nodes. This is the only method that will shrink the tree size and bring its physical and virtual contents, at least temporarily, into alignment.

For your convenience, the complete listing of the hard-deletion-based general tree presented in the lectures can he downloaded here

zipped FHgTree files (Links to an external site) http://fgamedia.org/faculty/loceff/cs_courses/cs_1b/resources/FHgTree.zip

Download the .zip file, unziop it and drag a copy of FHtree.java, FHtreeNode.java and Traverser.java into your project's src folder. Then, incorporate these classes into your project (in Eclipse, use File Refresh). Also, copy and past the contents of the client, Foothill.java into your main .java file. If your main class is not named Foothill, make adjustments, accordingly. If you compile and run the project after doing this, you should get the original output as shown in the modules.

Understand the Client:

The client main() that is provided in the lesson (and in your zipped download file, above) will eventually need to be modified in two ways for this assignment:

Any references to FHtreeNode and FHtree in the downloaded client must be changed to refer to the new classes we are designing, FHsdTreeNode and FHsdTree.

The client will contain some extra tests in addition to the ones that were there. For example, we'll need to write and test methods like displayPhysical(), collectGarbage().

Implementation Details:

After you succeed in compiling and running the lecture code as described above, rename FHtree.java to FHsdTree.java, and rename and FHtreeNode.java to FHsdTreeNode.java Change the names of the classes that these files contain to FHsdTreeNode and FHsdTree. [Note: Eclipse, will do all this for you automatically once you Refactor Rename each file, but other IDEs might require that you adjust the contents of all the files, manually, to accommodate the new file names.] Do whatever it takes to both these .java files and your main .java file so that everything compiles with these new names (but don't attempt any new implementation yet). Run again to make sure you get the same output as before. You are now ready to begin your assignment.

Class FHsdTreeNode:

1) Data Members: - All previous members remain plus the one new private (or protected if you prefer) data member boolean deleted.

2) Methods To Modify: - All parameter-taking constructors should be modified to take a new parameter for the deleted member, and the default constructor should make sure the value for the deleted member is initialized to false.

Class FHsdTree:

1) Overriding Methods: - addChild() - not much difference from old addChild(). In particular, we do not see if the data is already in the tree as deleted and get clever. We always add the node, exactly as if this were an ordinary tree. However, optionally, you can check the first parameter (treeNode, root, or whatever you call it) to see if it is deleted, and reject the add if it is. There are some unusual scenarios in which the client might inadvisably attempt to make a useless addition under/to a deleted node.

- find() - Two versions, just like the old implementation: one non-recursive takes only the data, x, and the other which takes two more parameters for recursion. The non-recursive calls the recursive. The recursive method should check the deleted flag of any data match (a "found" x) and, if true, should return as if the data were not in the tree. If the deleted flag is false, then you would return the node as before, a "good find". Note: the sub-tree of a deleted node is considered entirely deleted, even if individual sub-tree nodes might be still have deleted = false.

- remove() - Two versions, just like the previous implementation of a general tree, however, the deleted flag of the appropriate node is set to true. The node is not physically removed from the tree. Note the meaning: this has the same meaning as the old remove(). If a node is marked as deleted, then the entire child sub-tree is considered gone. Those nodes, while not marked themselves (big error to waste time marking them), are no longer in the tree. Caution: While you might think it best to mark the firstChild of the deleted node to null, thereby allowing the Java garbage collector to get rid of that subtree for you, do not do this. Leave the firstChild, and all the children still in the physical tree. In CS 1C, we will see how we can reuse deleted nodes left in the tree to save work. This forces us to write our other methods (like display() and find()) to obey the deleted flag and consciously skip processing children of a deleted node.

- Others -- any other method which require overriding must be overridden. You have to decide. Using common sense on the meaning and interpretation of deleted is part of your assignment. There are several methods that require overriding. Hint: size() will not use mSize, since that member only reflects physical size. Instead, size() has to compute the size, manually (read "recursively"), so it is harder than the old size(). traverse() is another that needs tweaking. Check for more.

2) New Methods: - "Physical" versions of some methods are needed so we can (for debugging and maintenance purposes) see the actual tree on the console, replete with both deleted and undeleted nodes. Some of these methods work almost exactly as the prior implementation of methods in the non-soft-deletion trees.

- sizePhysical() - returns the actual, physical size. This is easy: just like our old size() from the lectures. It just has a new name in this regime since the old name, size(), is now used to return the virtual size of the tree (a count of non-deleted nodes -- and remember, all children/sub-trees of deleted nodes are considered deleted, even if their deleted flag is still set to false).

- displayPhysical() - like the old display() from the lectures. Ignores the deleted flag. Optionally, place a " (D)" after any node that has deleted == true. Note: you don't have to add the "(D)" if the node is not marked as deleted, even though it might actually be deleted by virtue of its being in a subtree of a deleted node.

- collectGarbage() - physically removes all nodes that are marked as deleted. After this method is called, the physical and virtual size of the tree would be the same. A physical and virtual display() would also be the same after a call to collectGarbage() (at least temporarily, until more items are remove()ed from the tree). This method does exactly what it says: it takes out the garbage. Hint: make use of removeNode(), which can be preserved from the original general tree class.

Suggestion about Order of Implementation: Add the deleted member to the FHsdTreeNode class as private or protected.

Update the signatures of the constructors FHsdTreeNode(), to accommodate the extra parameter (wherever you want to put it).

One at-a-time, begin updating the FHsdTree methods as demanded by the new FHsdTreeNode member, deleted. Suggestion: Start with addChild(), then find(), then remove(). Test as you go. Once these three are working, you'll implement all the rest.

Client

Here is a client you can use to test your code. I am not going to tell you what this client should produce. You should be able to predict that on your own and make a judgment about whether your code is working. This is the minimal client for testing, but you can add to it, optionally, if you wish.

Client: https://docs.google.com/document/d/1S3kPZLIf6Zd2pCaKPjTlAP0fWt3vyuKNkhxl_WrkUfg/edit?usp=sharing