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

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

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

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

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

原文

分享到QQ

分享到微博

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

发布评论

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

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

编辑：以下是通用子树删除。您需要的只是一个 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

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

回复收藏 0 原文

那请放手 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%）。

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

回复收藏 0 原文