Lab 4 – Lazy Deletion in BSTs
Parts A is required. Part B is optional and is worth two points extra credit (but must be submitted in addition to, and along with, Part A). Part C is optional but has no extra point value. Make sure you have read and understood
● both modules A and B this week, and
● module 2R – Lab Homework Requirements 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.”
You will find it helpful to fetch and install the files in the following zip archives now:
● https://fgamedia.org/faculty/anand/resources/CS_2C_Client_Support.zip
● https://fgamedia.org/faculty/anand/resources/CS_2C_Files.zip
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.
Preparation
Copy the file FHsearch_tree.h and name the copy FHlazySearchTree.h . Work on the latter file for this assignment. In the new file, change the name of the classes FHsearch_tree and FHs_treeNode to FHlazySearchTree and FHlazySearchTreeNode , respectively. Hint: Do a global search/replace of the old names with the new ones in this file . Also, if you use #ifndef/#define at the top of the file (to avoid nested compilation) they should be changed to some name distinct from FHSEARCHTREE_H .
This file should now compile without any errors and be compatible with your cs_1c library and project as a whole (other than the name of the new tree class). 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 bool deleted member to FHlazySearchTreeNode . 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 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() (recursive version) to implement lazy deletion .
4. Adjust insert() and any other methods that might need revision to work with this new deletion technique. This often means inspecting the deleted member when you are traversing for the data and take appropriate action based on the value of deleted . (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 height -related code you find in the .h file.)
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. 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:
// Assignment #4 Instructor Solution
In addition to testing your client a little better than the above main() does, add a couple of 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 EC Points)
Apply the same new ADT to EBookEntry objects by reading them in and doing various
removes and inserts. Do garbage collection at various points.
Option C: Benchmarking
If you have time and interest, after completing the above program, try to formulate an experiment to see if the lazy deletion helps or hinders various operations (insertions,
deletions, finds, etc.)
Submission Instructions Again
It’s worth reiterating because many students find it hard to follow instructions the first time. If you’re not one of them, feel free to skip the below. Note the following very simple important instructions. I will
only accept and grade submissions that follow these guidelines except when they are specifically
overridden in instructions.
1. Your submission should be a plain text file. See above. Save your file as a plain text file.
2. It is insufficient to simply have plain text format. The file name SHOULD have a .txt or .java extension. In the past, many students who submitted files with NO extension ended up
with no points earned for those assignments. I want to help you NOT be one of them. So that’s
why this guideline is explicitly stated here.
3. If you have multiple files you might otherwise need to submit, put them all in a single file, called
Assignment_N.txt and separate the various sections in this file using a commented line of
dashes. E.g. Your Assignment_8.txt file could be:
4. IMPORTANT: Don’t include any provided files (e.g. iTunes*.*) in your submission (I already
have them 🙂
5. Submit your work on time by uploading the above file into Canvas, well before the deadline.
6. The following guidelines are technically not mandatory, but following them would earn you the
full points you are eligible for. Why not earn easy-to-get points?
● Make sure you follow all the formatting guidelines. Serious points could be lost for badly
formatted or difficult-to-read code.
● Don’t over-engineer your code. Implement exactly what’s asked, no more and no less.
To demonstrate your additional knowledge, use the forums. Assignments are not the place to do it. No bells and whistles or decorative code/output.
● If you’re doing this course for a grade (i.e. your GPA is important) only attempt the BASIC OPTION unless you are absolutely certain you have the basics nailed.
Intermediate and Advanced options are generally graded far more strictly. You should, however, attempt the advanced options and post/discuss that code in the forums AFTER the lab has been graded.
● Make sure your output is not “touched up” by hand. Incorrect output is better than “doctored output.