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

发布于 2024-11-01 17:14:03 字数 163 浏览 10 评论 0原文

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

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

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

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?

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

绾颜 2024-11-08 17:14:03

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

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

众所周知,红黑树上的SplitJoin操作可以在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

EDIT: The below is for a generic sub-tree delete. What you need is just a single Split operation (based on your actual question contents).

It is possible to delete a whole subtree of a Red-Black tree in worst case O(log n) time.

It is known that Split and Join operations on a red-black tree can be done in O(log n) time.

Split : Given a value k and a red-black Tree T, Split T into two red-black trees T1 and T2 such that all values in T1 < k and all values in T2 >= k.

Join : Combine two red-black trees T1 and T2 into a single red-black tree T. T1 and T2 satisfy max in T1 <= min in T2 (or T1 <= T2 in short).

What you need is two Splits and one Join.

In your case, the subtree you need to delete will correspond to a range of values L <= v <= U.

So you first Split on L, to get T1 and T2 with T1 <= T2. Split T2 on U to get T3 and T4 with T3 <= T4. Now Join the trees T1 and T4.

In pseudoCode, your code will look something like this:

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

See this for more information: https://cstheory.stackexchange.com/questions/1045/subrange-of-a-red-and-black-tree

那请放手 2024-11-08 17:14:03

当您从红黑树中删除一个元素时,需要 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%)。

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

When you delete one element from a red-black tree it takes O(log n) time, where n is the number of elements currently in the tree.

If you remove only few of the elements, then it's best just to remove them one by one, ending up with O(k log n) operations (k = removed elements, n = elements in the tree before removals).

But if you know that you are going to remove a large number of nodes (e.g. 50% or more of the tree), then it's better to iterate through the elements you want to keep (O(k') operation where k' = elements what will be kept), then scrap the tree (O(1) or O(n) depending on your memory management scheme) and rebuild the tree (O(k' log k')) operation. The total complexity is O(k')+O(k' log k') = O(k' log k'), which obviously is less than O(k log n) when k' < k (you keep less than 50% of the tree).

Well, the point being anyway that when you are going to remove MOST of the elements, it's better in practice to enumerate the ones you want to keep and then rebuild the tree.

弥枳 2024-11-08 17:14:03

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

Bulk deletion from a red-black tree is hard because the black-height invariant gets messed up pretty badly. Assuming you're not doing (soft) real-time, I would either delete one-by-one (since you had to insert them one by one, we're talking about a smaller constant factor here) or switch to a splay tree.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文