Treaps - Codeforces

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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

Комментарии (18)

Показать архивные | Написать комментарий?

Break-Neck

11 лет назад, # |

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.

→ Ответить

DanAlex

← Rev. 3 →

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

sbasrik

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.

tanvir_cse

8 лет назад, # ^ |

if i build a treap then it forget it's order and make bst . how could i keep trace index also.

http://www.spoj.com/problems/TREAP/ for this problem i can insert and delete but how could i keep trace the index and output the interval queries ?

Nafis.Shahriar

5 лет назад, # ^ |

You can keep count of sub-tree size and find out the index. You just need to find the ans from ith minimum number to jth minimum number.

This can be helpful- https://cp-algorithms.com/data_structures/treap.html

yeputons

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

Insert — split plus two merges
Erase — two splits plus merge

And so on.

k0re

11 лет назад, # ^ |

+14

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.

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.

← Rev. 2 →

+19

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 $\text{[math]}$ ).

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.

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.

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'.

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

+11

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;
}

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

_LNHTD_

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.

The code as I wrote it puts values equal to the key to the "right" result.
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".

I got that :D. Thanks so much <3

abzaloid

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?

hzyfr

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.

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

Operations

Usefulness