1

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

4

5 回答 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 回答