Investigate what must happen to delete a key from a Binary Search Tree. Is deletion always as fast as insertion?
I looked up insertions and deletions in a BST. It appears that a deletion is more complex because the nodes need to be re-routed, which also means that the keys need to be reassigned and reorganized. As far as speed is concerned, based on the complexity of the deletion, I assume that this means that a deletion is not as fast as an insertion.
Is this a correct assumption? Thanks
Although it may initially appear that insertion should be faster, I'm not at all convinced that this is really true, at least to any significant degree.
When we do an insertion, we always insert the new node as a child of a leaf node. We have to traverse the tree to the leaf node to do the insertion.
When we do a deletion, we have three cases to consider. The simplest is that we're deleting a leaf node. In such a case, we set the parent's pointer to that leaf node to a null pointer, and we release the memory occupied by the leaf. Not really any different from the insertion.
If the node to be deleted is a non-leaf node with one child, the task is only marginally more difficult: we set the parent of the current node to point to the child of the node to be deleted, and (again) release the memory occupied by the node we're deleting.
The only time we encounter anything that could be considered extra work at all is when we have to delete a non-leaf node that has two children. In this case, we need to find a leaf node that's a child of that node--either the right-most descendant of its left child, or the left-most descendant of its right child. We swap that node into the place of the one we're deleting and release its memory.
The thing to keep in mind here is that for insertion, we started by traversing the tree to a leaf, then we insert. In the case of deletion, it's possible that we reach the node to delete before traversing all the way to a leaf--but even in the worst case, we still just continue traversing until we reach the leaf (something we do for insertion anyway), the assign pointers to move that node into the place of the one being deleted.
There might be one or two extra assignments here (depending primarily on how you implement things), but at most the difference is extremely small.
From a practical viewpoint, any real performance difference is likely to come down to one question: whether the memory management you're using attempts to balance the costs of allocation and deletion, or favors one over the other (and of so, which).
In short, depending on how your heap is managed, the slowest part of this may well be allocation or deletion of the memory for the node, and the tree manipulation is basically lost in the noise.