删除红黑树的整个子树会保留其属性吗？

Question

我目前正在实现一个红黑树数据结构来对应用程序执行一些优化。

在我的应用程序中，在给定点，我需要从树中删除所有小于或等于给定值的元素（您可以假设元素是整数）。

我可以一一删除元素，但我想要更快的东西。因此，我的问题是：如果我删除红黑树的整个子树，如何修复该树以恢复高度和颜色不变量？

Answer 1

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

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

众所周知，红黑树上的Split和Join操作可以在O(log n)时间内完成。

Split ：给定一个值 k 和一棵红黑树 T，将 T 拆分为两棵红黑树 T1 和 T2，使得 T1 中的所有值都

k 以及 T2 >= k 中的所有值。

Join ：将两棵红黑树 T1 和 T2 组合成一棵红黑树 T。T1 和 T2 满足 T1 中的 max <= T2 中的 min（或 T1 <= T2）简而言之）。

您需要的是两个 Split 和一个 Join。

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

因此，您首先在 L 上进行Split，以获得 T1 和 T2，其中 T1 <= T2。在 U 上拆分 T2 得到 T3 和 T4，其中 T3 <= T4。现在加入树T1和T4。

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

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

Answer 2

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

如果只删除少数元素，那么最好将它们一一删除，最终执行 O(k log n) 次操作（k = 删除的元素，n = 删除之前树中的元素）。

但是，如果您知道要删除大量节点（例如，树的 50% 或更多），那么最好迭代要保留的元素（O(k') 操作，其中 k' = elements将保留什么），然后废弃树（O(1) 或 O(n)，具体取决于您的内存管理方案）并重建树（O(k' log k')）操作。总复杂度为 O(k')+O(k' log k') = O(k' log k')，当 k' < 时，显然小于 O(k log n)。 k（您保留了树的不到 50%）。

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

Answer 3

从红黑树中批量删除是很困难的，因为黑色高度不变量会变得非常混乱。假设你没有做（软）实时，我要么一一删除（因为你必须一一插入它们，我们在这里讨论一个较小的常数因子）或切换到展开树。