红黑树:以log(n)时间分割/连接 [英] Red-Black tree: Split/Concatenate in log(n) time

问题描述

根据罗恩·温(Ron Wein)，您能够在O(log(n))时间内对红黑树进行拆分和串联.请参阅他的文章:有效实施红黑树具有拆分和分类操作

According to Ron Wein your able to do split and concatenation of red-black tree's in O(log(n)) time. See his artikle: Efficient Implementation of Red-Black Trees with Split and Catenate Operations

但是我仍然不相信split的运行时间确实是正确的.

However I'm still not convinced that the running time of split really is true.

这个想法是split使用最坏情况的log(n)串联.这些连接的速度很快，因为我们可以通过记住上一个连接的p来找到p的节点.

The idea is that split uses worst-case log(n) concatenatations. These concat's is done fast as we can find the node, p, by remembering the p, from last concatenate.

问题在于，级联会启动修正(平衡)算法，据我所知，该算法需要O(log n)(请参见伪代码中的第5步进行级联).这给了我log(n)* log(n)的运行时间，因为拆分会产生最坏情况的log(n)串联.

The problem is that concatenation starts the fix-up (balancing) algorithm, which as far as I know takes O(log n) (see step 5 in the pseudo-code for concatenation). This gives me a running time of log(n)*log(n), as split will make worst-case log(n) concatenations.

罗恩·温恩(Ron Wein)在他的论点中没有考虑修正算法.我在分析中错过了什么，或者算法错误?

Ron Wein, does not take the fix-up algorithm into count in his argumentation. What have i missed in my analysis, or is the algorithm wrong?

推荐答案

将来.如果有任何同样的问题:与Ron Wein相比，Tarjan在算法上有一些重要差异.我仍然无法看到Wein在他的算法中是正确的，但是Tarjan是正确的.所以我建议您改用他.

In future. If any have the same problem again: Tarjan have some important differences in the algorithm compared to what Ron Wein does. I still haven't been able to see that Wein is correct in his algoritm, but Tarjan is. So I suggest you use his instead.

第一个要点是，平衡算法的成本为O(log(d))，其中d是开始进行封口的深度.然后，Tarjan的算法有所不同，从分割键开始，然后移动到根目录.这样，您将看到所连接的子树的深度大致相同.因此，"d"将始终很小.因此可以更快地完成它.

First important point is that the balancing algorithm cost O(log(d)) where d is the depth for which you start the balacing from. Tarjan's algorithm then differs by starting at the split-key and moving on the path to root. By do this, you will see that the the subtree's you concatenate have about same depth. Thus will "d" always be small. Thus it is can be done much faster.

第二件事是，Tarjan建议对所有节点进行扩充，使其知道其等级(其子树的黑色深度+它的自身).通过这样做，我们可以知道哪棵树在O(1)时间中最大.还可以找到O(1)时间中该高度的差异.

A second thing is that Tarjan suggest that all nodes is augmented such that they know their rank (black depth of its subtrees+it self). By doing this, we are able to know which tree is biggest in O(1) time. It is also possible to find the difference in there height in O(1) time.

我建议所有人都阅读Tarjans论文，而不是Wein的

I suggest all to read Tarjans paper instead of Wein's

这篇关于红黑树:以log(n)时间分割/连接的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！