Lazy Deletion in Binary Search Trees Assignment before submitting this assignment. Hand in only one program, please. PART A (REQUIRED) – LAZY DELETION WIT
Lazy Deletion in Binary Search Trees Assignment before submitting this assignment. Hand in only one program, please.
PART A (REQUIRED) – LAZY DELETION WITH INTS
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 generic 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.
Preparation
Copy the contents of both FHsearch_tree.java and FHs_treeNode.java into a new class and file of your creation named FHlazySearchTree and FHlazySearchTree.java. In the new file, change the name of the main public class from FHsearch_tree to FHlazySearchTree. Also, in your new file, change the name of the node class to FHlazySTNode and remove the public access for this node class so that it can reside in the same file as the tree class without a compiler error. Do a global search/replace of the old names with the new ones in this file. At the top of the file you’ll need the statements:
// file FHlazySearchTree.java
import cs_1c.*;
import java.util.*;
Any other places that import or package might appear as a result of your recent paste should be removed. This file should now compile without any errors and be compatible with your cs_1c package and project as a whole. So far, you have basically duplicated the logic of a BST into a second class that behaves exactly like the first, but has a new name. This is your starting point.
New Class Design
Add a boolean deleted member to FHlazySTNode . Adjust this class to accommodate this member.
Add a new int mSizeHard member to the FHlazySearchTree 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 undeletednodes. 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.
Revise remove() (both the public and protected/recursive version) to implement lazy deletion. The private version can now be void return type.
Adjust insert() and any other methods that might need revision to work with this new deletion technique. (The only exceptions to this are the height-related members and methods which are only there for the derived class AVL tree. You can ignore any height-related code you find in the file.)
Add a public/private pair, collectGarbage() (the private method is the recursive counterpart of the public one, and takes/returns a root node). 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.
Test your code thoroughly.
I will help you with the testing by providing a sample main() and successful run, but this is not a thorough test of the class:
// CIS 1C Assignment #4
// Instructor Solution Client
import cs_1c.*;
class PrintObject
{
public void visit(E x)
{
System.out.print( x + ” “);
}
};
//——————————————————
public class Foothill
{
// ——- main ————–
public static void main(String[] args) throws Exception
{
int k;
FHlazySearchTree
PrintObject
searchTree.traverse(intPrinter);
System.out.println( “ninitial size: ” + searchTree.size() );
searchTree.insert(50);
searchTree.insert(20);
searchTree.insert(30);
searchTree.insert(70);
searchTree.insert(10);
searchTree.insert(60);
System.out.println( “After populating — traversal and sizes: “);
searchTree.traverse(intPrinter);
System.out.println( “ntree 1 size: ” + searchTree.size()
+ ” Hard size: ” + searchTree.sizeHard() );
System.out.println( “Collecting garbage on new tree – should be ” +
“no garbage.” );
searchTree.collectGarbage();
System.out.println( “tree 1 size: ” + searchTree.size()
+ ” Hard size: ” + searchTree.sizeHard() );
// test assignment operator
FHlazySearchTree
= (FHlazySearchTree
System.out.println( “nnAttempting 1 removal: “);
if (searchTree.remove(20))
System.out.println( “removed ” + 20 );
System.out.println( “tree 1 size: ” + searchTree.size()
+ ” Hard size: ” + searchTree.sizeHard() );
System.out.println( “Collecting Garbage – should clean 1 item. ” );
searchTree.collectGarbage();
System.out.println( “tree 1 size: ” + searchTree.size()
+ ” Hard size: ” + searchTree.sizeHard() );
System.out.println( “Collecting Garbage again – no change expected. ” );
searchTree.collectGarbage();
System.out.println( “tree 1 size: ” + searchTree.size()
+ ” Hard size: ” + searchTree.sizeHard() );
// test soft insertion and deletion:
System.out.println( “Adding ‘hard’ 22 – should see new sizes. ” );
searchTree.insert(22);
searchTree.traverse(intPrinter);
System.out.println( “ntree 1 size: ” + searchTree.size()
+ ” Hard size: ” + searchTree.sizeHard() );
System.out.println( “nAfter soft removal. ” );
searchTree.remove(22);
searchTree.traverse(intPrinter);
System.out.println( “ntree 1 size: ” + searchTree.size()
+ ” Hard size: ” + searchTree.sizeHard() );
System.out.println( “Repeating soft removal. Should see no change. ” );
searchTree.remove(22);
searchTree.traverse(intPrinter);
System.out.println( “ntree 1 size: ” + searchTree.size()
+ ” Hard size: ” + searchTree.sizeHard() );
System.out.println( “Soft insertion. Hard size should not change. ” );
searchTree.insert(22);
searchTree.traverse(intPrinter);
System.out.println( “ntree 1 size: ” + searchTree.size()
+ ” Hard size: ” + searchTree.sizeHard() );
System.out.println( “nnAttempting 100 removals: ” );
for (k = 100; k > 0; k–)
{
if (searchTree.remove(k))
System.out.println( “removed ” + k );
}
searchTree.collectGarbage();
System.out.println( “nsearch_tree now:”);
searchTree.traverse(intPrinter);
System.out.println( “ntree 1 size: ” + searchTree.size()
+ ” Hard size: ” + searchTree.sizeHard() );
searchTree2.insert(500);
searchTree2.insert(200);
searchTree2.insert(300);
searchTree2.insert(700);
searchTree2.insert(100);
searchTree2.insert(600);
System.out.println( “nsearchTree2:n” );
searchTree2.traverse(intPrinter);
System.out.println( “ntree 2 size: ” + searchTree2.size()
+ ” Hard size: ” + searchTree2.sizeHard() );
}
}
/* ———————- Run ————————–
initial size: 0
After populating — traversal and sizes:
10 20 30 50 60 70
tree 1 size: 6 Hard size: 6
Collecting garbage on new tree – should be no garbage.
tree 1 size: 6 Hard size: 6
Attempting 1 removal:
removed 20
tree 1 size: 5 Hard size: 6
Collecting Garbage – should clean 1 item.
tree 1 size: 5 Hard size: 5
Collecting Garbage again – no change expected.
tree 1 size: 5 Hard size: 5
Adding ‘hard’ 22 – should see new sizes.
10 22 30 50 60 70
tree 1 size: 6 Hard size: 6
After soft removal.
10 30 50 60 70
tree 1 size: 5 Hard size: 6
Repeating soft removal. Should see no change.
10 30 50 60 70
tree 1 size: 5 Hard size: 6
Soft insertion. Hard size should not change.
10 22 30 50 60 70
tree 1 size: 6 Hard size: 6
Attempting 100 removals:
removed 70
removed 60
removed 50
removed 30
removed 22
removed 10
search_tree now:
tree 1 size: 0 Hard size: 0
searchTree2:
10 20 30 50 60 70 100 200 300 500 600 700
tree 2 size: 12 Hard size: 12
———————————————————————- */
In addition to testing your client a little better than the above main() does, add a couple tests forfindMin() and findMax() at various stages (e.g., hard-empty tree, a tree that has non-deleted stuff in it, and a tree that is completely empty but has all soft-deleted nodes) to make sure your exception handling is working in findMin() and findMax().
OPTION B – LAZY DELETION WITH EBOOKS (2 POINTS EXTRA CREDIT)
Apply the same new ADT to EBookEntry objects by reading them in and doing various removes and inserts. Do garbage collection at various points. This can be less rigorous than the above test – it is just to show that the generic does not break on the EBookEntry data set.
