Programming Assignment 2
In programming assignment 2 you will continue to build on the templated Binary Search Tree class from Week 9 lab. Compared to the Week 9 lab exercise, this time the BST class will use a Node class with more features. In addition to pointers to the left and right children, now the Node class will also have a pointer to the parent of a node. The parent of the root node is nullptr , and otherwise the parent pointer of a node will point to the parent of that node. Parent pointers will allow us to easily trace our way back up a tree, say to go from a leaf back to the root.
We add parent pointers in order to maintain the second new feature of the Node class: now the Node class has integer variable for the height of a node, which should always be equal to the height of the node in the tree. You will have to maintain this property as keys are added and deleted from the tree.
Like in the Week 9 lab, the BST class has two private member variables, root_,a pointer to the root of the tree, and size_ , which maintains the number of keys in the tree.
Copyright By PowCoder代写 加微信 powcoder
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.
There are three files provided in the scaffold.
The header file bst.hpp contains the definitions of all member functions of the BST class and instructions about which functions need to be implemented. All of your implementations should be written in this file. This is the only file that is tested when “mark” is pressed.
The header file unit_tests.hpp contains tests that you can use to check the implementation of your functions. These are the same tests that are checked when you press the “mark” button. We largely recommend that you use the tests here as you are implementing the functions. This way you can test one function at a time, and can add couts as needed to the tests to help in your debugging. The error messages resulting from “mark” are also sometimes not very helpful. Once you regularly pass the tests in unit_tests.hpp you should also pass them in the marker as they are the same tests, although note that many tests are randomised.
The final file is bst.cpp. This is the file that is compiled when “Run” is pressed. You can modify this file as you like. We have provided a skeleton with the names of all the tests in unit_tests.hpp.
There are 15 tests that are run on your code. The first 4 tests are on the insert function. Then are are 2 tests of delete_min and 2 tests of successor. Next are 4 tests of the erase function, and finally 3 tests of the rotate_right function.
test_insert_string: Creates a BST with template type std::string. Checks that the size is correctly updated and BST property holds after inserting some strings. All other tests instantiate the template type with ints.
test_insert_size: Checks that size behaves properly when duplicate keys are tried to be inserted into the tree. Remember the BST should not insert a key again that is already in the tree.
test_insert_values: Tests the BST property after inserting some ints.
test_insert_heights: Tests that the node heights are correct after inserting some ints.
test_delete_min: Inserts some ints into the tree and then repeatedly calls delete_min until tree should be empty.
test_delete_min_heights: Tests that heights are updated properly after delete_min
test_successor: Tests that the successor function returns a pointer to the correct node.
test_successor_max: Tests the successor function on the largest key in the tree (nullptr should be returned).
test_erase: Tests that BST property is maintained after erasing a random key.
test_erase_heights: Tests that heights are updated properly after erasing a random key
test_erase_root: Tests erasing the key at the root.
test_erase_successor_child: Tests the case where we erase the key at a node whose successor is their right child.
test_rotate_right: Tests parent/child relationships after calling rotate_right on a random node that has a left child. Also tests that BST property is preserved.
test_rotate_root: Calls rotate_right on the root.
test_rotate_heights: Checks that heights are updated properly after calling rotate_right on a random node that has a left child.
#ifndef BST_ASSIGNMENT_HPP
#define BST_ASSIGNMENT_HPP
#include
#include
template
// 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
int height = 0;
Node* left = nullptr;
Node* right = nullptr;
Node* parent = nullptr;
// default constructor
// 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)
parent = input_node;
// 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;
// Default constructor. No action required on this one.
// Destructor. We implement this for you.
//*** Methods for you to implement
// 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
// 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();
// 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
// The next two functions are to check your height values
// Please do not modify
std::vector
std::vector
// 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();
// 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
void your_postorder_heights(Node* node, std::vector
int real_postorder_heights(Node* node, std::vector
// Default constructor
// You do not need to change this
template
BST
// Destructor
// We implement this for you
template
BST
delete_subtree(root_);
// helper function for destructor
template
void BST
if(node==nullptr)
delete_subtree(node->left);
delete_subtree(node->right);
delete node;
//*** For you to implement
template
void BST
// You can mostly follow your solution from Week 9 lab here
// Add functionality to set the parent pointer of the new node created
// ++size_;
// Also remember to correct the heights on the path from the newly
// inserted node to the root.
// fix_height(start_fix);
// node will iterate down through the tree starting from the root
Node* node = root_;
// prev_node will hold node’s parent
Node* prev_node = node;
bool went_right;
if(node == nullptr)
root_ = new Node(k);
while(node != nullptr)
prev_node = node;
if(k < node->key)
node = node->left;
went_right = false;
else if (k > node->key)
node = node->right;
went_right = true;
// item already in set
// new node is either left or right child of prev_node
if(went_right)
prev_node->right= new Node(k, prev_node);
prev_node->left= new Node(k, prev_node);
//*** For you to implement
template
typename BST
// There are two cases here.
// If the node containing k has a right child, then
// the successor will be the minimum node in its right subtree
// Otherwise, the successor will be the first node with a key
// bigger than k on the path from the node with key k to the root.
// In other words, it is the node where we last took a left turn when
// searching for the key k.
// dummy return value so compiler does not complain
return root_;
//*** For you to implement
template
void BST
// if tree is empty just return.
//Node* min_node = min();
// Now update pointers to remove min_node from the tree
//delete min_node;
//–size_;
//fix_height(start_fix);
//*** For you to implement
template
void BST
// Step 1: locate node holding key k
// simply return if k is not in tree
// let node_to_remove be a pointer to the node to be removed
// Step 2: find a node, replacement, to replace node_to_remove
// We break this down into 3 cases
// Case 1: node_to_remove has no right child
// Case 2: node_to_remove has no left child
// Case 3: node_to_remove has both children
// in this case replacement is successor of node_to_remove
// There is a further instance of Case 3 that needs special handling.
// This is where replacement is the right child of node_to_remove.
// Once pointers have been correctly adjusted then don’t forget to:
// delete node_to_remove;
// –size_;
// fix the heights from the bottom-most node affected by the changes
//fix_height(start_fix);
//*** For you to implement
template
void BST
// Assumptions: node is not nullptr and must have a left child
// Node* move_up_node = node->left;
// There are 3 pairs (parent and child) of pointers to change
// 1) node’s left child becomes move_up_node’s right child
// 2) node’s original parent becomes move_up_node’s parent
// 3) move_up_node’s right child becomes node
// Correct height of ancestors of node
// fix_height(node);
// The rest of the functions below are already implemented
// returns a pointer to the minimum node
template
typename BST
if(root_ == nullptr)
return root_;
return min(root_);
// returns pointer to minimum node in the subtree rooted by node
// Assumes node is not nullptr
template
typename BST
while(node->left != nullptr)
node = node->left;
return node;
// returns a pointer to node with key k
template
typename BST
Node* node = root_;
while(node != nullptr && node->key != k)
node = k < node->key ? node->left : node->right;
return node;
template
unsigned BST
return size_;
// prints out the keys in the tree using in-order traversal
template
void BST
print(root_);
// you can modify what is printed out to suit your needs
template
void BST
if(node == nullptr)
print(node->left);
std::cout << node->key << " height " << node->height << '\n';
print(node->right);
// This is used in our testing, please do not modify
template
typename std::vector
std::vector
vec.reserve(size_);
make_vec(root_, vec);
return vec;
// This is used for our testing, please do not modify
template
void BST
if(node == nullptr)
make_vec(node->left, vec);
vec.push_back(node->key);
make_vec(node->right, vec);
// This is used for our testing, please do not modify
template
void BST
if(node == nullptr)
your_postorder_heights(node->left, vec);
your_postorder_heights(node->right, vec);
vec.push_back(node->height);
// This is used for our testing, please do not modify
template
int BST
if(node == nullptr)
return -1;
int left_height = real_postorder_heights(node->left, vec);
int right_height = real_postorder_heights(node->right, vec);
int node_height = 1 + std::max(left_height, right_height);
vec.push_back(node_height);
return node_height;
// This is used for our testing, please do not modify
template
typename std::vector
std::vector
vec.reserve(size_);
your_postorder_heights(root_, vec);
return vec;
// This is used for our testing, please do not modify
template
typename std::vector
std::vector
vec.reserve(size_);
real_postorder_heights(root_, vec);
return vec;
// This is used for our testing, please do not modify
template
T BST
if(root_ == nullptr)
//std::cout << "Calling get_root_value on empty tree\n";
T dummy {};
return dummy;
return root_->key;
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com