是否有一种算法允许删除 RB 中的多个节点，或者从 RB 中删除节点的唯一算法是以某种方式执行此操作：
1. 删除一个和
2. 如有必要，修复树
问问题
927 次
5 回答
2
如果超过一半的节点被删除，您可以丢弃现有树并在更短的时间内构建新树，因为插入和删除的成本相同。
于 2011-04-15T23:20:08.290 回答
1
如果在执行多节点删除时没有限制说树必须保持平衡，那么对我来说，您可以在执行多次删除后修复树似乎是合理的。
每次删除后平衡树的目的是确保删除操作的计算成本是一致的。如果您不要求删除以这种方式保持一致，则可以以不同的方式编写删除算法。不过，修复操作将比仅删除一次后进行更长时间的计算。它也可能是一个更复杂的。
于 2010-11-08T19:43:40.077 回答
1
您可能对名为TeardownTree的数据结构感兴趣。它支持及时delete_range工作的操作O(k + log n)，其中n是树中的初始项目数，k是删除（并返回给调用者）的项目数。全面披露：我是作者。
不得不强调的是，数据结构不支持insert运算，而是针对cloneand进行了优化delete_range。我已经写了该算法的非正式描述。通过所有优化，代码现在与该文档有很大不同，但应该足以掌握这个想法。
于 2016-12-06T02:50:21.580 回答
0
我建议使用 Treap 而不是 Red-Black 树，因为使用 Treap v/sa Red-Black 树在各种情况下平衡树似乎更容易。我和你有同样的问题，但是Treaps。https://cstheory.stackexchange.com/questions/20495/algorithm-to-bulk-delete-nodes-from-a-treap
不确定预期的高度范围在批量删除后是否仍然有效（问题中提到的算法）。
于 2014-01-08T16:56:04.113 回答
0
我解决这个问题的方法是创建一个要删除的节点的链表，并在它们上连续使用标准的删除方法。我很想知道是否有更好的批量删除算法。
于 2011-03-14T13:22:08.293 回答