红-黑树:在日志(N)时间内分割/串联

Question

根据罗恩·韦恩的说法，你可以在O(log(n))时间内分割和连接红黑树。见他的作品：红黑树分割与连锁运算的高效实现

然而，我仍然不相信分割的运行时间真的是真的。

其思想是，split使用最坏情况的日志(N)连接。这些连接是快速完成的，因为我们可以从最后的级联中通过记住p来找到节点p。

问题是，级联启动了修复(平衡)算法，据我所知，该算法采用O(log )(参见伪代码中的级联步骤5)。这给我一个log(n)*log(n)的运行时间，因为拆分将导致最坏情况的log(n)连接。

罗恩·韦恩( Ron )在他的论证中没有考虑到修正算法。我在分析中遗漏了什么，或者算法是错误的？

Answer 1

在未来。如果有同样的问题的话:与Ron相比，Tarjan在算法上有一些重要的区别。我仍然没有看到Wein在他的algoritm中是正确的，但是Tarjan是正确的。所以我建议你用他的代替。

首先，平衡算法的代价是O(log(d))，其中d是开始平衡的深度。然后，Tarjan的算法不同，从拆分键开始，然后移动到根的路径上。通过这样做，您将看到您连接的子树具有大致相同的深度。因此，"d“永远是小的。因此，它可以做得更快。

第二件事是，Tarjan建议所有节点都进行扩展，以便它们知道它们的级别(其subtrees+it自我的黑色深度)。通过这样做，我们能够知道哪棵树在O(1)时间内是最大的。也有可能在O(1)时间内找到那里高度的差异。

我建议大家读读塔里木的报纸，而不是韦恩的