Re: Deletion from a red/black tree

Lech Duraj wrote:

In Introduction to Algorithms by Thomas Cormen insertion and deletion is said to take O (lg n) time.

I have read that delete takes amortized constant time if you supply the pointer to the element being deleted (you can omit the searching) but that is exactly the version described in cormen and it is said to take O(lg n) time, so how does this fit together?

Another thing, delete also use tree-successor which runs in the height of the tree so this would also slow down delete to O(lg n).

Try to use "lazy deletion". Instead of removing a node, just mark it as "deleted" (and of course answer negatively for all queries on this element). When the number of marked nodes exceeds half the size of the tree, rebuild it from scratch, perfectly balanced, without marked nodes - it's easy to do it in linear time. This gives amortized O(1) time for deleting (if the pointer is supplied!), while keeping logarithmic height of the tree.



On the wiki page about red black trees they describe that re balancing can be done amortized constant time but they don't mention that this is because that "lazy deletion" is used. So if you are not using lazy deletion it should still be possible in amortized constant time. But I still don't see how tree-successor can be done in amortized constant time.
.