ppavic's blog

Treap vs Splay
By ppavic, history, 6 years ago, In English

I couldn't find any good answers so I am posting here.

Currently, I know the splay tree data structure and I am thinking about learning treap. How useful is it to know Treap when you already know the splay tree data structure?

I am especially interested in finding an answer to these 4 questions:

Which do you find easier to code?

Are there any problems treap can solve and splay can't and vice versa?

Which is usually faster in practice?

And finally are there any other BBST you use except for the most popular splay tree and treap?

  • Vote: I like it
  • +15
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

Treaps are way easier to code.

Treaps can be easily made persistent while Splay trees usually use a parent pointer. So yeah, sometimes you'll need persistent treaps to replace dynamic segment trees (if you don't do coordinates compression). You can use such treap as a persistent vector with logarithmic time for deletion/insertion/query

Splay trees are conjectured to have dynamic optimality, meaning that they are, perhaps, fastest BS Trees for some random data. (You can build statically optimal BST with dyn. programming). Well, treaps are usually regarded as slow BS Trees (generating random) that use comparatively low memory.

I personally like Treaps very much for being easy to code and flexibility (you can use it instead of segment trees in many problems if you prefer)

→ Reply
»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I think treap is more easier to code than splay.

But however if you want to maintain a LCT using splay, it's O(nlogn) instead of O(nlog^2n)(using treap),

→ Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Treap: dynamic array — you can cut/paste any subarray — with pretty much arbitrary range functionality. I have an implementation that works as a sorted array (indexed set) with insert by value, delete by value, range sum, (possibly breaking sortedness) insert at position, add to range, reverse range, (if sorted) lower_bound supported all together. Sum can be replaced by any similar function.

I don't know much about splay trees.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it -10 Vote: I do not like it

    You can achieve the same with a splay tree as well. It is called an implicit key Treap/Splay tree and the one using Splay Tree will most certainly be faster (dynamic optimality conjecture). It is hard to code properly though. But the array cannot be made persistent trivially in case of a Splay tree.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Treap bases on zig-zag is faster than splay(except for merge), while it can not do interval operation.

→ Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Be ANIMAL, use splay :)

→ Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

treap

→ Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

For the second question, the ability to be made persistent is an important feature of Treaps, as is mentioned in the very first comment. Splay trees can't manage e.g. 'duplicate a subsegment after itself' or 'copy a subsegment and fill it into another' operations on a sequence in logarithmic time.

For the fourth question, I believe red-black trees (aka std::set's or std::map's) are the most popular :P

→ Reply