Алгоритм удаления нескольких элементов из красно-черного дерева

Question

Существует ли алгоритм, который позволяет удалять несколько узлов в RB, или единственный алгоритм, который удаляет узлы из RB, состоит в следующем:
1. Удалить один и
2. при необходимости исправить дерево

Answer 1

Если удаляется более половины узлов, вы можете выбросить существующее дерево и построить новое за меньшее время, поскольку стоимость вставки и удаления одинакова.

Answer 2

Возможно, вас заинтересует структура данных с именем TeardownTree .Он поддерживает операцию delete_range, которая работает за O(k + log n) время, где n - это начальное количество элементов в дереве, а k - это количество элементов, удаленных (и возвращенных вызывающей стороне).Полное раскрытие: я автор.

Я должен подчеркнуть, что структура данных не поддерживает операцию insert, но оптимизирована для clone и delete_range.Я написал неформальное описание алгоритма .После всех оптимизаций код теперь значительно отличается от этого документа, но этого должно быть достаточно, чтобы понять идею.

Answer 3

Если нет ограничения, согласно которому дерево должно оставаться сбалансированным, пока вы выполняете удаление нескольких узлов, мне кажется разумным, что вы можете исправить дерево после выполнения нескольких удалений.

Цель балансировки дерева после каждого удаления - убедиться, что операция удаления соответствует своей вычислительной стоимости. Если вам не требуется, чтобы удаления были согласованы таким образом, вы могли бы написать свой алгоритм удаления по-другому. Однако операция исправления будет более продолжительной, чем после одного удаления. Это также, вероятно, будет более сложным.

Answer 4

Я бы предложил использовать Treap вместо красно-черного дерева, поскольку балансировка дерева в различных сценариях кажется проще с Treap v / sa Красно-черным деревом.У меня такая же проблема, как и у вас, но с Трипсом.https://cstheory.stackexchange.com/questions/20495/algorithm-to-bulk-delete-nodes-from-a-treap

Не уверен, что ожидаемые границы высоты остаются действительными после массового удаления (алгоритм, упомянутый в вопросе).

Answer 5

Способ, которым я решил эту проблему, заключался в создании связанного списка удаляемых узлов и последующем использовании стандартного метода удаления для них.Мне было бы интересно узнать, есть ли лучший алгоритм для массового удаления.