algorithm - 平衡绳的串联复杂度是多少？

Question

我看过不同的论文，这里是我收集的信息:

• SGI implementation和 C cords既不保证长绳索的 O(1) 时间串联，也不保证短绳索的 ~log N 深度。
• 不同的来源相互矛盾。 Wikipedia要求 O(1) 级联。 This page表示仅当一个操作数较小时，串联才为 O(1)，否则为 O(log N)。

那么，串联的时间复杂度是多少？何时执行准确的重新平衡以确保这种级联复杂性同时保持树平衡？在谈论这种复杂性时是否假设了一些特定的使用模式？

Answer 1

维基百科文章不清楚，论文"Ropes: an Alternative to Strings"它没有引用任何地方，声称如此​​复杂的结果。

另一方面，最近的这篇论文(Gerth Stølting Brodal、Christos Makris 和 Kostas Tsichlas)确实:"Purely Functional Worst Case Constant Time Catenable Sorted Lists" .他们也有 O(logn) 搜索，因此您确实可以将其标记为“平衡”，不过我还没有阅读详细信息，只是阅读了结果。

“绳索”是一个在实践中(相对)常见但在研究中并不常见的术语。相反，我搜索了 catenable queues(或列表)，尤其是 Tarjan、Okasaki、Kaplan 等人所做的研究，我认为这才是您真正的答案。