Массовые операции на красно-черных деревьях?

Question

В моем проекте мне нужно очень часто обновлять / удалять / вставлять несколько RB-деревьев.Дело в том, что обновления приходят в пакетах элементов, таких как:

100 новых элементов для вставки, 100 ключей для удаления и т. Д.

Кроме того, элементы в каждом пакете сортируются по одномуключ, с которым построено дерево.

Можно ли каким-либо образом использовать это свойство моих данных для повышения производительности операций обновления / удаления / вставки?Например, может быть есть какой-нибудь массив удаленных предметов для RB-Tree?

Answer 1

Предполагая, что вам не нужны конкретно RB-деревья, но поиск O (logn), я бы предложил использовать списки пропусков и просто объединить существующий список пропусков со списком пропусков для входящего "пакета".