This will be your first foray into an actual ADT implementation. It is not a toy program, but the
real deal. You'll take the binary search tree implemented in the modules (and supplied in your
downloaded header file libraries) and modify it to use lazy deletion rather than the explicit
"hard deletion."
If you have carefully studied and experimented with the binary search tree template class, this
assignment should be "just right". It is not as difficult as doing an ADT from scratch, which might
require more than a week. Nonetheless, in the few methods that you must retool, you'll find just
enough of a challenge to feel like you are really cracking the problem. The changes and
debugging you will be doing are typical of ADT design.
Copy the file FHsearch_tree. h and name the copy FHlazySearchTree. h. Work on the latter file
for this assignment. Keep the names of the classes the
same: FHs_treeNode and FHsearch_tree. This way a client that works for the old "non-lazy"
trees will still work for the new ones without modification.
1. Add a bool deleted member to FHs_treeNode. Adjust this class to accommodate this
member.
2. Add a new int mSizeHard member to the FHsearch_tree class which tracks the number
of "hard" nodes in it, i. e., both deleted and undeleted. Meanwhile, mSize is still there
and will only reflect the number of undeleted nodes. Normally, the client will not need to
know about mSizeHard, but we want it for debugging purposes. Give it an
accessor, sizeHard(), so the client can test the class by displaying both the soft size (the
number the client normally wants) and the hard size.
3. Revise remove() (the private/recursive version) to implement lazy deletion.
4. Adjust insert() and any other methods that might need revision to work with this new
deletion technique. (The only exceptions to this is the height-related members and
methods which are only there for the derived class AVL tree. You can ignore any heightrelated code you find in the .h file.) (Also, note that when you insert() a new node you will
be inserting as if the deleted nodes were still there. For example, assume a sub tree, root
= 4, lchild = 1, rchild = 6. 4 is deleted. Insert 5. You could approach this by replacing "4"
with "5", but that's not what you should do. You should insert the 5 as if the 4 were still
there and make it a lchild of 6.)
5. Add a public/private pair, void collectGarbage() (the private method is the recursive
counterpart of the public one). This allows the client to truly remove all deleted (stale)
nodes. Don't do this by creating a new tree and inserting data into it, but by traversing
the tree and doing a hard remove on each deleted node. This will require that you have
a private removeHard() utility that works very much like our old remove() method.
6. findMin() and findMax() should return the min or max of the undeleted nodes. In other
words, they should not consider deleted nodes. This means you'll need an additional
function, findMinHard(), which finds the actual min, even if deleted, for use by
removeHard().
7. Test your code thoroughly. Documentation? No need for documentation in functions that you just modified. Just write
function comments for the functions that you wrote completely: the two garbage collection
functions, sizeHard(), findMinHard(), and remove_hard().