Algorithm for removing multiple elements from a Red-Black tree

Is there an algorithm that allows to delete multiple nodes in RB or the only algorithm to delete nodes f开发者_StackOverflow中文版rom RB is to do it in a way:

1. Delete one and

2. if necessary fix tree

If more than half the nodes are being deleted, you can throw away the existing tree and build a new one in less time, since insertion and deletion have the same cost.

If there is no constraint that says the tree must remain balanced while you are doing a multiple node deletion, it seems reasonable to me that you could fix the tree after doing multiple deletes.

The purpose of balancing the tree after each deletion is to make sure the delete operation is consistent in its computational cost. If you do not require deletes to be consistent in this fashion, you could write your delete algorithm differently. The fixup operation will be a more lengthy computation than after just one delete, though. It will also likely be a more complicated one, too.

You might be interested in a data structure called TeardownTree. It supports delete_range operation that works in O(k + log n) time, where n is the initial number of items in the tree and k is the number of items deleted (and returned to the caller). Full disclosure: I am the author.

I have to emphasize that the data structure does not support the insert operation, but is optimized for clone and delete_range. I have written up an informal description of the algorithm. With all the optimizations the code is now significantly different from that document, but it should be enough to grasp the idea.

The way I solved this problem was to create a linked list of nodes to be deleted and to use the standard deletion method on them in succession. I would be interested to know if there is a better algorithm for mass deletion.

I would suggest using a Treap instead of a Red-Black tree, since balancing the tree in various scenarios seems easier with a Treap v/s a Red-Black tree. I'm have the same problem as you, but with Treaps. https://cstheory.stackexchange.com/questions/20495/algorithm-to-bulk-delete-nodes-from-a-treap

Am unsure if the expected height bounds remain valid post bulk-deletion (algorithm mentioned in the question).