I would like to implement a priority queue using a red-black tree. Using a binary heap is O(log n) worst case for deletion, and I will be removing many keys from the queue at once, so I want O(log n) worst case for the bulk deletion, rather than O(m log n) worst case, where m is the number of keys being removed at once. I will probably only be removing a minority of the keys.
I will not need the old tree anymore. How can I split a red-black tree destructively (which apparently can somehow be done in O(log n)) to accomplish this, while maintaining the black height invariant?
