algorithm - 在实践中哪个更快：Treap 或 Splay 树？

Question

我已经学习了Treap和Splay 树，并使用它们解决了一些问题。
理论上，它们的平均复杂度为O(log n)，但在最坏的情况下，Treap 的复杂度为O(n)，而Splay 树的平均复杂度为 O (log n)。

Treap在哪种情况下会出现最坏的情况（因为它的优先级是随机选择的），并且Treap真的比Splay 树慢吗？我已经使用 Splay tree和Treap解决了 SPOJ 上的一些任务，使用Treap的解决方案比使用 Splay tree的解决方案要快一些（大约0.2s）。那么哪个实际上更快，我应该主要使用哪个以及何时使用？

Answer 1

在实践中，两者都没有真正使用。它们通常比必要的复杂得多。它们在学术和编程竞赛中大多很有趣。我真的只在生产代码中遇到过红黑树和 B 树，其他类型的平衡树极为罕见。

如果您发现陷阱更快，那么只需使用它们，因为 O(n) 最坏情况下的时间性能是由于运气不好，而不是对抗性输入。展开树稍微慢一些，因为您必须在实践中“支付”摊销费用才能将最坏的情况降低到 O(log n)。