Re: Deletion from a red/black tree


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.


--
Lech Duraj
.

Relevant Pages

  • Re: Deletion from a red/black tree
    ... I have read that delete takes amortized constant time if you supply the pointer to the element being deleted but that is exactly the version described in cormen and it is said to take Otime, so how does this fit together? ... 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. ... 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. ...
    (comp.theory)
  • Re: hacker challenge - traverse a list
    ... Here is a little challenge - print the contents of a binary tree ... I assume there are no up links, otherwise the algorithm is trivial. ... space hence unbounded number of bits in a pointer? ... Left branch *not* leaf, rotate: ...
    (comp.programming)
  • Re: question of style
    ... end of the day the quality of the code depends more on the quality of ... or the equivalent null pointer exceptions in Java, C, or whatever? ... But you have implemented a mutable tree. ...     def get: ...
    (comp.lang.python)
  • Re: Help me come up with a few and simple programming challenges
    ... >Dave Vandervies wrote: ... >> language, I'd probably pass around a pointer to the list's head pointer ... >(define (sublist tree lo hi) ...
    (comp.lang.scheme)
  • Re: Reading XML stream using unmanaged c++
    ... You don't need a back pointer to implement tree structures. ... but a back pointer is a handy thing to have when using a DOM node. ... XML is metadata, but an XML document is an XML metadata structure with actual data ...
    (microsoft.public.vc.mfc)