OPTION A (Basic): Soft Deletion in Trees (C++)

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 the FHtreeNode class:

 bool 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 bool 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 == 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

Download it, unzip and drag a copy of FHtree.h into your project's source directory. Rename the copy SoftDelTree.h. Then incorporate it in your project (it may appear automatically, or you can invoke "Header Files Add Existing item"). Also, copy and past the contents of the client Foothill.cpp into your main .cpp file. 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 three ways for this assignment:

The #include statement must be changed to reflect the new file name, "SoftDelTree.h. This only works, of course, after you have modified and renamed the supplied header file.

Any references to FHtreeNode and FHtree in the old 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, change the name of the .h file to SoftDelTree.h and the names of the classes it contains to FHsdTreeNode and FHsdTree. Do whatever it takes to both the .h and your .cpp files 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 bool deleted.

Methods To Modify:

All constructors should take a new default parameter for the deleted member, and the default value for that parameter should be false.

Class FHsdTree

Methods To Modify:

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 merely 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.

display() - Two versions, just like the previous implementation of a general tree, however, the deleted flag must be considered when deciding whether to display something, or return without doing anything. If a node is marked as deleted, neither it, nor its entire child sub-tree should be displayed. They are no longer in the tree.

Others -- any other method which require changes because of the deleted member must be modified. 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.

int 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, for our new size(), all children/sub-trees of deleted nodes are considered deleted, even if their deleted flag is still set to false).

void 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 append 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.

bool 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. The return value is true if there was at least one node that got garbage-collected, and false, otherwise. 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.

#include  #include  using namespace std; #include "SoftDelTree.h" int main() { FHsdTree sceneTree; FHsdTreeNode *tn; cout << "Starting tree empty? " << sceneTree.empty() << endl << endl; // 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"); 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"); cout << " ------------ Loaded Tree ----------------- "; sceneTree.display(); sceneTree.remove("spare mutant paw"); sceneTree.remove("Miguel the human"); sceneTree.remove("an imagined higgs boson"); cout << " ------------ Virtual (soft) Tree ----------------- "; sceneTree.display(); cout << " ------------ Physical (hard) Display ----------------- "; sceneTree.displayPhysical(); cout << "------- Testing Sizes (compare with above)----------- "; cout << "virtual (soft) size: " << sceneTree.size() << endl; cout << "physical (hard) size: " << sceneTree.sizePhysical() << endl; cout << "------------ Collecting Garbage -------------------- "; cout << "found soft-deleted nodes? " << sceneTree.collectGarbage() << endl; cout << "immediate collect again? " << sceneTree.collectGarbage() << endl; cout << "--------- Hard Display after garb col ------------ "; sceneTree.displayPhysical(); cout << "Semi-deleted tree empty? " << sceneTree.empty() << endl << endl; sceneTree.remove("room"); cout << "Completely-deleted tree empty? " << sceneTree.empty() << endl << endl; return 0; } 

OPTION B-1 (Intermediate) 3 Points Extra Credit

This is instead of, not in addition to, Option A.

Implement the above soft deletion using derived class templates

 template  class FHsdTreeNode : public FHtreeNode