Deleting Root Node of a Binary Search Tree
what I ended coming up with was this: keep track of the parent node that is one above the node that replaces the node to be deleted. there will then be 2 cases to consider: the parent is the node to be deleted and parent is not the node to be deleted. by replacing the appropriate parts of the tree at the right case, the structure and invariants of the tree remained ok and the node to be deleted was successfully deleted. technically, it would be the data at the node to be deleted.
else if (toDelete->left != NULL && toDelete->right != NULL) {
// find rightmost child on left that is a leaf
Node* replacement = toDelete->left;
parent = toDelete;
// parent is now the parent of the replacement
while ( replacement->right ) {
parent = replacement;
replacement = replacement->right;
} // By the end, parent will be the node one above replacement
toDelete->key = replacement->key;
if (parent == target)
parent->left = replacement->left;
else
parent->right = replacement->left;
delete replacement;
return true;
}
eggrollers
Updated on June 04, 2022Comments
-
eggrollers almost 2 years
I have this function for deleting a node in a binary search tree which seems to be working EXCEPT in the case where I ask it to delete the root node. It is supposed to take the right-most value on the left and replace the node with that; however, once that happens, the new root node's children pointers don't seem to point to the original root node's children. Code is as follows:
bool delete_node(Node*& root, TYPE data) { Node* toDelete; Node* parent; // This function is defined appropriately elsewhere, and finds the target to be deleted toDelete = find(data, root); if (!toDelete) { return false; } // This function is defined appropriately elsewhere, and finds the parent of the node to be deleted parent = find_parent(root, toDelete); // Other cases left out because they work // If the target node has two children: if (toDelete->left && toDelete->right) { // find rightmost child on left that is a leaf Node *replacement = toDelete->left; while (replacement->right) { replacement = replacement->right; } // set the target node's data toDelete->data = replacement->data; if (parent) { if ( parent->data < toDelete->data ) { parent->right = replacement; } else { parent->left = replacement; } } else { // if node has no parents, then it is the root and should be replaced with replacement // This line here is what seems to be causing my trouble...I think root = replacement; } parent = find_parent(toDelete, replacement); if (parent) { if (parent->left == replacement) parent->left = NULL; else parent->right = NULL; } delete toDelete; return true; } }
Thanks in advance!