#data-structures #tree #binary-search-tree #priority-queue #red-black-tree
#структуры данных #дерево #двоичное дерево поиска #приоритет-очередь #красно-черное дерево
Вопрос:
Я хотел бы реализовать очередь приоритетов, используя красно-черное дерево. Использование двоичной кучи — это O (log n) наихудший вариант для удаления, и я буду удалять много ключей из очереди одновременно, поэтому я хочу O (log n) наихудший вариант для массового удаления, а не O (m log n) наихудший случай, где m — количество ключей, удаляемых одновременно. Вероятно, я удалю только меньшинство ключей.
Мне больше не понадобится старое дерево. Как я могу деструктивно разделить красно-черное дерево (что, по-видимому, каким-то образом можно выполнить в O (log n)), чтобы выполнить это, сохраняя инвариант высоты черного?
Ответ №1:
В архиве есть реализация нужного вам алгоритма по адресу https://github.com/CGAL/cgal/releases/download/releases/CGAL-5.0.3/CGAL-5.0.3.zip
в файле include/cgal/MultiSet.h, начинающемся со строки 2617, функция является Multiset<Тип, сравнение, распределитель>::split
Алгоритм также описан в статье на https://www.google.com/url?sa=tamp;rct=jamp;q=amp;esrc=samp;source=webamp;cd=amp;ved=2ahUKEwjpqfz_sKrrAhVkFjQIHbnbDYYQFjADegQIAhABamp;url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.4875&rep=rep1&type=pdfamp;usg=AOvVaw26DS8sY7M2fmunxpDfXUZn
Комментарии:
1. Большое вам спасибо, увидеть реальную реализацию бесценно!