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.

Save your time - order a paper!

Get your paper written from scratch within the tight deadline. Our service is a reliable solution to all your troubles. Place an order on any task and we will take care of it. You won’t have to worry about the quality and deadlines

Order Paper Now
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_x000D_
_x000D_
import cs_1c.*;_x000D_
import java.util.*;_x000D_

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
  1. Add a boolean deleted member to FHlazySTNode . Adjust this class to accommodate this member.
  2. 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.
  3. Revise remove() (both the public and protected/recursive version) to implement lazy deletion. The private version can now be void return type.
  4. 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.)
  5. 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.
  6. 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_x000D_
// Instructor Solution Client_x000D_
_x000D_
import cs_1c.*;_x000D_
_x000D_
class PrintObject<E> implements Traverser<E>_x000D_
{_x000D_
   public void visit(E x)_x000D_
   {_x000D_
      System.out.print( x + " ");_x000D_
   }_x000D_
};_x000D_
_x000D_
//------------------------------------------------------_x000D_
public class Foothill_x000D_
{_x000D_
   // -------  main --------------_x000D_
   public static void main(String[] args) throws Exception_x000D_
   {_x000D_
      int k;_x000D_
      FHlazySearchTree<Integer> searchTree = new FHlazySearchTree<Integer>();_x000D_
      PrintObject<Integer> intPrinter = new PrintObject<Integer>();_x000D_
_x000D_
      searchTree.traverse(intPrinter);_x000D_
_x000D_
      System.out.println( "ninitial size: " + searchTree.size() );_x000D_
      searchTree.insert(50);_x000D_
      searchTree.insert(20);_x000D_
      searchTree.insert(30);_x000D_
      searchTree.insert(70);_x000D_
      searchTree.insert(10);_x000D_
      searchTree.insert(60);_x000D_
_x000D_
      System.out.println( "After populating -- traversal and sizes: ");_x000D_
      searchTree.traverse(intPrinter);_x000D_
      System.out.println( "ntree 1 size: " + searchTree.size() _x000D_
         + "  Hard size: " + searchTree.sizeHard() );_x000D_
_x000D_
      System.out.println( "Collecting garbage on new tree - should be " +_x000D_
            "no garbage." );_x000D_
      searchTree.collectGarbage();_x000D_
      System.out.println( "tree 1 size: " + searchTree.size() _x000D_
         + "  Hard size: " + searchTree.sizeHard() );_x000D_
_x000D_
      // test assignment operator_x000D_
      FHlazySearchTree<Integer> searchTree2 _x000D_
         = (FHlazySearchTree<Integer>)searchTree.clone();_x000D_
_x000D_
      System.out.println( "nnAttempting 1 removal: ");_x000D_
      if (searchTree.remove(20))_x000D_
         System.out.println( "removed " + 20 );_x000D_
      System.out.println( "tree 1 size: " + searchTree.size() _x000D_
         + "  Hard size: " + searchTree.sizeHard() );_x000D_
_x000D_
      System.out.println( "Collecting Garbage - should clean 1 item. " );_x000D_
      searchTree.collectGarbage();_x000D_
      System.out.println( "tree 1 size: " + searchTree.size() _x000D_
         + "  Hard size: " + searchTree.sizeHard() );_x000D_
_x000D_
      System.out.println( "Collecting Garbage again - no change expected. " );_x000D_
      searchTree.collectGarbage();_x000D_
      System.out.println( "tree 1 size: " + searchTree.size() _x000D_
         + "  Hard size: " + searchTree.sizeHard() );_x000D_
_x000D_
      // test soft insertion and deletion:_x000D_
_x000D_
      System.out.println( "Adding 'hard' 22 - should see new sizes. " );_x000D_
      searchTree.insert(22);_x000D_
      searchTree.traverse(intPrinter);_x000D_
      System.out.println( "ntree 1 size: " + searchTree.size() _x000D_
         + "  Hard size: " + searchTree.sizeHard() );_x000D_
_x000D_
      System.out.println( "nAfter soft removal. " );_x000D_
      searchTree.remove(22);_x000D_
      searchTree.traverse(intPrinter);_x000D_
      System.out.println( "ntree 1 size: " + searchTree.size() _x000D_
         + "  Hard size: " + searchTree.sizeHard() );_x000D_
_x000D_
      System.out.println( "Repeating soft removal. Should see no change. " );_x000D_
      searchTree.remove(22);_x000D_
      searchTree.traverse(intPrinter);_x000D_
      System.out.println( "ntree 1 size: " + searchTree.size() _x000D_
         + "  Hard size: " + searchTree.sizeHard() );_x000D_
_x000D_
      System.out.println( "Soft insertion. Hard size should not change. " );_x000D_
      searchTree.insert(22);_x000D_
      searchTree.traverse(intPrinter);_x000D_
      System.out.println( "ntree 1 size: " + searchTree.size() _x000D_
         + "  Hard size: " + searchTree.sizeHard() );_x000D_
_x000D_
      System.out.println( "nnAttempting 100 removals: " );_x000D_
      for (k = 100; k > 0; k--)_x000D_
      {_x000D_
         if (searchTree.remove(k))_x000D_
            System.out.println( "removed " + k );_x000D_
      }_x000D_
      searchTree.collectGarbage();_x000D_
_x000D_
      System.out.println( "nsearch_tree now:");_x000D_
      searchTree.traverse(intPrinter);_x000D_
      System.out.println( "ntree 1 size: " + searchTree.size() _x000D_
         + "  Hard size: " + searchTree.sizeHard() );_x000D_
_x000D_
      searchTree2.insert(500);_x000D_
      searchTree2.insert(200);_x000D_
      searchTree2.insert(300);_x000D_
      searchTree2.insert(700);_x000D_
      searchTree2.insert(100);_x000D_
      searchTree2.insert(600);_x000D_
      System.out.println( "nsearchTree2:n" );_x000D_
      searchTree2.traverse(intPrinter);_x000D_
      System.out.println( "ntree 2 size: " + searchTree2.size() _x000D_
         + "  Hard size: " + searchTree2.sizeHard() );_x000D_
   }_x000D_
}_x000D_
/* ---------------------- Run --------------------------_x000D_
_x000D_
initial size: 0_x000D_
After populating -- traversal and sizes: _x000D_
10 20 30 50 60 70 _x000D_
tree 1 size: 6  Hard size: 6_x000D_
Collecting garbage on new tree - should be no garbage._x000D_
tree 1 size: 6  Hard size: 6_x000D_
Attempting 1 removal: _x000D_
removed 20_x000D_
tree 1 size: 5  Hard size: 6_x000D_
Collecting Garbage - should clean 1 item. _x000D_
tree 1 size: 5  Hard size: 5_x000D_
Collecting Garbage again - no change expected. _x000D_
tree 1 size: 5  Hard size: 5_x000D_
Adding 'hard' 22 - should see new sizes. _x000D_
10 22 30 50 60 70 _x000D_
tree 1 size: 6  Hard size: 6_x000D_
_x000D_
After soft removal. _x000D_
10 30 50 60 70 _x000D_
tree 1 size: 5  Hard size: 6_x000D_
Repeating soft removal. Should see no change. _x000D_
10 30 50 60 70 _x000D_
tree 1 size: 5  Hard size: 6_x000D_
Soft insertion. Hard size should not change. _x000D_
10 22 30 50 60 70 _x000D_
tree 1 size: 6  Hard size: 6_x000D_
Attempting 100 removals: _x000D_
removed 70_x000D_
removed 60_x000D_
removed 50_x000D_
removed 30_x000D_
removed 22_x000D_
removed 10_x000D_
_x000D_
search_tree now:_x000D_
_x000D_
tree 1 size: 0  Hard size: 0_x000D_
_x000D_
searchTree2:_x000D_
_x000D_
10 20 30 50 60 70 100 200 300 500 600 700 _x000D_
tree 2 size: 12  Hard size: 12_x000D_
---------------------------------------------------------------------- */_x000D_

In addition to testing your client a little better than the above
main() does, add a couple tests for
findMin() 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.

 
Do you need a similar assignment done for you from scratch? We have qualified writers to help you. We assure you an A+ quality paper that is free from plagiarism. Order now for an Amazing Discount!
Use Discount Code "Newclient" for a 15% Discount!

NB: We do not resell papers. Upon ordering, we do an original paper exclusively for you.