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?
There is an implementation of the algorithm you need in the archive at https://github.com/CGAL/cgal/releases/download/releases%2FCGAL-5.0.3/CGAL-5.0.3.zip
in the file include/cgal/MultiSet.h starting at line 2617 the function is Multiset<Type, Compare, Allocator>::split
The algorithm is also described in the paper at https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwjpqfz_sKrrAhVkFjQIHbnbDYYQFjADegQIAhAB&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.109.4875%26rep%3Drep1%26type%3Dpdf&usg=AOvVaw26DS8sY7M2fmunxpDfXUZn