{"id":108163,"date":"2022-12-05T03:49:04","date_gmt":"2022-12-05T03:49:04","guid":{"rendered":"https:\/\/assignmenttutors.net\/blog\/lab-4-lazy-deletion-in-bsts\/"},"modified":"2022-12-05T03:49:04","modified_gmt":"2022-12-05T03:49:04","slug":"lab-4-lazy-deletion-in-bsts","status":"publish","type":"post","link":"https:\/\/assignmenttutors.net\/blog\/lab-4-lazy-deletion-in-bsts\/","title":{"rendered":"Lab 4 – lazy deletion in bsts"},"content":{"rendered":"
\n

\u00a0\u00a0<\/p>\n

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
\u25cf both \u200b modules A\u200b and \u200b B\u200b this week, and
\u25cf 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:
\u25cf https:\/\/fgamedia.org\/faculty\/anand\/resources\/CS_2C_Client_Support.zip
\u25cf 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 \u200b FHsearch_tree.h \u200b and name the copy \u200b FHlazySearchTree.h\u200b . Work on the latter file for this assignment. In the new file, change the name of the classes FHsearch_tree\u200b and \u200b FHs_treeNode\u200b to \u200b FHlazySearchTree \u200b and FHlazySearchTreeNode\u200b , respectively. \u200b Hint: Do a global search\/replace of the old names with the new ones in this file\u200b . Also, if you use \u200b #ifndef\/#define \u200b at the top of the file (to avoid nested compilation) they should be changed to some name \u200b distinct\u200b from FHSEARCHTREE_H\u200b .
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 \u200b bool deleted\u200b member to \u200b FHlazySearchTreeNode\u200b . Adjust this class to accommodate this member.
2. Add a new \u200b int mSizeHard\u200b member to the \u200bFHlazySearchTree \u200b class which tracks the number of “hard” nodes in it, i.e., both \u200b deleted\u200b and \u200b undeleted\u200b.
Meanwhile, \u200b mSize\u200b is still there and will only reflect the number of \u200b undeleted nodes. Normally, the client will not need to know about \u200b mSizeHard\u200b , but we want it for debugging purposes. Give it an accessor, \u200b sizeHard()\u200b , 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 \u200b remove()\u200b (recursive version) to implement \u200b lazy deletion\u200b .
4. Adjust\u200b insert()\u200b \u200b and any other methods\u200b that might need revision to work with this new deletion technique. This often means inspecting the \u200b deleted member when you are traversing for the data and take appropriate action based on the value of \u200b deleted\u200b . (The only exceptions to this is the
height\u200b -related members and methods which are only there for the derived class \u200b AVL tree\u200b . You can ignore any \u200bheight\u200b -related code you find in the \u200b .h\u200b file.)
5. Add a public\/private pair, void \u200b collectGarbage()\u200b (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 \u200b hard remove\u200b on each
deleted node. This will require that you have a private \u200b removeHard()\u200b utility
that works very much like our old \u200b remove()\u200b method.
6. Test your code thoroughly.
I will help you with the testing by providing a sample \u200b main()\u200b 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 \u200b main()\u200b does, add a couple of tests for\u200b findMin()\u200b and \u200b findMax()\u200b 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\u200b findMin()\u200b and findMax()\u200b .
Option B – Lazy Deletion with EBooks (2 EC Points)
Apply the same new \u200b ADT\u200b to \u200b EBookEntry\u200b 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 \u200b lazy deletion\u200b helps or hinders various operations (insertions,
deletions, finds, etc.)
\u00a0\u00a0\u00a0Submission Instructions Again
It\u2019s worth reiterating because many students find it hard to follow instructions the first time. If you\u2019re 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 \u200b .txt\u200b or .java\u200b 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\u2019s
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 \u200b Assignment_8.txt\u200b file could be:
4. IMPORTANT: Don\u2019t include any provided files (e.g. iTunes*.*) in your submission (I already
have them \ud83d\ude42
5. Submit your work \u200b on time\u200b 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?
\u25cf Make sure you follow all the formatting guidelines. Serious points could be lost for badly
formatted or difficult-to-read code.
\u25cf Don\u2019t over-engineer your code. Implement exactly what\u2019s 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.
\u25cf If you\u2019re 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.
\u25cf Make sure your output is not \u201ctouched up\u201d by hand. Incorrect output is better than \u201cdoctored output.<\/p>\n

\u00a0<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

\u00a0\u00a0 Lab 4 – Lazy Deletion in BSTsParts 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\u25cf both \u200b modules A\u200b […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[16],"tags":[],"class_list":["post-108163","post","type-post","status-publish","format-standard","hentry","category-education"],"_links":{"self":[{"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/posts\/108163","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/comments?post=108163"}],"version-history":[{"count":0,"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/posts\/108163\/revisions"}],"wp:attachment":[{"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/media?parent=108163"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/categories?post=108163"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/tags?post=108163"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}