6

I'm currently implementing a red-black tree data structure to perform some optimizations for an application.

In my application, at a given point I need to remove all elements less than or equal to a given value (you can assume that the elements are integers) from the tree.

I could delete the elements one by one, but I would like to have something faster. Therefore, my question is: if I delete a whole subtree of a red-black tree, how could I fix the tree to recover the height and color invariants?

4

3 回答 3

8

从红黑树中删除一个元素需要 O(log n) 时间，其中 n 是当前树中的元素数。

如果您只删除少数元素，那么最好只一个一个地删除它们，以 O(k log n) 操作结束（k = 删除的元素，n = 删除前树中的元素）。

但是如果你知道你要移除大量的节点（例如树的 50% 或更多），那么最好遍历你想要保留的元素 (O(k') 操作 where k' = elements将保留什么），然后报废树（O(1) 或 O(n)，具体取决于您的内存管理方案）并重建树（O(k' log k')）操作。总复杂度为 O(k')+O(k' log k') = O(k' log k')，当 k' < k 时明显小于 O(k log n)（你保持小于 50树的百分比）。

好吧，无论如何，当你要删除大部分元素时，最好在实践中枚举你想要保留的元素，然后重建树。

于 2011-04-14T15:36:52.507 回答
7

编辑：以下是通用子树删除。您需要的只是一个Split操作（根据您的实际问题内容）。

在最坏的情况下，可以删除红黑树的整个子树O(log n)。

众所周知，Split对Join红黑树的操作可以及时完成O(log n)。

拆分：给定一个值 k 和一个红黑树 T，将 T 拆分为两个红黑树 T1 和 T2，使得 T1 中的所有值 < k 并且 T2 中的所有值 >= k。

Join：将两棵红黑树 T1 和 T2 组合成一棵红黑树 T。 T1 和 T2 满足 T1 中的最大值 <= T2 中的最小值（或简称 T1 <= T2）。

你需要的是二Splits加一Join。

在您的情况下，您需要删除的子树将对应于一系列 values L <= v <= U。

所以你首先Split在 L 上，在 T1 <= T2 的情况下获得 T1 和 T2。SplitU 上的 T2 得到 T3 和 T4 且 T3 <= T4。现在Join是树 T1 和 T4。

在 pseudoCode 中，您的代码将如下所示：

Tree DeleteSubTree( Tree tree, Tree subTree) {

    Key L = subTree.Min();
    Key U = subTree.Max();

    Pair <Tree> splitOnL = tree.Split(L);
    Pair <Tree> splitOnU = splitOnL.Right.Split(U);

    Tree newTree = splitOnL.Left.Join(splitOnU.Right);

    return newTree;
}

有关更多信息，请参阅：https ://cstheory.stackexchange.com/questions/1045/subrange-of-a-red-and-black-tree

于 2011-04-14T19:02:02.837 回答
2

从红黑树中批量删除是很困难的，因为黑高不变量被搞得一团糟。假设您没有进行（软）实时操作，我会一个一个地删除（因为您必须一个一个地插入它们，我们在这里讨论的是一个较小的常数因子）或切换到一个展开树.

于 2011-04-14T15:08:22.277 回答