删除红黑树的整个子树会保留其属性吗?
我目前正在实现一个红黑树数据结构来对应用程序执行一些优化。
在我的应用程序中,在给定点,我需要从树中删除所有小于或等于给定值的元素(您可以假设元素是整数)。
我可以一一删除元素,但我想要更快的东西。因此,我的问题是:如果我删除红黑树的整个子树,如何修复该树以恢复高度和颜色不变量?
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 技术交流群。

绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(3)
编辑:以下是通用子树删除。您需要的只是一个
Split
操作(基于您的实际问题内容)。在最坏的情况下,有可能删除红黑树的整个子树
O(log n)
时间。众所周知,红黑树上的
Split
和Join
操作可以在O(log n)
时间内完成。您需要的是两个
Split
和一个Join
。在您的情况下,您需要删除的子树将对应于一系列值
L <= v <= U
。因此,您首先在 L 上进行
Split
,以获得 T1 和 T2,其中 T1 <= T2。在 U 上拆分
T2 得到 T3 和 T4,其中 T3 <= T4。现在加入
树T1和T4。在伪代码中,您的代码将如下所示:
有关更多信息,请参阅此: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
andJoin
operations on a red-black tree can be done inO(log n)
time.What you need is two
Splits
and oneJoin
.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. NowJoin
the trees T1 and T4.In pseudoCode, your code will look something like this:
See this for more information: https://cstheory.stackexchange.com/questions/1045/subrange-of-a-red-and-black-tree
当您从红黑树中删除一个元素时,需要 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.
从红黑树中批量删除是很困难的,因为黑色高度不变量会变得非常混乱。假设你没有做(软)实时,我要么一一删除(因为你必须一一插入它们,我们在这里讨论一个较小的常数因子)或切换到展开树。
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.