Description
Hi, I have attached below the instructions for this assignment so please take a look at that to see what needs to be done for this assignment. Please make sure to follow the instructions/guidelines provided to complete the assignment! This is very important! I have also attached the zip file with the files required to complete this assignment. Let me know if you have any questions or if there’s something that you find confusing about the instructions that you would like me to clear up with you!
Unformatted Attachment Preview
1/24/24, 1:55 PM
Submit Homework 2 | Gradescope
Q5
25 Points
The stack frame of a function is a specific region of memory designated
for storing local variables and function call information. It operates in a
stack-like manner, with memory automatically released upon the function
call’s completion. In contrast, the heap is a memory region utilized for
dynamic memory allocation, allowing the allocation of memory at
runtime. The memory allocated on the heap persists beyond the function
call unless explicitly deallocated. (See section 2.2 Stack in the lecture
notes)
In the context of the binary search tree class, the node objects are created
using the new operator, placing them in the heap. This choice is
deliberate, as it allows for dynamic allocation and management of
memory resources. However, this design also introduces a challenge – the
memory associated with these node objects may not be released
automatically when the binary search tree object is deleted. This situation
becomes particularly problematic in scenarios where multiple binary
search trees are created and deleted over the course of a program’s
execution.
To address this concern and prevent memory leaks, it becomes crucial to
provide a destructor for the binary search tree class.
The destructor facilitates the proper release of memory by visiting each
node in the tree and deallocating the allocated memory for each node.
Without a destructor, the heap-allocated memory for node objects would
persist, leading to an accumulation of memory leaks over the course of
repeated binary search tree creations and deletions. Therefore, the
implementation of a destructor is an essential aspect of managing the
memory lifecycle within the context of binary search trees.
Modifying the BinarySearchTree code discussed in the class according to
the following instructions:
1 Provide a destructor (~BinarySearchTree) for the BinarySearchTree class.
The destructor should traverse through all nodes in the tree and use the
delete operator to deallocate the memory for each node.
Determine the appropriate traversal method for iterating through all
nodes in the tree: in-order, pre-order, or post-order. Choose the method
https://www.gradescope.com/courses/696054/assignments/3928849/submissions/new
17/20
1/24/24, 1:55 PM
Submit Homework 2 | Gradescope
that best suits your memory deallocation requirements.
2 If your class involves dynamic memory allocation, creating a copy of an
object or performing an assignment using the default copy constructor or
assignment operator can lead to issues like double deletion or memory
leaks.
To fix this problem, please provide a custom copy constructor and
assignment operator for the BinarySearchTree class. In these custom
functions, perform a deep copy to ensure that new memory is allocated
for the copied object’s dynamic data. This prevents problems associated
with multiple objects attempting to manage the same memory.
For additional details on copy constructor and assignment operator
implementation, refer to sections 3.6.6-3.6.8 in the PIC10B lecture notes.
3 Node Class Modification:
Utilize the provided code for the Node class. In this modified code, a static
variable ‘ncall’ is introduced to record the total number of constructor
calls.
class Node
{
public:
static long int ncall;
//equals the total number of constructor calls
Node(){
left=nullptr;
right = nullptr;
ncall++;
};
private:
string data;
Node* left;
Node* right;
friend class BinarySearchTree;
friend class Iterator;
};
long int Node::ncall = 0;
If the above class is in .h file, then long int Node::ncall = 0; should be in
cpp file to avoid the linker error.
https://www.gradescope.com/courses/696054/assignments/3928849/submissions/new
18/20
1/24/24, 1:55 PM
Submit Homework 2 | Gradescope
4 Make sure the modified binary search tree class is compatible with the
code provided here
#include
#include
#include
using namespace std;
//put the implementation of the LinkedHashTable here
int main()
{
string s(10000, ‘*’);
for (int i = 1;i < 100000;i++)
{
BinarySearchTree* tpt;
tpt = new BinarySearchTree;
for (int j = 0;j < i % 193;j++)
{
tpt->insert(to_string(j)+s);
}
delete tpt;
}
//Without a destructor, this loop uses about 400GB of memory
Node n1;
cout
Purchase answer to see full
attachment
