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

Question

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

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

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

Answer 1

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

如果你只删除了一些元素，那么最好只是逐个删除它们，最后以O（k log n）操作（k =删除的元素，n =移除之前树中的元素）结束。但是如果你知道你要移除大量的节点（例如50％或更多的树），那么最好迭代你想要保留的元素（O（k'））操作，其中k'=将保留的元素），然后根据内存管理方案废弃树（O（1）或O（n））并重建树（O（k'log k'））操作。当k'< k（保持小于50）时，总复杂度为O（k'）+ O（k'log k'）= O（k'log k'），显然小于O树的％）。

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

Answer 2

从红黑树上批量删除很难，因为黑高不变变得非常糟糕。假设你没有实时（软），我要么一个接一个地删除（因为你必须逐个插入它们，我们在这里讨论一个较小的常量因子），或者切换到一个splay树。

Answer 3

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

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

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

拆分：给定的值k和红黑树T，t分裂成两个红黑树T1和T2，使得在T1 < K的T2的所有数值和所有数值> = K。

加入：组合两个红黑树T1和T2到单个红黑树T. T1和T2满足Max在T1在T2（或T1 <在短= T2）< =分钟。

你需要的是两个Splits和一个Join。

对于您的情况，您需要删除的子树将对应于值范围L <= v <= U。

所以你首先在L上输入Split，得到T1和T2，T1为< = T2。 Split T2在U上得到T3和T4与T3 < = T4。现在Join树T1和T4。

伪代码，你的代码将是这个样子：https://cstheory.stackexchange.com/questions/1045/subrange-of-a-red-and-black-tree

：

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; 
} 

有关更多信息，请参见本