我查看了不同的论文，以下是我收集的信息：
- SGI 实现和C 绳既不能保证长绳索的 O(1) 时间连接，也不能保证较短绳索的 ~log N 深度。
- 不同的来源相互矛盾。维基百科声称 O(1) 级联。该页面说，仅当一个操作数较小时，连接才为 O(1)，否则为 O(log N)。
那么，串联的时间复杂度是多少？何时执行重新平衡以确保这种连接复杂性同时保持树平衡？在谈论这种复杂性时，是否假设了一些特定的使用模式？
问问题
1193 次
1 回答
3
维基百科的文章不清楚，它在任何地方都没有引用的论文“绳索：字符串的替代品”声称如此复杂的结果。
另一方面，这篇最近的论文（由 Gerth Stølting Brodal、Christos Makris 和 Kostas Tsichlas 撰写）确实：“Purely Functional Worst Case Constant Time Cateable Sorted Lists”。他们也有 O(logn) 搜索，所以你确实可以将它标记为“平衡”，但我还没有阅读详细信息，只是结果。
“绳索”是一个在实践中（相对）常见的术语，但在研究中并不常见。相反，我搜索catenable queues（或列出），尤其是 Tarjan、Okasaki、Kaplan 等人所做的研究，我认为这才是你真正的答案所在。
于 2010-10-13T16:20:33.520 回答