实践中哪个更快：Treap 还是 Splay 树？
What is faster in practice: Treap or Splay tree?
我学习了 Treap 和 Splay tree 并使用它们解决了一些问题.
理论上，它们的平均复杂度是 O(log n)，但在最坏情况下 Treap 的 复杂度是 O(n ) 而 Splay 树的 是 摊销 O(log n)。
最坏的情况发生在 Treap 中（因为它的优先级是随机选择的），并且 Treap 真的比 展开树？我已经使用 Splay tree 和 Treap 解决了 SPOJ 上的一些任务，使用 Treap 的解决方案是比使用 Splay tree 快一点（大约 0.2s）。那么哪个实际上更快，我应该主要使用哪个以及什么时候使用？
实际上，两者都没有真正使用过。 They are often way more complex than necessary. 它们在学术上和编程竞赛中都很有趣。我在生产代码中真的只运行接触过红黑树和B树，其他类型的平衡树非常少见。
如果你发现 treaps 更快，那么就使用它们，因为 O(n) 最坏情况下的时间性能是由于运气不好，而不是对抗性输入。 Splay 树稍微慢一些，因为在实践中你必须 "pay" 进行摊销才能将最坏情况降低到 O(log n)。
我学习了 Treap 和 Splay tree 并使用它们解决了一些问题.
理论上，它们的平均复杂度是 O(log n)，但在最坏情况下 Treap 的 复杂度是 O(n ) 而 Splay 树的 是 摊销 O(log n)。
最坏的情况发生在 Treap 中（因为它的优先级是随机选择的），并且 Treap 真的比 展开树？我已经使用 Splay tree 和 Treap 解决了 SPOJ 上的一些任务，使用 Treap 的解决方案是比使用 Splay tree 快一点（大约 0.2s）。那么哪个实际上更快，我应该主要使用哪个以及什么时候使用？
实际上，两者都没有真正使用过。 They are often way more complex than necessary. 它们在学术上和编程竞赛中都很有趣。我在生产代码中真的只运行接触过红黑树和B树，其他类型的平衡树非常少见。
如果你发现 treaps 更快，那么就使用它们，因为 O(n) 最坏情况下的时间性能是由于运气不好，而不是对抗性输入。 Splay 树稍微慢一些，因为在实践中你必须 "pay" 进行摊销才能将最坏情况降低到 O(log n)。