我已经学会了treap和splay tree，并且用它们解决了一些问题。
理论上，它们的复杂度一般是O（log n），但在最坏情况下，其复杂度是O（n），而分支树是O（log n）的摊销。
在哪种情况下，Treap会出现最坏的情况（因为它的优先级是随机选择的），Treap真的比Splay tree慢吗我已经用Splay tree和Treap解决了SPOJ上的一些任务，使用Treap的解决方案比使用Splay tree的解决方案快一点（大约0.2秒）那么哪一个实际上更快，我应该主要用哪一个，什么时候用？
最佳答案
在实践中，两者都没有被真正使用。They are often way more complex than necessary.它们在学术上和编程比赛中都很有趣。我在生产代码中只遇到过红黑树和B树，其他类型的平衡树非常罕见。
如果您发现treaps更快，那么就使用它们，因为o（n）最坏情况下的性能是由于运气不好，而不是对手的输入。Splay树稍微慢一点，因为在实践中，您必须“支付”分期付款，才能将最坏的情况降到O（log n）。