Я хотел бы реализовать приоритетную очередь, используя красно-черное дерево. Использование двоичной кучи — это O(log n) в худшем случае для удаления, и я буду удалять сразу много ключей из очереди, поэтому я хочу O(log n) в худшем случае для массового удаления, а не O(m log n). ) наихудший случай, где m — количество одновременно удаляемых ключей. Я, вероятно, только удалю меньшинство ключей.
Старое дерево мне больше не понадобится. Как я могу деструктивно разделить красно-черное дерево (что, по-видимому, каким-то образом можно сделать за O (log n)), чтобы выполнить это, сохраняя при этом инвариант высоты черного?
