svg_af's blog

Help with treaps

By svg_af, history, 9 years ago, In English

Hello there

I'm trying to learn treaps and I've been stuck for a while trying to figure out how merge and split functions work

and I've read somewhere that reverse operations on arrays can be done using treaps

any help explaining these topics would be appreciated :D

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

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

GlebsHP gave a lecture on this two weeks ago, and you can watch it here.

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

I have written an article explaining treaps and their applications. Here are the links to Part-1 and Part-2 of the article. Part-1 explains the basic construction of the data structure and its use as Balanced BST's. Part-2 explains implicit treaps and its use as a Dynamic Interval Tree.
Hope that helps :)

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

    the implementation in your blog was perfect thank you

    one question comes to mind now ... generating random numbers without collisions ... is it possible ?

    if so what is the method used ?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      Look, this is my treap implementation — http://ideone.com/8DUWwZ. It's a bit different since it uses rotations instead of merge/split but the generation is the same. I use the structure called xorshift for that, it's a pseudo number generator, you can google it. It produces the same sequence of values every time so you can check if the numbers you choose for x,y,z,w give a collision in the first 10^6 numbers generated and if they don't, you are safe. Actually I haven't seen a case when it produces a collision so if you randomly enter some integers for x,y,z,w, it will most likely give no collision :)

      PS: Of course you can simply put all numbers from 1 to 10^6 in a vector, then random shuffle it and always take the last element but random shuffle uses modulo operations and mine doesn't so I will keep using it :)

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

        your xorshift struct is very fast, easy to implement, and with 0 collisions up to 10^7 ... which is how much i was willing to wait for :p

        thank you very much ...

        question if you may ... handling repeating elements insertion in a treap using the merge/split method where i have repeating elements ... is there a way to have one node for an element and keep a frequency variable in each node ... besides the obvious way of course where i look for it first with a find method ?

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

          I think it can be done by adding a counter in each node and if the key is in the treap just increase it :) Actually I have used the normal treap as MULTIset assuming that left subtree contains nodes with key less than the current and right subtree contains nodes with key greater than or equal to the current. Insert, erase and find worked correctly but not kth and count_less, maybe I had some bug :)

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

plus another question regarding BSTs in general ... what is the best way to handle duplicates ?

in AVL trees i used to put the frequency in the node itself but i can't see how that's possible here

→ Reply