Есть ли алгоритм, который позволяет удалять несколько узлов в RB или единственный алгоритм для удаления узлов из RB - это сделать так:
1. Удалите один и
2. При необходимости исправить деревоАлгоритм для удаления нескольких элементов из дерева Red-Black
Если нет ограничений, указывающих на то, что дерево должно оставаться сбалансированным при удалении нескольких узлов, мне представляется разумным исправить это дерево после нескольких удалений.
Цель балансировки дерева после каждого удаления состоит в том, чтобы убедиться, что операция удаления согласована в его вычислительной стоимости. Если вы не нуждаетесь в том, чтобы удаления были согласованными таким образом, вы могли бы написать свой алгоритм удаления по-разному. Операция fixup будет более длинным вычислением, чем после одного удаления. Вероятно, это тоже будет более сложным.
Как я решил эту проблему, было создать связанный список удаляемых узлов и последовательно использовать стандартный метод удаления. Мне было бы интересно узнать, есть ли лучший алгоритм для массового удаления.
Если удалено более половины узлов, вы можете выбросить существующее дерево и построить новое за меньшее время, так как вставка и удаление имеют одинаковую стоимость.
Я бы предложил использовать Treap вместо дерева Red-Black, так как балансировка дерева в различных сценариях кажется проще с помощью Treap v/s дерева Red-Black. У меня такая же проблема, как у вас, но с Treaps. https://cstheory.stackexchange.com/questions/20495/algorithm-to-bulk-delete-nodes-from-a-treap
Не уверен, что ожидаемые границы высот остаются действительными после объемного удаления (алгоритм, упомянутый в вопросе).
Возможно, вас заинтересует структура данных под названием TeardownTree. Он поддерживает операцию delete_range, которая работает в O(k + log n) времени, где n - это начальное количество элементов в дереве, а k - количество элементов, удаленных (и возвращенных вызывающему абоненту). Полное раскрытие: я автор.
Я должен подчеркнуть, что структура данных не поддерживает операцию insert, но оптимизирована для clone и delete_range. Я написал неофициальный description of the algorithm. При всех оптимизации код теперь значительно отличается от этого документа, но его должно хватить, чтобы понять идею.
Извините, но это не имеет смысла. Если вы удалите узлы из дерева без фиксации дерева, вы останетесь с указателями налево и вправо. – 2011-03-14 13:21:32
Я думаю, что Филлис подразумевал, что указатели будут подключены после удаления узла, но он не будет перебалансироваться до тех пор, пока весь LL удаленных узлов не будет удален. – reuscam
Я думаю, что это может быть плохим подходом, несмотря на то, что сложность перебалансирования дерева после множественного удаления, вероятно, будет чрезмерно выше суммы одиночных удалений. С тех пор я работал с ними. – reuscam