红黑树：Split/Concatenate log(n) 时间
Red-Black tree: Split/Concatenate in log(n) time
根据 Ron Wein 的说法，您可以在 O(log(n)) 时间内完成红黑树的拆分和连接。查看他的文章：Efficient Implementation of Red-Black Trees with Split and Catenate Operations
不过我还是不相信分裂的运行时间是真的。
想法是拆分使用最坏情况的 log(n) 连接。这些连接的完成速度很快，因为我们可以通过记住上次连接中的 p 找到节点 p。
问题是串联会启动修复（平衡）算法，据我所知，该算法需要 O(log n)（参见串联伪代码中的步骤 5）。
这给了我 log(n)*log(n) 的 运行 时间，因为拆分会产生最坏情况的 log(n) 级联。
Ron Wein，在他的论证中没有考虑修复算法。我在分析中遗漏了什么，还是算法有误？
将来。如果有任何人再次遇到同样的问题：
与 Ron Wein 相比，Tarjan 在算法上有一些重要差异。我仍然无法看出 Wein 在他的算法中是正确的，但 Tarjan 是。所以我建议你改用他的。
第一个要点是平衡算法的成本为 O(log(d))，其中 d 是您开始平衡的深度。
然后，Tarjan 的算法的不同之处在于从拆分密钥开始并沿着通往根的路径移动。通过这样做，您将看到您连接的子树具有大致相同的深度。因此 "d" 总是很小的。因此可以更快地完成。
第二件事是 Tarjan 建议对所有节点进行扩充，以便它们知道它们的等级（其子树的黑色深度 + 它自身）。通过这样做，我们能够在 O(1) 时间内知道哪棵树最大。
也可以在 O(1) 时间内找到高度的差异。
我建议大家阅读 Tarjans 的论文而不是 Wein 的
根据 Ron Wein 的说法，您可以在 O(log(n)) 时间内完成红黑树的拆分和连接。查看他的文章：Efficient Implementation of Red-Black Trees with Split and Catenate Operations
不过我还是不相信分裂的运行时间是真的。
想法是拆分使用最坏情况的 log(n) 连接。这些连接的完成速度很快，因为我们可以通过记住上次连接中的 p 找到节点 p。
问题是串联会启动修复（平衡）算法，据我所知，该算法需要 O(log n)（参见串联伪代码中的步骤 5）。 这给了我 log(n)*log(n) 的 运行 时间，因为拆分会产生最坏情况的 log(n) 级联。
Ron Wein，在他的论证中没有考虑修复算法。我在分析中遗漏了什么，还是算法有误？
将来。如果有任何人再次遇到同样的问题： 与 Ron Wein 相比，Tarjan 在算法上有一些重要差异。我仍然无法看出 Wein 在他的算法中是正确的，但 Tarjan 是。所以我建议你改用他的。
第一个要点是平衡算法的成本为 O(log(d))，其中 d 是您开始平衡的深度。 然后，Tarjan 的算法的不同之处在于从拆分密钥开始并沿着通往根的路径移动。通过这样做，您将看到您连接的子树具有大致相同的深度。因此 "d" 总是很小的。因此可以更快地完成。
第二件事是 Tarjan 建议对所有节点进行扩充，以便它们知道它们的等级（其子树的黑色深度 + 它自身）。通过这样做，我们能够在 O(1) 时间内知道哪棵树最大。 也可以在 O(1) 时间内找到高度的差异。
我建议大家阅读 Tarjans 的论文而不是 Wein 的