I have the folloiwng assignment in c++ data structures. I need help with impleme
ID: 665810 • Letter: I
Question
I have the folloiwng assignment in c++ data structures. I need help with implementing the remove method. I will post the assignment and the code:
Create the following remove method for the binary search tree for removing elements:
void remove(const T & t);
The deletion algorithm works as follows:
Find the node to be removed.
If it does not exist, throw a BinarySearchTreeNodeNotFound exception and stop.
If it does exist, determine how many children it has. There are three cases:
1. No children: set its parent’s child pointer to NULL and then delete it.
2. One child: set its parent’s child pointer to its one child and then delete it.
3. Two children: Find the node with the largest element in its left subtree. Replace the element in the node to be deleted with the largest element in its left subtree. Delete the node containing the largest element in the left subtree.
To find the node with the largest element in left subtree, navigate first to the root of the left subtree of the node to be deleted. Then follow the right pointers as far as possible (until a NULL right pointer is found). Copy the element in the right-most node of the left subtree to the node to be deleted then delete the right-most node. The right-most node will have either zero or one child (because its right pointer is NULL). Delete the right-most node as in cases 1 or 2.
Here is the code:
//BinarySearchTree.h
#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H
#include "BinarySearchTreeNode.h"
namespace cs20a
{
template<class T>
class BinarySearchTree
{
public:
BinarySearchTree();
BinarySearchTree(const BinarySearchTree &original);
~BinarySearchTree();
const BinarySearchTree & operator=(const BinarySearchTree &original);
void insert(const T & value);
void remove(const T & value);
bool contains(const T & value) const;
T & retrieve(T & value) const;
void makeEmpty();
bool isEmpty() const;
void inOrder(void(*func)(const T &)) const;
int getSize() const;
private:
BinarySearchTreeNode<T> *root;
int size;
void insert(const T & value, BinarySearchTreeNode<T>* node);
void remove(const T & value, BinarySearchTreeNode<T>* node);
bool contains(const T& value, BinarySearchTreeNode<T>* node) const;
T & retrieve(T & value, BinarySearchTreeNode<T>* node) const;
void makeEmpty(BinarySearchTreeNode<T>* node);
inline void deepCopy(const BinarySearchTreeNode<T>* node);
void inOrder(void(*func)(const T &), BinarySearchTreeNode<T>* node) const;
};
}
#endif
//BinarySearchTree.cpp
#include <iostream>
#include "BinarySearchTree.h"
#include "BinarySearchTreeNode.h"
#include "BinarySearchTreeNodeExists.h"
#include "BinarySearchTreeNodeNotFound.h"
namespace cs20a
{
template<class T>
BinarySearchTree<T>::BinarySearchTree() : root(NULL), size(0)
{}
template<class T>
BinarySearchTree<T>::BinarySearchTree(const BinarySearchTree &original) : root(NULL), size(0)
{
deepCopy(original.root);
}
template<class T>
const BinarySearchTree<T> & BinarySearchTree<T>::operator=(const BinarySearchTree &original)
{
if (this == &original)
return *this;
makeEmpty();
deepCopy(original.root);
return *this;
}
template<class T>
BinarySearchTree<T>::~BinarySearchTree()
{
makeEmpty();
}
template<class T>
inline void BinarySearchTree<T>::deepCopy(const BinarySearchTreeNode<T>* node)
{
if (node != NULL)
insert(node->value);
if (node->left != NULL)
deepCopy(node->left);
if (node->right != NULL)
deepCopy(node->right);
}
template<class T>
void BinarySearchTree<T>::makeEmpty()
{
makeEmpty(root);
root = NULL;
}
template<class T>
void BinarySearchTree<T>::makeEmpty(BinarySearchTreeNode<T>* node)
{
if (node != NULL) {
if (node->left != NULL)
makeEmpty(node->left);
if (node->right != NULL)
makeEmpty(node->right);
delete node;
node = NULL;
size--;
}
}
template<class T>
void BinarySearchTree<T>::insert(const T &value)
{
if (root == NULL)
{
root = new BinarySearchTreeNode<T>(value, NULL, NULL);
size++;
}
else
{
insert(value, root);
}
}
template<class T>
void BinarySearchTree<T>::insert(const T &value, BinarySearchTreeNode<T>* node)
{
if (value < node->value)
{
if (node->left == NULL)
{
node->left = new BinarySearchTreeNode<T>(value, NULL, NULL);
size++;
}
else
{
insert(value, node->left);
}
}
else
if (value > node->value)
{
if (node->right == NULL)
{
node->right = new BinarySearchTreeNode<T>( value, NULL, NULL);
size++;
}
else
{
insert(value, node->right);
}
}
else
{
throw BinarySearchTreeNodeExists();
}
}
template<class T>
void BinarySearchTree<T>::remove(const T &value)
{
// *** Add code here ***
// *** Add code here ***
// *** Add code here ***
}
template<class T>
void BinarySearchTree<T>::remove(const T &value, BinarySearchTreeNode<T>* node)
{
// *** Add code here ***
// *** Add code here ***
// *** Add code here ***
}
template<class T>
T & BinarySearchTree<T>::retrieve(T &value) const
{
return retrieve(value, root);
}
template<class T>
T & BinarySearchTree<T>::retrieve(T &value, BinarySearchTreeNode<T>* node) const
{
if (node == NULL)
throw BinarySearchTreeNodeNotFound();
else if (value < node->value)
return retrieve(value, node->left);
else if (value > node->value)
return retrieve(value, node->right);
else
return node->value;
}
template<class T>
bool BinarySearchTree<T>::contains(const T &value) const
{
if (root == NULL)
return false;
else
return contains(value, root);
}
template<class T>
bool BinarySearchTree<T>::contains(const T &value, BinarySearchTreeNode<T> *node) const {
if (node == NULL)
return false;
else if (value < node->value)
return contains(value, node->left);
else if (value > node->value)
return contains(value, node->right);
else // value == node->value
return true;
}
template<class T>
void BinarySearchTree<T>::inOrder(void(*func)(const T &)) const
{
inOrder(func, root);
}
template<class T>
void BinarySearchTree<T>::inOrder(void(*func)(const T &), BinarySearchTreeNode<T>* node) const
{
if (node != NULL)
{
inOrder(func, node->left);
if (func != NULL)
func(node->value);
inOrder(func, node->right);
}
}
template<class T>
bool BinarySearchTree<T>::isEmpty() const
{
return root == NULL;
}
template<class T>
int BinarySearchTree<T>::getSize() const
{
return size;
}
}
//BinarySearchTreeNode.h
#ifndef BINARYSEARCHTREENODE_H
#define BINARYSEARCHTREENODE_H
#include <iostream>
namespace cs20a
{
template<class T>
struct BinarySearchTreeNode
{
BinarySearchTreeNode() : value(), left(NULL), right(NULL)
{}
BinarySearchTreeNode(const T &t, BinarySearchTreeNode<T> *l = NULL,
BinarySearchTreeNode<T> *r = NULL)
: value(t), left(l), right(r)
{}
T value;
BinarySearchTreeNode<T> *left, *right;
};
}
#endif
//BinarySearchTreeNodeNotFound.h
#ifndef BINARYSEARCHTREENODENOTFOUND_H
#define BINARYSEARCHTREENODENOTFOUND_H
#include <stdexcept>
namespace cs20a
{
class BinarySearchTreeNodeNotFound : public std::logic_error
{
public:
BinarySearchTreeNodeNotFound();
};
}
#endif
//BinarySearchTreeNodeNotFound.cpp
#include "BinarySearchTreeNodeNotFound.h"
namespace cs20a
{
BinarySearchTreeNodeNotFound::BinarySearchTreeNodeNotFound() : logic_error( "Binary Search Tree Node not found")
{}
}
//BinarySearchTreeNodeExists.h
#ifndef BINARYSEARCHTREENODEEXISTS_H
#define BINARYSEARCHTREENODEEXISTS_H
#include <stdexcept>
namespace cs20a
{
class BinarySearchTreeNodeExists : public std::logic_error {
public:
BinarySearchTreeNodeExists();
};
}
#endif
//BinarySearchTreeNodeExists.cpp
#include "BinarySearchTreeNodeExists.h"
namespace cs20a
{
BinarySearchTreeNodeExists::BinarySearchTreeNodeExists() : logic_error( "Binary Search Tree Node not found")
{}
}
//BinarySearchTreeDriver.cpp
#include <iostream>
#include <stdlib.h>
#include <string>
#include "BinarySearchTree.h"
#include "BinarySearchTree.cpp"
using namespace std;
using namespace cs20a;
void printWordLocation(const int & i);
int main()
{
srand(77); // Initialize random seed
int first = 0;
BinarySearchTree<int> bt;
for (int i=0; i < 100; i++)
{
int num = rand() % 100 + 1;
if (i==0) first = num;
if (!bt.contains(num))
bt.insert(num);
}
if (bt.contains(first))
{
cout << "Before Delete" << endl;
bt.inOrder(printWordLocation);
cout << "remove " << first << endl;
bt.remove(first);
cout << "After Delete" << endl;
bt.inOrder(printWordLocation);
cout << endl << endl;
}
for (int i=0; i < 20; i++)
{
int num = rand() % 100 + 1;
if (bt.contains(num))
{
cout << "Before Delete" << endl;
bt.inOrder(printWordLocation);
cout << "remove " << num << endl;
bt.remove(num);
cout << "After Delete" << endl;
bt.inOrder(printWordLocation);
cout << endl << endl;
}
}
return 0;
}
void printWordLocation(const int & i)
{
cout << i << " ";
}
Explanation / Answer
template<class T>
void BinarySearchTree<T>::remove(const T &value)
{
remove(value, root);
}
template<class T>
void BinarySearchTree<T>::remove(const T &value, BinarySearchTreeNode<T>* node)
{
if(node == NULL)
{
throw BinarySearchTreeNodeNotFound();
}
if(node->value == value)
{
BinarySearchTreeNode<T> *temp = node;
// 1. No children
if(node->left == NULL && node->right == NULL)
{
free(node);
}
// 2. One child
else if(node->left == NULL || node->right == NULL)
{
if(node->left == NULL)
{
node = node->right;
delete (node->right);
}
else
{
node = node->left;
delete (node->left);
}
}
// 3. Two children
else
{
temp = node->left;
while(temp->right != NULL)
{
temp = temp->right;
}
remove(value, temp->left);
}
}
else if(node->value < value)
{
remove(value, node->right);
}
else
{
remove(value, node->left);
}
}