JAVA

Soft Deletion in Trees

Understand the Problem

Understand the Classes

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

FHtree.java

public class FHtree<E> implements Cloneable
{
protected int mSize;
protected FHtreeNode<E> mRoot;

public FHtree() { clear(); }
public boolean empty() { return (mSize == 0); }
public int size() { return mSize; }
public void clear() { mSize = 0; mRoot = null; }

public FHtreeNode<E> find(E x) { return find(mRoot, x, 0); }
public boolean remove(E x) { return remove(mRoot, x); }
public void display() { display(mRoot, 0); }

public < F extends Traverser< ? super E > >
void traverse(F func) { traverse(func, mRoot, 0); }

public FHtreeNode<E> addChild( FHtreeNode<E> treeNode, E x )
{
// empty tree? – create a root node if user passes in null
if (mSize == 0)
{
if (treeNode != null)
return null; // error something's fishy. treeNode can't right
mRoot = new FHtreeNode<E>(x, null, null, null);
mRoot.myRoot = mRoot;
mSize = 1;
return mRoot;
}
if (treeNode == null)
return null; // error inserting into non_null tree with a null parent
if (treeNode.myRoot != mRoot)
return null; // silent error, node does not belong to this tree

// push this node into the head of the sibling list; adjust prev pointers
FHtreeNode<E> newNode = new FHtreeNode<E>(x,
treeNode.firstChild, null, treeNode, mRoot); // sb, chld, prv, rt
treeNode.firstChild = newNode;
if (newNode.sib != null)
newNode.sib.prev = newNode;
++mSize;
return newNode;
}

public FHtreeNode<E> find(FHtreeNode<E> root, E x, int level)
{
FHtreeNode<E> retval;

if (mSize == 0 || root == null)
return null;

if (root.data.equals(x))
return root;

// otherwise, recurse. don't process sibs if this was the original call
if ( level > 0 && (retval = find(root.sib, x, level)) != null )
return retval;
return find(root.firstChild, x, ++level);
}

public boolean remove(FHtreeNode<E> root, E x)
{
FHtreeNode<E> tn = null;

if (mSize == 0 || root == null)
return false;

if ( (tn = find(root, x, 0)) != null )
{
removeNode(tn);
mSize–;
return true;
}
return false;
}

private void removeNode(FHtreeNode<E> nodeToDelete )
{
if (nodeToDelete == null || mRoot == null)
return;
if (nodeToDelete.myRoot != mRoot)
return; // silent error, node does not belong to this tree

// remove all the children of this node
while (nodeToDelete.firstChild != null)
removeNode(nodeToDelete.firstChild);

if (nodeToDelete.prev == null)
mRoot = null; // last node in tree
else if (nodeToDelete.prev.sib == nodeToDelete)
nodeToDelete.prev.sib = nodeToDelete.sib; // adjust left sibling
else
nodeToDelete.prev.firstChild = nodeToDelete.sib; // adjust parent

// adjust the successor sib's prev pointer
if (nodeToDelete.sib != null)
nodeToDelete.sib.prev = nodeToDelete.prev;
}

public Object clone() throws CloneNotSupportedException
{
FHtree<E> newObject = (FHtree<E>)super.clone();
newObject.clear(); // can't point to other's data

newObject.mRoot = cloneSubtree(mRoot);
newObject.mSize = mSize;
newObject.setMyRoots(newObject.mRoot);

return newObject;
}

private FHtreeNode<E> cloneSubtree(FHtreeNode<E> root)
{
FHtreeNode<E> newNode;
if (root == null)
return null;

// does not set myRoot which must be done by caller
newNode = new FHtreeNode<E>
(
root.data,
cloneSubtree(root.sib), cloneSubtree(root.firstChild),
null
);

// the prev pointer is set by parent recursive call … this is the code:
if (newNode.sib != null)
newNode.sib.prev = newNode;
if (newNode.firstChild != null)
newNode.firstChild.prev = newNode;
return newNode;
}

// recursively sets all myRoots to mRoot
private void setMyRoots(FHtreeNode<E> treeNode)
{
if (treeNode == null)
return;

treeNode.myRoot = mRoot;
setMyRoots(treeNode.sib);
setMyRoots(treeNode.firstChild);
}

// define this as a static member so recursive display() does not need
// a local version
final static String blankString = " ";

// let be public so client can call on subtree
public void display(FHtreeNode<E> treeNode, int level)
{
String indent;

// stop runaway indentation/recursion
if (level > (int)blankString.length() – 1)
{
System.out.println( blankString + " … " );
return;
}

if (treeNode == null)
return;

indent = blankString.substring(0, level);

// pre-order processing done here ("visit")
System.out.println( indent + treeNode.data ) ;

// recursive step done here
display( treeNode.firstChild, level + 1 );
if (level > 0 )
display( treeNode.sib, level );
}

// often helper of typical public version, but also callable by on subtree
public <F extends Traverser<? super E>>
void traverse(F func, FHtreeNode<E> treeNode, int level)
{
if (treeNode == null)
return;

func.visit(treeNode.data);

// recursive step done here
traverse( func, treeNode.firstChild, level + 1);
if (level > 0 )
traverse( func, treeNode.sib, level);
}
}

FHtreeNode.java

public class FHtreeNode<E>
{
// use protected access so the tree, in the same package,
// or derived classes can access members
protected FHtreeNode<E> firstChild, sib, prev;
protected E data;
protected FHtreeNode<E> myRoot; // needed to test for certain error

public FHtreeNode( E d, FHtreeNode<E> sb, FHtreeNode<E> chld, FHtreeNode<E> prv )
{
firstChild = chld;
sib = sb;
prev = prv;
data = d;
myRoot = null;
}

public FHtreeNode()
{
this(null, null, null, null);
}

public E getData() { return data; }

// for use only by FHtree (default access)
protected FHtreeNode( E d, FHtreeNode<E> sb, FHtreeNode<E> chld,
FHtreeNode<E> prv, FHtreeNode<E> root )
{
this(d, sb, chld, prv);
myRoot = root;
}
}

Foothill.java

import java.text.*;
import java.util.*;

//——————————————————
public class Foothill
{
// ——- main ————–
public static void main(String[] args) throws Exception
{
FHtree<String> sceneTree = new FHtree<String>();
FHtreeNode<String> tn;

// 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");

sceneTree.display();

sceneTree.remove("spare mutant paw");
sceneTree.remove("Miguel the human");
sceneTree.remove("an imagined higgs boson");

sceneTree.display();
}
}

/* —————— RUN ————-
room
table
south west leg
south east leg
north west leg
north east leg
Miguel the human
torso
right arm
right hand
pinky
ring finger
middle finger
index finger
thumb
left arm
left hand
pinky
ring finger
middle finger
index finger
thumb
Lily the canine
torso
wagging tail
spare mutant paw
left rear paw
right rear paw
left front paw
right front paw
room
table
south west leg
south east leg
north west leg
north east leg
Lily the canine
torso
wagging tail
left rear paw
right rear paw
left front paw
right front paw

——————————————– */

Traverser.java

public interface Traverser<E>
{
public void visit(E x);
}

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

Data 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 FHsdTree

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 addif 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();   }}