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

| 我目前正在实现红黑树数据结构，以对应用程序执行一些优化。在我的应用程序中，在给定的点上，我需要从树中删除所有小于或等于给定值（可以假定这些元素是整数）的元素。我可以一一删除元素，但我想更快些。因此，我的问题是：如果删除一棵红黑树的整个子树，如何修复该树以恢复高度和颜色不变性？

已邀请:

3 个回复

久坡

当您从红黑树中删除一个元素时，将花费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 \'

涸坍饺

编辑：以下是针对通用子树的删除。您只需要执行一次“ 0”操作（根据您实际的问题内容）。在最坏的情况下（ѭ1to），可以删除红黑树的整个子树。众所周知，可以在tree1ѭ时间内完成对红黑树的Split和Join操作。拆分：给定值k和红黑树T，将T拆分为两个红黑树T1和T2，以使T1中的所有值 = k。连接：将两个红黑树T1和T2合并为一个红黑树T。T1和T2满足T1中的max <= T2中的min（或简称T1 <= T2）。您需要的是两个Splits和一个Join。在您的情况下，您需要删除的子树将对应于值L <= v <= U的范围。因此，您首先在L上ѭ0，以得到T1和T2，且T1 <= T2。在U上SplitT2以获得T3和T4，且T3 <= T4。现在“ 3”树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

捐焦

很难从红黑树中进行批量删除，因为黑高不变式非常糟糕。假设您不是实时（软），我要么一个接一个地删除（因为您必须一个接一个地插入它们，所以我们在这里讨论的是一个较小的常数），或者切换到一个八叉树。

要回复问题请先登录或注册

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

3 个回复

发起人

binary_tree

algorithm

data_structures

red_black_tree

问题状态

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

与内容相关的链接

3 个回复

发起人

binary_tree

algorithm

data_structures

red_black_tree

问题状态