2

I've learned both Treap and Splay tree and solved few problems using them.
In theory, their complexity is O(log n) on average, but in worst-case Treap's complexity is O(n) while Splay tree's is amortized O(log n).

In which case does worst case occur in Treap (since its priorities are randomly chosen), and is Treap really slower than Splay tree? I've solved some tasks on SPOJ with both Splay tree and Treap, and solutions using Treap were a bit faster (around 0.2s) than ones using Splay tree. So which one is actually faster, and which one should I mainly use and when?

NikolaTECH
  • 76
  • 10

1 Answers1

2

In practice, neither are really used. They are often way more complex than necessary. They're mostly interesting academically and for programming contests. I've really only run into red-black trees and B-trees in production code, other types of balanced trees are extremely rare.

If you're finding that treaps are faster, then just use them, as the O(n) worst case time performance is due to bad luck, not adversarial input. Splay trees are slightly slower because you have to "pay" for the amortization in practice to get the worst case down to O(log n).

kevmo314
  • 4,223
  • 4
  • 32
  • 43
  • 1
    I'm not sure that I buy the complexity argument. As I recall handling the red-black tree cases made my brain hurt while splay trees were a breeze in comparison. They are certainly harder to use as you lose the predictable performance and need to evaluate whether your application can bear the amortization hit (though in practice I'll admit that I've been known to use vectors and the like without giving this much though.) – doynax Jan 07 '18 at 06:53
  • I'll admit that I've only seen red-black trees in `std::map`, and apparently the choice to use them over hash maps is more for historical consistency: https://stackoverflow.com/questions/5288320/why-is-stdmap-implemented-as-a-red-black-tree I agree in practice balanced trees aren't as useful due to the additional complexity they need. I also just use vectors. – kevmo314 Jan 07 '18 at 13:43
  • 2
    In my experience (both in practice and in ACM-style contests) treaps are much easier to code (and remember) than RB trees. The actual code is also simpler and faster unless your RNG sucks (`rand` and MT19937, I’m looking at you). The only reason to prefer RB trees over treaps I can think of is fear of randomized algorithms... Which could make sense, if you remember how `std::sort` works (quicksort, until it detects things are getting too slow because it got an adversarial input). – Alex Shpilkin Jul 13 '18 at 05:41