平衡绳的串联复杂度是多少？
我查看了不同的论文，以下是我收集的信息：
- SGI 实现< /a> 和 C 线< /a> 既不能保证长绳索的 O(1) 时间串联，也不能保证短绳索的 ~logN 深度。
- 不同的来源相互矛盾。 Wikipedia 声称 O(1) 级联。 此页面表示仅当一个操作数为 O(1) 时，串联才是 O(1)小，否则为 O(log N)。
那么，串联的时间复杂度是多少呢？何时执行重新平衡以确保这种串联复杂性，同时保持树平衡？在谈论这种复杂性时是否假设了一些特定的使用模式？
I've looked at different papers and here is the information that I've gathered:
- SGI implementation and C cords neither guarantee O(1) time concatenation for long ropes nor ~log N depth for shorter ones.
- Different sources contradict each other. Wikipedia claims O(1) concatenation. This page says that concatenation is O(1) only when one operand is small and O(log N) otherwise.
So, what is the time complexity of concatenation? When exactly rebalancing is performed to ensure this concatenation complexity while maintaining tree balance? Are some specific usage patterns assumed when talking about this complexity?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
维基百科文章不清楚，论文 “绳子：弦的替代品”它没有引用任何地方，声称这样的复杂性结果。
另一方面，最近的这篇论文（作者：Gerth Stølting Brodal、Christos Makris 和 Kostas Tsichlas）确实：“纯函数式最坏情况常数时间可连接排序列表”。他们还有 O(logn) 搜索，所以实际上你可以将其标记为“平衡”，但我还没有阅读详细信息，只是阅读结果。
“绳索”是一个在实践中（相对）常见的术语，但在研究中并不常见。相反，我搜索了可连接队列（或列表），特别是 Tarjan、Okasaki、Kaplan 等人所做的研究，我认为这就是您真正的答案。
The wikipedia article is unclear, the paper "Ropes: an Alternative to Strings" that it cites nowhere, claims such a complexity result.
On the other hand, this recent paper (by Gerth Stølting Brodal, Christos Makris and Kostas Tsichlas) does: "Purely Functional Worst Case Constant Time Catenable Sorted Lists". They also have O(logn) search, so indeed you can tag it "balanced", I haven't read the details though, just the results.
"Rope" is a term that is (relatively) common in practice, but not in research. Instead, I searched for
catenable queues(or lists), especially research done by people as Tarjan, Okasaki, Kaplan and others, I think that's where your real answer is.