Блог пользователя svg_af

Автор svg_af, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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 :)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 ?

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      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 :)

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        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 ?

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 :)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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