Description
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”.
Of course, this is like passing a law. Unless everyone obeys the law, it won’t have any effect. So we have to modify most of the methods to take advantage of it.
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.
[When we get to binary trees and probing hash tables in the next course, we will be able to re-use the deleted nodes when a client wants to add something that is physically present but marked as deleted. However, for general trees, this refinement is both trickier and less useful, so there is no need for us to burden ourselves with that technique.]
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.)
Links to an external site.
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 FHsdTreeNodeData Members:
- All previous members remain plus the one new private (or protected if you prefer) data member boolean deleted.
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 FHsdTreeOverriding 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.
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. At this point in the second programming course, I expect you to be able to make these kinds of determinations. This is the minimal client for testing, but you can add to it, optionally, if you wish.
import java.text.*;
import java.util.*;
//------------------------------------------------------
public class Foothill
{
// ------- main --------------
public static void main(String[] args) throws Exception
{
FHsdTree<String> sceneTree = new FHsdTree<String>();
FHsdTreeNode<String> tn;
System.out.println("Starting tree empty? " + sceneTree.empty() + "n");
// create a scene in a room
tn = sceneTree.addChild(null, "room");
// add three objects to the scene tree
sceneTree.addChild(tn, "Lily the canine");
sceneTree.addChild(tn, "Miguel the human");
sceneTree.addChild(tn, "table");
// add some parts to Miguel
tn = sceneTree.find("Miguel the human");
// Miguel's left arm
tn = sceneTree.addChild(tn, "torso");
tn = sceneTree.addChild(tn, "left arm");
tn = sceneTree.addChild(tn, "left hand");
sceneTree.addChild(tn, "thumb");
sceneTree.addChild(tn, "index finger");
sceneTree.addChild(tn, "middle finger");
sceneTree.addChild(tn, "ring finger");
sceneTree.addChild(tn, "pinky");
// Miguel's right arm
tn = sceneTree.find("Miguel the human");
tn = sceneTree.find(tn, "torso", 0);
tn = sceneTree.addChild(tn, "right arm");
tn = sceneTree.addChild(tn, "right hand");
sceneTree.addChild(tn, "thumb");
sceneTree.addChild(tn, "index finger");
sceneTree.addChild(tn, "middle finger");
sceneTree.addChild(tn, "ring finger");
sceneTree.addChild(tn, "pinky");
// add some parts to Lily
tn = sceneTree.find("Lily the canine");
tn = sceneTree.addChild(tn, "torso");
sceneTree.addChild(tn, "right front paw");
sceneTree.addChild(tn, "left front paw");
sceneTree.addChild(tn, "right rear paw");
sceneTree.addChild(tn, "left rear paw");
sceneTree.addChild(tn, "spare mutant paw");
sceneTree.addChild(tn, "wagging tail");
// add some parts to table
tn = sceneTree.find("table");
sceneTree.addChild(tn, "north east leg");
sceneTree.addChild(tn, "north west leg");
sceneTree.addChild(tn, "south east leg");
sceneTree.addChild(tn, "south west leg");
System.out.println("n------------ Loaded Tree ----------------- n");
sceneTree.display();
sceneTree.remove("spare mutant paw");
sceneTree.remove("Miguel the human");
sceneTree.remove("an imagined higgs boson");
System.out.println("n------------ Virtual (soft) Tree --------------- n");
sceneTree.display();
System.out.println("n----------- Physical (hard) Display ------------- n");
sceneTree.displayPhysical();
System.out.println("------- Testing Sizes (compare with above) -------- n");
System.out.println("virtual (soft) size: " + sceneTree.size() );
System.out.println("physiical (hard) size: " + sceneTree.sizePhysical() );
System.out.println("------------ Collecting Garbage ---------------- n");
System.out.println("found soft-deleted nodes? "
+ sceneTree.collectGarbage() );
System.out.println("immediate collect again? "
+ sceneTree.collectGarbage() );
System.out.println("--------- Hard Display after garb col ------------ n");
sceneTree.displayPhysical();
System.out.println("Semi-deleted tree empty? " + sceneTree.empty() + "n");
sceneTree.remove("room");
System.out.println("Completely-deleted tree empty? " + sceneTree.empty()
+ "n");
sceneTree.display();
}
}
OPTION B-1 (Intermediate)Â
This is instead of, not in addition to, Option A.
Implement the above soft deletion using derived class generics:
public class FHsdTreeNode<E> extends FHtreeNode<E>
public class FHsdTree<E> extends FHtree<E> implements Cloneable
In this solution, you may not touch a single character or the base classes – download them by using the same link given in Option A, but don’t modify them after they are copied into your project directory. Thus your project will have the old FHtree.java and FHtreeNode.java files, as well as new file FHsdTreeNode.java and FHsdTree.java files that you will write. These two files will have the derived classes FHsdTreeNode and FHsdTree defined. This is a realistic approach that prepares you for a situation in which you do not have access to the original source. The only members that the derived class may have are as follows:
Class FHsdTreeNode:
- boolean deleted (private or protected).
- at least one constructor that takes all parameters, chains to base class, and sets the deleted flag manually, by parameter. Default constructor overload, okay. (You won’t need the protected constructor because of the addition of the mutator in the next step, but it’s okay if you decide to add it in.)
- accessors and mutators for members like firstChild, prev, myRoot, etc.
Class FHsdTree
- No new data members or statics.
- Overrides of find(), remove(), addChild(), size(), etc. (Whatever was needed in Option A is needed here.)
- Adds displayPhysical(), sizePhysical() and collectGarbage()
These methods work exactly like their single-class counterparts of Option A, but are now in the derived class.
Client
The client will not change from Option A.
Use the organization and methods in FHtree.java and FHtreeNode.java as a guide for declaring your two new classes, but remember, these new classes extend the old ones.
Warning: This is harder than it looks. Your new classes are not “friends” with the given classes, and they might not even be in the same package. The data members of the FHtreeNode class will not be visible to the FHsdTree class, and you can’t provide accessors in FHtreeNode.java since, in Option B1, you don’t have permission to touch the base class source. This is why I direct you to provide accessors in the derived FHsdTreeNode class for these data members in the base class. You might, incidentally, seem to be able to do without the accessors, but if so, that would only be because your FHsdTree class and FHtreeNode class happen to be in the same package. In general, they won’t be.  Therefore, you have to constantly find ways in the FHsdTree methods to “get at” either the derived members or the new deleted member, as needed.
OPTION B-2 (Intermediate)
To either option above, demonstrate two more main()s, in addition to the first, that create a tree of different types:
- A simple numeric type
- Some user-defined Object type (like iTunes, Employee or whatever you want to provide).
