c++ - 从红黑树中删除多个元素的算法

Question

是否有一种算法允许删除 RB 中的多个节点，或者从 RB 中删除节点的唯一算法是以某种方式执行此操作：
1. 删除一个和
2. 如有必要，修复树

Answer 1

如果超过一半的节点被删除，您可以丢弃现有树并在更短的时间内构建新树，因为插入和删除的成本相同。

Answer 2

如果在执行多节点删除时没有限制说树必须保持平衡，那么对我来说，您可以在执行多次删除后修复树似乎是合理的。

每次删除后平衡树的目的是确保删除操作的计算成本是一致的。如果您不要求删除以这种方式保持一致，则可以以不同的方式编写删除算法。不过，修复操作将比仅删除一次后进行更长时间的计算。它也可能是一个更复杂的。

Answer 3

您可能对名为TeardownTree的数据结构感兴趣。它支持及时delete_range工作的操作O(k + log n)，其中n是树中的初始项目数，k是删除（并返回给调用者）的项目数。全面披露：我是作者。

不得不强调的是，数据结构不支持insert运算，而是针对cloneand进行了优化delete_range。我已经写了该算法的非正式描述。通过所有优化，代码现在与该文档有很大不同，但应该足以掌握这个想法。

Answer 4

我建议使用 Treap 而不是 Red-Black 树，因为使用 Treap v/sa Red-Black 树在各种情况下平衡树似乎更容易。我和你有同样的问题，但是Treaps。https://cstheory.stackexchange.com/questions/20495/algorithm-to-bulk-delete-nodes-from-a-treap

不确定预期的高度范围在批量删除后是否仍然有效（问题中提到的算法）。

Answer 5

我解决这个问题的方法是创建一个要删除的节点的链表，并在它们上连续使用标准的删除方法。我很想知道是否有更好的批量删除算法。