Objectives:

• Implement the new class type: LazySearchTree based on FHsearch_tree by enabling lazy deletion.
• Implement the new class: LazySTNode based on FHs_treeNode as an inner class in LazySearchTree.
• Complete the implementation of the class(es): SuperMarket.
• Update the class: LazySearchTree by enabling garbage collection on lazily deleted nodes..
• Test the implementation of the class(es): SuperMarket.
• Practice adding and removing items from a Binary Search Tree (BST).

class LazySearchTree and LazySTNode

All necessary files are here: https://drive.google.com/file/d/1crohBvbtrrpAtXzEmeUsCiTQYf2b3XN1/view?usp=sharing

Copy the contents of both FHsearch_tree.java and FHs_treeNode.java from your module. Then we need to make a few changes:

• Paste it into a new class and file of your creation named LazySearchTree. This will reside within the LazySearchTree.java file.
• In the new file, refactor (i.e. change the name of) the outer public class from FHsearch_tree to LazySearchTree. Note: You can easily do this in Eclipse, by right-clicking on the class name. Then scrolling down the menu until you get to "Refactor" -> "Rename...".
• Refactor the class FHs_treeNode to LazySTNode.
• Copy and paste the contents of LazySTNode in your new file LazySearchTree.java.
• Remove the type parameterization of the inner LazySTNode class:

// inner class

private class LazySTNode /*NOTE: no parameters here! */

{ ... }

• Make LazySTNode a private class.

Once you've prepared the class LazySearchTree, make the following design changes:

• Add a protected method called findMinHard() and findMaxHard() which start searching from the root. Each should return the true minimum and maximum node.
• Add a protected method called removeHard() that takes in two parameters*, one of type LazySTNode called root and a generic E type called x, and returns an object of type LazySTNode for the node we just removed. It will hard remove one node. NOTE: This method works very much like our old remove() method from FHsearch_tree. Simply put, this method has the same signature as that of remove() which does lazy deletion. The difference is that now we are explicitly hard removing nodes from the tree.
• Add a public/private pair, collectGarbage() Remember that the private method is the recursive counterpart of the public one, and takes/returns a root node. This method will call the removeHard() utility. A call to this method allows the client to truly remove all deleted (stale) nodes from the tree. Do *not* do this by creating a new tree and inserting data into it, but instead by traversing the tree and doing a hard remove on each deleted node.
• Test your code thoroughly.

class SuperMarket

The SuperMarket class provides an example scenario to test your implementation of garbage collection of lazily deleted elements. Similar to before an object of type SuperMarket handles adding and removal of items from the store's inventory.

From main(), your program:

• Will read from an "inventory.txt" file which contains a list of items that are added and bought.
• Will add and lazily remove items based on the input file.
• As the number of lazily deleted items increases, the amount of work that will be done in searching the tree will increase. To minimize this, every so often based on the static final class fieldGARBAGE_COLLECTION_THRESHOLD a call to cleanInventory() will hard remove lazily deleted nodes. The method cleanInventory() --already been written for you-- will call your collectGarbage() method, which you need to add in your LazySearchTree class. NOTE: For complete credit do not garbage collect after every call to remove(), instead iteratively call collectGarbage(). The collectGarbage() method will be invoked from within the test class.
• Finally, print what the SuperMarket inventory contains before and after a call to cleanInventory().