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

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'))操作.总复杂度为O(k')+ O(k'log k')= O(k'log k'),当k'<k(你保持小于50)时,它明显小于O(k log n)树的百分比).

好吧,关键是当你要删除大部分元素时,最好在实践中枚举你想要保留的元素然后重建树.

Answer 2

编辑:以下是通用子树删除.你需要的只是一个Split操作(根据你的实际问题内容).

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

据了解,Split和Join上一个红黑树操作可以在完成O(log n)时间.

分割:给定值k和红黑树T,将T分成两个红黑树T1和T2,使得T1 <k中的所有值和T2中的所有值> = k.

加入:将两个红黑树T1和T2组合成一个红黑树T.T1和T2在T2 <= min(或T1 <= T2)中满足最大值T1 <= min.

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

在您的情况下,您需要删除的子树将对应于一系列值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