Using the following c++ header file near the bottom for context, fill in the "TODO" commented parts of the following function to finish the function implementation for the following remove function: FUNCTION: / PURPOSE: Removes vertex pointed to by V // PARAM: V and its parent pointer P // Case 1: it is a leaf, delete it // Case 2: it has just one child, bypass it // Case 3: it has two children, replace it with the max of the left subtree void BST::remove(Vertex *V, Vertex *P) { if (/*TODO*/) { // if V is a leaf (case 1) cout << "removing a leaf" << endl; if (/*TODO*/) { // if V is a left child of P // TODO delete V and also make Parent's left NULL // TODO call here from P to adjust height and BF } else {// V is a right child of the Parent // TODO delete V and also make Parent's right NULL // TODO call from P to adjust height and BF } } else if (/*TODO*/) { // if V has just the left child so bypass V (case 2) Vertex* C = V->left; // C is the left child cout << "removing a vertex with just the left child" << endl; // TODO You need if then else to determine Parent's left or right // should point to C; // TODO Make C point UP to the parent; cout << C->elem << " points up to " << C->up->elem << endl; // TODO Be sure to delete V // TODO call from P to adjust height and BF } else if (/*TODO*/) { // if V has just the right child so bypass V (case 2) Vertex* C = V->right; // C is the right child cout << "removing a vertex with just the right child" << endl; // TODO You need if then else to determine Parent's left or right // should point to C; // TODO Make C point UP to the parent; cout << C->elem << " points up to " << C->up->elem << endl; // TODO Be sure to delete V // TODO call from P to adjust height and BF } else { // V has two children (case 3) cout << "removing an internal vertex with children" << endl; cout << "..find the MAX of its left sub-tree" << endl; el_t Melem; // find MAX element in the left sub-tree of V Melem = findMax(V); cout << "..replacing " << V->elem << " with " << Melem << endl; // TODO Replace V's element with Melem here } }// end of remove ----------------------------------------------------------------------------------------------------------- HEADER FILE: // tree element type is int for nowtypedef int el_t; // el_t is hidden from the client // definition of what a Vertex is - also hidden from the clientstruct Vertex{ Vertex *up; // points to the parent node Vertex *left; el_t elem; Vertex *right; int height; int balance;}; // this is set up to be inherited by another classclass BST {public: BST(); // intializes Root ~BST(); // destructor calls dtraverse to destroy the dynamic tree // PURPOSE: these will show the vertices in IN order // TO CALL: No parameter but provide a pointer to // the root vertex in calling INorderTraversal void Display(); void InOrderTraversal(Vertex*); // recursive // PURPOSE: these will search in PRE order - same as Depth First // TO CALL: provide the element to search for; provide a pointer to // the root vertex in calling PREorderSearch bool Search(el_t); bool PreOrderSearch(Vertex*, el_t); // recursive
Using the following c++ header file near the bottom for context, fill in the "TODO" commented parts of the following function to finish the function implementation for the following remove function:
FUNCTION:
/ PURPOSE: Removes vertex pointed to by V
// PARAM: V and its parent pointer P
// Case 1: it is a leaf, delete it
// Case 2: it has just one child, bypass it
// Case 3: it has two children, replace it with the max of the left subtree
void BST::remove(Vertex *V, Vertex *P)
{
if (/*TODO*/) { // if V is a leaf (case 1)
cout << "removing a leaf" << endl;
if (/*TODO*/) { // if V is a left child of P
// TODO delete V and also make Parent's left NULL
// TODO call here from P to adjust height and BF
} else {// V is a right child of the Parent
// TODO delete V and also make Parent's right NULL
// TODO call from P to adjust height and BF
}
} else if (/*TODO*/) { // if V has just the left child so bypass V (case 2)
Vertex* C = V->left; // C is the left child
cout << "removing a vertex with just the left child" << endl;
// TODO You need if then else to determine Parent's left or right
// should point to C;
// TODO Make C point UP to the parent;
cout << C->elem << " points up to " << C->up->elem << endl;
// TODO Be sure to delete V
// TODO call from P to adjust height and BF
} else if (/*TODO*/) { // if V has just the right child so bypass V (case 2)
Vertex* C = V->right; // C is the right child
cout << "removing a vertex with just the right child" << endl;
// TODO You need if then else to determine Parent's left or right
// should point to C;
// TODO Make C point UP to the parent;
cout << C->elem << " points up to " << C->up->elem << endl;
// TODO Be sure to delete V
// TODO call from P to adjust height and BF
} else { // V has two children (case 3)
cout << "removing an internal vertex with children" << endl;
cout << "..find the MAX of its left sub-tree" << endl;
el_t Melem;
// find MAX element in the left sub-tree of V
Melem = findMax(V);
cout << "..replacing " << V->elem << " with " << Melem << endl;
// TODO Replace V's element with Melem here
}
}// end of remove
-----------------------------------------------------------------------------------------------------------
HEADER FILE:
// tree element type is int for now
typedef int el_t; // el_t is hidden from the client
// definition of what a Vertex is - also hidden from the client
struct Vertex
{
Vertex *up; // points to the parent node
Vertex *left;
el_t elem;
Vertex *right;
int height;
int balance;
};
// this is set up to be inherited by another class
class BST {
public:
BST(); // intializes Root
~BST(); // destructor calls dtraverse to destroy the dynamic tree
// PURPOSE: these will show the vertices in IN order
// TO CALL: No parameter but provide a pointer to
// the root vertex in calling INorderTraversal
void Display();
void InOrderTraversal(Vertex*); // recursive
// PURPOSE: these will search in PRE order - same as Depth First
// TO CALL: provide the element to search for; provide a pointer to
// the root vertex in calling PREorderSearch
bool Search(el_t);
bool PreOrderSearch(Vertex*, el_t); // recursive
AI-generated content may present inaccurate or offensive content that does not represent bartleby’s views.
Unlock instant AI solutions
Tap the button
to generate a solution
