破坏性地分裂红黑树？

Question

我想用红黑树实现一个优先级队列。使用二进制堆是 O(log n) 最坏的删除情况，我将立即从队列中删除许多键，所以我想要 O(log n) 批量删除的最坏情况，而不是 O(m log n ) 最坏情况，其中 m 是一次删除的密钥数。我可能只会删除少数键。

我不再需要那棵老树了。我怎样才能破坏性地分割红黑树（这显然可以在 O(log n) 中以某种方式完成）来实现这一点，同时保持黑色高度不变？

Answer 1

存档中有您需要的算法的实现，网址为 https://github.com/CGAL/cgal/releases/download/releases%2FCGAL-5.0.3/CGAL-5.0.3.zip

在文件 include/cgal/MultiSet.h 中，从第 2617 行开始，函数是 Multiset::split

该算法也在 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

的论文中进行了描述