I need help with my code. i need to make these member functions... I got the first one to work but the others don't work

Business, Finance, Economics, Accounting, Operations Management, Computer Science, Electrical Engineering, Mechanical Engineering, Civil Engineering, Chemical Engineering, Algebra, Precalculus, Statistics and Probabilty, Advanced Math, Physics, Chemistry, Biology, Nursing, Psychology, Certifications, Tests, Prep, and more.
Post Reply
answerhappygod
Site Admin
Posts: 899603
Joined: Mon Aug 02, 2021 8:13 am

I need help with my code. i need to make these member functions... I got the first one to work but the others don't work

Post by answerhappygod »

I need help with my code.
i need to make these member functions... I got the first one to
work but the others don't work.
There are 5 member functions to implement in this assignment.
Recall that our class is templated with keys of type T.
void insert(T k)
Insert the key k into the tree. Like in the week 9 lab, the BST
should act like a std::set . If k is already in the tree then no
action is taken. After insertion, the size_ variable and the
heights of nodes should be updated accordingly. Also now when
adding the new node containing k to the tree its parent pointer
needs to be set.
Node* successor(T k)
Return a pointer to the node containing the minimum key in the tree
larger than k. Return nullptr if k is the largest key in the tree
or if k is not in the tree.
void delete_min()
Remove the minimum key from the tree. Remember to update size_ and
heights of nodes accordingly. delete_min largely serves as a warmup
for the next function, erase.
void erase(T k)
Locate the node containing key k and remove it. If k is not in the
tree, you do not have to do anything. Don't forget to update size_
and heights of nodes accordingly.
void rotate_right(Node* node)
Implement a right rotation about the node pointed to by
node , as described in Lecture 8.6. This will only be called when
node has a left child. If left_child points to the left child of
*node, then *left_child becomes the parent of *node , and the right
subtree of *left_child becomes the left subtree of *node. Node
heights should again be properly updated after this operation.
#ifndef BST_ASSIGNMENT_HPP
#define BST_ASSIGNMENT_HPP
#include <iostream>
#include <algorithm>
template <typename T>
class BST
{
public:
// We have a Node class with more features now
// In addition to pointers to the left and right
child,
// there is also a pointer to the parent of Node.

// The parent of the root should always be
nullptr
// We also hava a height field to store the height
of
// a node in the tree.
class Node
{
public:
T key;
int height = 0;
Node* left = nullptr;
Node* right = nullptr;
Node* parent = nullptr;
// default constructor
Node(){}
// constructor that takes one or
optionally 2 arguments
// if only one argument is passed in
the second argument
// defaults to nullptr
Node(T k, Node* input_node =
nullptr)
{
key = k;
parent =
input_node;
}
};
private:
// The BST has two private variables, a pointer to
the root
// and an unsigned integer to hold its size
// We make the style choice of indicating these are
private
// data variables by having a trailing underscore in
their names.
Node* root_ = nullptr;
unsigned int size_ = 0;
public:
// Default constructor. No action required on
this one.
BST();
// Destructor. We implement this for
you.
~BST();
//*** Methods for you to implement
// insert
// insert the key k into the BST while maintaining
the BST property
// Like std::set, if k is already in the tree then no
action is taken
// Update the size_ variable and heights of nodes
accordingly
//*** For you to implement
void insert(T k);
// successor
// Return a pointer to the node containing the
smallest key larger
// than k
// Return nullptr if k is the largest key in the
tree
// Also return nullptr if k is not in the tree
//*** For you to implement
Node* successor(T k);
// delete the minimum
// Erase the minimum key in the tree
// Take no action if tree is empty
//*** For you to implement
void delete_min();
// erase
// Locate the key k in the tree and remove it
// If k is not in the tree you do not have to do
anything
// Update the size_ variable and heights of nodes
accordingly
//*** For you to implement
void erase(T k);
// Implement a right rotation about the node
pointed to by
// node, as described in Lecture 8.6. This will
only be
// called when node has a left child.
// If left_child points to the left child of
*node,
// then *left_child becomes the parent of *node, and
the
// right subtree of *left_child becomes the left
subtree of *node.
// Node heights should be properly updated after this
operation.
//*** For you to implement
void rotate_right(Node* node);
//*** End of methods for you to implement
// Returns the number of keys in the tree
// we implement this for you, but it is up to you to
correctly
// update the size_ variable
unsigned size();
// Prints out the keys in the tree via an in-order
traversal
// we implement this for you
void print();
// Returns a pointer to the node containing the
key k
// We implement this for you
Node* find(T k);
// Creates a vector holding the keys in the tree
by
// doing an in-order traversal
// We implement this for you, it is used in our
testing.
std::vector<T> make_vec();
// The next two functions are to check your height
values
// Please do not modify
std::vector<int> your_postorder_heights();
std::vector<int>
real_postorder_heights();
// get_root_value returns the value stored at the
root
// It used for testing purposes
// No action needed on your part
T get_root_value();
// Return a pointer to the node containing the
minimum key in the tree
// We implement this for you
Node* min();
private:
// We found it useful to have a "fix_height"
function.
// This assumes that the subtrees rooted at node's
children have
// correct heights and then walks up the tree from
node to the root
// correcting the heights.
// You can imlement this, or correct the heights
another way
void fix_height(Node* node);
// The rest of these functions are already
implemented
// helper function for the destructor
void delete_subtree(Node* node);
// returns pointer to minimum node in subtree
rooted by node
// Assumes node is not nullptr
Node* min(Node* node);
// helper function for print
void print(Node* node);
// helper function for make_vec
void make_vec(Node* node, std::vector<T>&
vec);
void your_postorder_heights(Node* node,
std::vector<int>& vec);
int real_postorder_heights(Node* node,
std::vector<int>& vec);
};
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!
Post Reply