Deleting a whole subtree of a red-black tree would keep its properties?

I'm currently implementing a red-black tree data structure to perform some optimizations for an application.

In my application, at a given point I need to remove all elements less than or equal to a given value (you can assume that the elements are integers) from the tree.

I could delete the elements one by one, but I would like to have something faster. Therefore, my question is: if I delete a whole subtree of a red-black tree, how could I fix the tree to recover the height and color invariants?

6
задан dfeuer 24 March 2015 в 00:17
поделиться