svg_af's blog

Are treaps slow ?
By svg_af, history, 9 years ago, In English

Hello there

so I'm trying to solve this problem

It's about finding the gcd of a set of numbers where i insert and delete numbers from the set

I already solved it with a segment tree, and after learning about treas i tried solving it with a treap but it TLEd on testcase 18

now my question is: aren't treaps on average Log(n)? if so ... shouldn't it pass where segment tree did with complexity of stable Log(n)?

here's my treap code for reference for maybe the error is in my implementation

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

»
9 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Treaps are solwer than segment trees. If you are able sving a problem using a segment tree there is no point in writing a treap. So in fact treaps are slower, because the operations are with complexity c*depth where c is the number of times you call merge/split. Another thing you should consider is that the depth of the treap is bigger than the depth of the segment tree, because it's not a perfectly balanced binary tree. So the complexity of the segment tree is lesser than the treap's complexity. But this is just a comparison between the two data structures's complexities. The pros of the treap are that you are able of doing much more operations using just merge and split (like Cyclic shift, reverse and etc).

So in short:

if you are able using a segment tree — use segment tree.

Else use (implicit) treap/avl.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    roger that ... another question ... AVL trees ... they are stable Log(n) in height

    are rotation operations costly ... i mean are they as slow as treaps ?

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

      I do not really like solving problems with AVL, because its just a lot harder to implement than treap. And for the complexity it may be a little faster, but still its harder to implement.

      → Reply