DanAlex's blog

Treaps
By DanAlex, 11 years ago, In English

Hello everybody ! This is my first entry. I want to share with you my knowledge about treaps and to ask if you know any problems that use this data structure.

The treap is a combination between a heap and a BST. So , you have two values asociated with every node — the key and the priority.

The main properties are: 1. if you traverse it in inorder , your keys will be sorted 2. priority of every node is greater than the ones of the sons

Operations

Search: like in an usual BST.

Rotations: the idea behind the rotations is to keep the heap property , so if you want to swap w and z this goes like that


      z            w
     / \          / \
    w   c   <=>  a   z
   / \              / \
  a   b            b   c

Insertion: you go to the right place and insert the new node as a leaf and then when you return you balance the tree ( that means you make roations to keep the heap property )

Deletion: you search for the specified key and move it downwards ( in left or in right — you have to keep the heap property ) ; when the node becomes a leaf you delete it

Split: you can split the treap in two treaps ( one with the keys smaller than the wanted value and one with the key bigger than the wanted value ) ; you will insert a new node with priority = infinity and key = value ; your new treaps will be the left and the right sons

Join: you can join two treaps in one new treap ; you can do this by inserting a new node having the sons the two treaps and than you will delete the inserted node

Usefulness

You can keep dynamic arrays with a treap as you can search the k-th value in an array at any time in O(log n). All the operation stated before are made in O(log n) ( except rotations which are made in O(1) ).

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

Comments Comments (18)
| Write comment?
»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

What you name join really is merge, and it works only with treaps such that all values in the second treap is >= than all values in the first one.

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

You are right , one treap's values have to be smaller than the other one's.

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

http://www.spoj.com/problems/TREAP/

This problem is pretty good and simple to first implement treap.

http://www.codechef.com/JAN12/problems/CARDSHUF/

Treap could be used in this problem according to what writes in its explanation, but I didnt examine the problem. May be helpful.

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

What do you need rotation for? It's rather complex comparing to merge/split, and these two operations are enough for all another operations:

  1. Insert — split plus two merges
  2. Erase — two splits plus merge

And so on.

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

    true. + with merge and split implementation you change 8 lines or something and you get a fast O(log n) array.

    Treap is Scarlett Johansson of algorithms, short but beautiful.

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

    I am not sure if the complexity holds if you do that. I use the rotations to keep the tree balanced ( that means it keeps the heap property ). When you insert a new node , usually its priority will be a random number.

    If it works give me your code , please.

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

      Complexity holds as long as the priorities are random. There are only one treap for each set of pairs (value, priority), so if your merge and split are correct, there is nothing to worry about.

      Here is some code, which supports split, merge, insert, erase and dynamically calculates size of each sub-treap (it can be useful if you want to get k-th element in ).

      UPD: by the way, as priorities are used in merge only, we can get rid of them: just assume that l->x < r->x with probability l->cnt / (l->cnt + r->cnt) (i.e. the larger treap is, with the larger probability its root will become our new root). It's enough for keeping the treap balanced, too.

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

        lol i never thought about that. In my opinion that's even cooler than with priorities, since the treap is not defined solely by the set of pairs (value, priority), instead it's a bit more clear how it balances. If i'm not mistaken, you have the exact complexity if you change this part (but since we take into account the size of treap and therefore have a weighted probability, it's probably a bit faster than the implementation with priorities), however the pairs don't represent a unique treap anymore.

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

          It may be cooler, but it's slow, because taking one random number from range is one call to rand() (or similar) and one module, which is not faster than one comparison of ints. However, it's still very useful if you are unable to use priorities (say, in persistent treap).

          Yes, complexity remains the same and you don't have paris at all anymore, so it's strange to talk about 'pairs do not represent a unique treap'.

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

        Super cool ! :D My implementation is much larger ( http://goo.gl/5zyqG1 ) and you are right. Thanks a lot !

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

      There are a more "common" way to implement treaps (honestly, I've never seen rotating in treaps yet) that uses only two basic operations: 1. Merge:

      void merge (pitem & t, pitem l, pitem r) {
	if (!l || !r)
		t = l ? l : r;
	else if (l->prior > r->prior)
		merge (l->r, l->r, r),  t = l;
	else
		merge (r->l, l, r->l),  t = r;
}
      1. Split:
      void split (pitem t, int key, pitem & l, pitem & r) {
	if (!t)
		l = r = NULL;
	else if (key < t->key)
		split (t->l, key, l, t->l),  r = t;
	else
		split (t->r, key, t->r, r),  l = t;
}

      (Code examples above are copied from this page, that is in Russian, but contains a good "start guide" for treaps)

      All other operations with a tree can be done using merge and split (though, sometimes it's a bit faster to implement them in more "smart" variant, for example, to delete a value we can just overplace it with it's merged children).

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

        Can anyone illustrate me how the above split function works exactly ?

        Split into 2 Treap : Treap L (all values <= key) , Treap R (all values > key)

        I understood that at node U (child $$$Ul$$$, $$$Ur$$$):

        if (key < t -> key).

        • $$$U$$$ and $$$Ur$$$ and all of its descendants will be in Treap R.

        • Then call the split function for $$$Ul$$$ and attach the root of R’ returned by split as left child of $$$U$$$ (in Treap R).

        else if (key >= t -> key) : do nearly the samething.

        But I don't get how they attach the root of Treap R' returned by the split of $$$Ul$$$ as the left child of $$$U$$$ (in Treap R) by set $$$r = t$$$ after the split ?:

        Like this ? :split (t-> l, key, l, t-> l), r = t;

        Thanks in advanced <3.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          1. The code as I wrote it puts values equal to the key to the "right" result.
          2. The split function mutates its arguments by reference (kinda ugly, but this code, I believe, was written with other ideas in mind, like length, etc.), so it can be read as "take this treap U and set other 2 pointers to L(U) and R(U) treaps" (with notion of p.1 above). So the first if-case splits the Ul into he required 2 parts L(Ul) and R(Ur), then we note that L(Ul) is actually our L(U), so we use the "argument" pointer for the later directly, and R(U) is just like U, but with Ul replaced by R(Ul) -- all still in case of key < t->key ! As by definition L(Ul) and L(Ur) don't intersect, after the split call we can treat them separately.

          It's not clear to me what confused you, as you explained the code pretty well by youself, so I've writen the wordly explanation above, when the answer is actually "it sets it by the reference".

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

            I got that :D. Thanks so much <3

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

I am trying to implement treap with updating an interval (adding some constant to all elements in interval) and finding the sum on interval. Here is my code: http://pastebin.com/GV4U2fUn But it doesn't update properly. Could you please find a mistake?

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

    You can use segment tree instead of treap(Sorry I can't connect to pastebin)

    Usually on interval update problems segment tree and splay can do better.

    → Reply