• Create Account

### #ActualiMalc

Posted 05 November 2012 - 02:40 AM

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:
// 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
} else if (rem < *head) {
//the item to be removed is in the left sub-tree
} else if (*head < rem) {
//the item to be removed is in the right sub-tree
} else {
//if we got here then we have found the item
//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.
} else if (head->right == NULL) {
//there was no right node, but we already know there is a left one so use that
} else {
//difficult case: We need to find a replacement for this node in the tree.
//this uses leftmost node of the right sub-tree
//now copy all of the old details in the node being reused
//switch it with the old one
}
return found;
}
}
template <class TNode>
TNode *found;
//special case used for finding the node to replace a higher deleted node
else {
//if we got here then we have found the item
//there is no left node, put any right one as the new parent
}
return found;
}
I think you'll agree that it's considerably less complex, and probably still shorter despite the thorough commenting.

### #2iMalc

Posted 05 November 2012 - 02:38 AM

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:
template <class TNode>

TNode *found;

//special case used for finding the node to replace a higher deleted node

else {

//if we got here then we have found the item

//there is no left node, put any right one as the new parent

}

return found;

}

// 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

} else if (rem < *head) {

//the item to be removed is in the left sub-tree

} else if (*head < rem) {

//the item to be removed is in the right sub-tree

} else {

//if we got here then we have found the item

//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.

} else if (head->right == NULL) {

//there was no right node, but we already know there is a left one so use that

} else {

//difficult case: We need to find a replacement for this node in the tree.

//this uses leftmost node of the right sub-tree

//now copy all of the old details in the node being reused

//switch it with the old one

}

return found;

}

}

### #1iMalc

Posted 05 November 2012 - 02:38 AM

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:
template <class TNode>

TNode *found;

//special case used for finding the node to replace a higher deleted node

else {

//if we got here then we have found the item

//there is no left node, put any right one as the new parent

}

return found;

}

// 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

} else if (rem < *head) {

//the item to be removed is in the left sub-tree

} else if (*head < rem) {

//the item to be removed is in the right sub-tree

} else {

//if we got here then we have found the item

//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.

} else if (head->right == NULL) {

//there was no right node, but we already know there is a left one so use that

} else {

//difficult case: We need to find a replacement for this node in the tree.

//this uses leftmost node of the right sub-tree

//now copy all of the old details in the node being reused

//switch it with the old one

}