BELOW is my code for a remove function in C++ for a binary search tree. This cod
ID: 3810705 • Letter: B
Question
BELOW is my code for a remove function in C++ for a binary search tree. This code doesnt seem to be working and I was hoping for suggestions on how to perfect my helper function so that it would successfully find, remove, and remake the binary search tree so it is legal, then update the size
BinaryTreeNode* parent;
virtual void removeHelper(BinaryTreeNode* node, const Key& key)
{
if (node == nullptr)
{
return;
}
else if (keyLessThan(key, node->_key))
{
parent = node;
removeHelper(node->_left, key);
}
else if (keyLessThan(node->_key, key))
{
parent = node;
removeHelper(node->_right, key);
}
else if (keyEquals(key, node->_key))
{
//if node to delete has no children
if (node->_left == nullptr && node->_right == nullptr)
{
node = nullptr;
}
//if node to delete has two children
else if (node->_left != nullptr && node->_right != nullptr)
{
//and it is the parents left child
if (keyEquals(parent->_left->_key, node->_key))
{
parent->_left->_key = minHelper(node->_right)->_key;
}
else //it is the parents right child
{
parent->_right->_key = minHelper(node->_right)->_key;
}
}
//if node to delete has one child
else
{
//and it is the parents left child
if (keyEquals(parent->_left->_key, node->_key))
{
node->_left == nullptr ? parent->_left->_key = node->_right->_key : parent->_left->_key = node->_left->_key;
}
else //it is the parents right child
{
node->_left == nullptr ? parent->_right->_key = node->_right->_key : parent->_right->_key = node->_left->_key;
}
}
}
return;
node->_size = 1 + size(node->_left) + size(node->_right);
}
public:
// remove key (and its value) from table
virtual void remove(const Key& key)
{
removeHelper(_root, key);
}
HERE IS THE CODE FOR A BINARY TREE ELEMENT
protected:
struct BinaryTreeNode
{
Key _key;
Value _value;
BinaryTreeNode* _left;
BinaryTreeNode* _right;
unsigned _size;
BinaryTreeNode(const Key& key = Key{},
const Value& value = Value{},
unsigned size = 0,
BinaryTreeNode* ell = nullptr,
BinaryTreeNode* r = nullptr)
: _key{ key }, _value{ value }, _size{ size }, _left{ ell }, _right{ r } {}
BinaryTreeNode(const BinaryTreeNode& that)
: _key{ that._key }, _value{ that._value }, _size{ that._size }, _left{ that._left }, _right{ that._right } {}
~BinaryTreeNode()
{
if (_left != nullptr)
{
delete _left;
_left = nullptr;
}
if (_right != nullptr)
{
delete _right;
_right = nullptr;
}
_size = 0;
}
};
// Key value comparison (less than)
bool keyLessThan(const Key& lhs, const Key& rhs) const { return lhs < rhs; }
// Equality of key values
bool keyEquals(const Key& lhs, const Key& rhs) const { return lhs == rhs; }
// Equality of key values
bool keyLessThanOrEquals(const Key& lhs, const Key& rhs) const
{
return keyEquals(lhs, rhs) || keyLessThan(lhs, rhs);
}
// The container of the <key, value> pairs
BinaryTreeNode* _root;
Explanation / Answer
Your code is messy and had a lot of defects. For instance
1.
//if node to delete has no children
if (node->_left == nullptr && node->_right == nullptr)
{
node = nullptr;
}
It doesn't delete the node, it simply assigns the temporary variable named node to nullptr. The node will be there as it is. You have to remove it completely.
2. Don't use "parent" variable. It unnecessarily complicates things.
3. You can't have anything after return statement
return;
node->_size = 1 + size(node->_left) + size(node->_right);
--------------------------------------------------------------------------------------------------------------
Here is a way simpler and efficient implementation.
--------------------------------------------------------------------------------------------------------------
virtual BinaryTreeNode* node removeHelper(BinaryTreeNode* node, const Key& key)
{
if (node == nullptr)
{
return node;
}
else if (keyLessThan(key, node->_key))
{
node->_left = removeHelper(node->_left, key);
}
else if (keyLessThan(node->_key, key))
{
node->_right = removeHelper(node->_right, key);
}
else // Remove unnecessary check
{
//if the node has only one child or no child
if (node->_left == nullptr)
{
BinaryTreeNode* temp = node->_right;
free(node);
return temp;
}
if (node->_right == nullptr)
{
BinaryTreeNode* temp = node->_left;
free(node);
return temp;
}
// If the node has two children, then get the successor node (smallest from right subtree)
BinaryTreeNode* temp = minHelper(node->_right);
// Replace the content of current node with successor node
node->_key = temp->_key;
// Now delete the inorder successor
node->_right = removeHelper(node->_right, temp->_key);
}
// Aren't you going to update the sizes of sub-trees?
node->_size = 1 + size(node->_left) + size(node->_right);
return node;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.