template<class T>
void BinarySearchTree<T>::remove(BSTNode<T>* nodeToDelete)
{
sorted = false;
if(nodeToDelete->getLeftChild() == nullptr && nodeToDelete->getRightChild() == nullptr) //No Children
{
if(root == nodeToDelete)
root = nullptr;
setParentsChildNodeToNull(nodeToDelete);
eraseNode(nodeToDelete);
}
else if(nodeToDelete->getRightChild() == nullptr) //Left child only
{
BSTNode<T>* newRoot = maximum(nodeToDelete->getLeftChild());
if(nodeToDelete->getLeftChild() != newRoot)
{
if(newRoot->getLeftChild())
{
newRoot->getParent()->setRightChild(newRoot->getLeftChild());
newRoot->getLeftChild()->setParent(newRoot->getParent());
}
else
{
newRoot->getParent()->setRightChild(nullptr);
}
nodeToDelete->getLeftChild()->setParent(newRoot);
newRoot->setLeftChild(nodeToDelete->getLeftChild());
}
newRoot->setParent(nodeToDelete->getParent());
if(newRoot->getParent() != nullptr)
replaceOldChildInParent(nodeToDelete, newRoot);
if(nodeToDelete == root)
root = newRoot;
eraseNode(nodeToDelete);
}
else if(nodeToDelete->getLeftChild() == nullptr) //Right child only
{
BSTNode<T>* newRoot = minimum(nodeToDelete->getRightChild());
if(nodeToDelete->getRightChild() != newRoot)
{
if(newRoot->getRightChild())
{
newRoot->getParent()->setLeftChild(newRoot->getRightChild());
newRoot->getRightChild()->setParent(newRoot->getParent());
}
else
{
newRoot->getParent()->setLeftChild(nullptr);
}
nodeToDelete->getRightChild()->setParent(newRoot);
newRoot->setRightChild(nodeToDelete->getRightChild());
}
newRoot->setParent(nodeToDelete->getParent());
if(newRoot->getParent() != nullptr)
replaceOldChildInParent(nodeToDelete, newRoot);
if(nodeToDelete == root)
root = newRoot;
eraseNode(nodeToDelete);
}
else //Both children exsist
{
BSTNode<T>* newRoot = maximum(nodeToDelete->getLeftChild());
if(nodeToDelete->getLeftChild() != newRoot)
{
if(newRoot->getLeftChild())
{
newRoot->getParent()->setRightChild(newRoot->getLeftChild());
newRoot->getLeftChild()->setParent(newRoot->getParent());
}
else
{
newRoot->getParent()->setRightChild(nullptr);
}
nodeToDelete->getLeftChild()->setParent(newRoot);
newRoot->setLeftChild(nodeToDelete->getLeftChild());
}
newRoot->setRightChild(nodeToDelete->getRightChild());
newRoot->getRightChild()->setParent(newRoot);
newRoot->setParent(nodeToDelete->getParent());
if(newRoot->getParent() != nullptr)
replaceOldChildInParent(nodeToDelete, newRoot);
if(nodeToDelete == root)
root = newRoot;
eraseNode(nodeToDelete);
}
}
Binary Search Tree Remove Node Critique
Author
I have written the code needed to remove a node from a non-self balancing BST. I've put it through every test I could think of and it seems to be pretty solid, but the method is pretty long. I have been trying to figure out a way to re-factor it to make it more streamlined (if that is possible?). However I haven't had much luck. The code for removing a node with a single child is pretty much identical. The only difference is that the children they get/set are their opposite. I figure some special pointer magic would make this work but haven't had any luck.
Seems like a lot of code to remove a node. Wait, just looked over my own binary tree delete code.
Seems about right.
tree* left = node->left, right = node->right;
// Has 2 Children
if( left->value && right->value ) {
// Move left nodes to leftmost right node
// Get leftmost right node
tree* successor = right;
while( successor->left->value )
successor = successor->left;
delete successor->left;
successor->left = left;
// Replace this node with right node
delete node->value;
node->value = right->value;
node->left = right->left;
node->right = right->right;
delete right;
}
// Has left child
else if( left->value ) {
// No right value, so delete
delete right;
// Delete this node's value and replace it with left node value
delete node->value;
node->value = left->value;
node->left = left->left;
node->right = left->right;
// Delete left node
delete left;
} else if( right->value ) {
// No left value so delete
delete left;
// Delete this node's value and replace it with right node value
delete node->value;
node->value = right->value;
node->left = right->left;
node->right = right->right;
// Delete right node
delete right;
} else {
// This node becomes dead leaf
delete node->value;
node->value = NULL;
delete left;
delete right;
}
return node;
Seems about right.
For reference, here's an ordered binary tree remove function that I wrote some time ago which uses the less-than operator for ordering and returns the removed node rather than deleting it:
I think you'll agree that it's considerably less complex, and probably still shorter despite the thorough commenting.
// O(n) : Remove selected item - caller responsible for deallocation
template <class TNode, class TKey>
TNode *TreeRemove(TNode *&head, TKey &rem) {
TNode *found;
//unexpected case: the item was not even in the tree
if (head == NULL) {
return NULL; // Not found
} else if (rem < *head) {
//the item to be removed is in the left sub-tree
return TreeRemove(head->left, rem);
} else if (*head < rem) {
//the item to be removed is in the right sub-tree
return TreeRemove(head->right, rem);
} else {
//if we got here then we have found the item
found = head;
if (head->left == NULL) {
//there is no left node, put the right one as the new parent
//the right could be NULL, but if so this also does what we want.
head = head->right;
} else if (head->right == NULL) {
//there was no right node, but we already know there is a left one so use that
head = head->left;
} else {
//difficult case: We need to find a replacement for this node in the tree.
//this uses leftmost node of the right sub-tree
TNode *temp = TreeRemoveMin_Aux(head->right);
//now copy all of the old details in the node being reused
temp->left = head->left;
temp->right = head->right;
//switch it with the old one
head = temp;
}
return found;
}
}
template <class TNode>
TNode *TreeRemoveMin_Aux(TNode *&head) {
TNode *found;
//special case used for finding the node to replace a higher deleted node
if (head->left != NULL)
found = TreeRemoveMin_Aux(head->left);
else {
//if we got here then we have found the item
found = head;
//there is no left node, put any right one as the new parent
head = head->right;
}
return found;
}I think you'll agree that it's considerably less complex, and probably still shorter despite the thorough commenting.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
