Stack Overflow
Stack Overflow

Questions tagged [treap]

A treap is a form of a binary search tree data structure that maintains a dynamic set of ordered keys and allows binary searches among the keys.

A treap (tree+heap) is a Cartesian tree in which each key is given a (randomly chosen) numeric priority. As with any binary search tree, the inorder traversal order of the nodes is the same as the sorted order of the keys.

The structure of the tree is determined by the requirement that it be heap-ordered: that is, the priority number for any non-leaf node must be greater than or equal to the priority of its children.

Thus, as with Cartesian trees more generally, the root node is the maximum-priority node, and its left and right subtrees are formed in the same manner from the subsequences of the sorted order to the left and right of that node.

Useful links

Related tags

30 questions
28
votes
6 answers

When to use a treap

Can anyone provide real examples of when is the best way to store your data is treap? I want to understand in which situations treap will be better than heaps and tree structures. If it's possible, please provide some examples from real…
user2281439
  • 673
  • 2
  • 11
  • 19
20
votes
8 answers

Why is insertion into my tree faster on sorted input than random input?

Now I've always heard binary search trees are faster to build from randomly selected data than ordered data, simply because ordered data requires explicit rebalancing to keep the tree height at a minimum. Recently I implemented an immutable treap, a…
Juliet
  • 80,494
  • 45
  • 196
  • 228
11
votes
4 answers

Treap with implicit keys

There's a data structure called treap: that's a randomized binary search tree, which is also a heap on randomly generated so-called "priorities". There's a variation of this structure, where keys are implicit, they aren't stored in the tree, but we…
Skiminok
  • 2,801
  • 1
  • 24
  • 29
6
votes
1 answer

Which data structure is most suitable to implement a Dictionary?

I have to write a Dictionary program as a semester project for an undergraduate course on Data Structures and Algorithms, and I am expected to find the most suitable solution (Data Structure) to the problem. I considered using either a hash table or…
Saif Khan
  • 309
  • 1
  • 2
  • 19
6
votes
3 answers

When is a treap useful?

In what kind of situation is a treap the optimal data structure to use? I have been searching for answers on this but haven't really found anything concrete. There's another stackoverflow question asking when to use a treap but no real world…
Just some guy
  • 1,909
  • 4
  • 21
  • 32
3
votes
1 answer

How does a treap help to update this ordered queue?

I'm having trouble understanding this solution to a problem on HackerRank. Please see the solution code below, apparently by Kimiyuki Onaka. The problem is: given a list of unique numbers, and m queries of the type, "move the current ith to jth…
גלעד ברקן
  • 23,602
  • 3
  • 25
  • 61
2
votes
1 answer

Generating random priorities for a treap in C++

I am creating a treap, and I want to know, which random number generator is most suitable for generating priorities at insertion. The data set is about 6000 items long. I am modifying an existing template class(largely just declared methods without…
dodekja
  • 537
  • 11
  • 24
2
votes
1 answer

What is faster in practice: Treap or Splay tree?

I've learned both Treap and Splay tree and solved few problems using them. In theory, their complexity is O(log n) on average, but in worst-case Treap's complexity is O(n) while Splay tree's is amortized O(log n). In which case does worst case…
NikolaTECH
  • 76
  • 10
2
votes
2 answers

How to generate random priorities for Treap nodes?

In most examples I've seen on the web, it is taken as given that there's some sort of external random number generator that will yield random (distinct!) priorities. From what I recall, there was a method to actually generate the priorities randomly…
devoured elysium
  • 101,373
  • 131
  • 340
  • 557
1
vote
0 answers

Python: Recursive Treap Insert Function cannot create new node

I am writing a Python program for my class and I have to create a function (_insert) which is supposed to recursively perform the insert operation into my Map which is a treap data structure. However, whenever I am checking in my base cases to see…
Sam C.
  • 11
  • 1
1
vote
1 answer

Rotation in treap while keeping track of parent nodes

My treap maintains both the heap and BST properties, but the parent nodes of each node in the treap isn't always correct, and I think it's because of how I'm rotating. Here are my rotation functions: def left_rotate(self, child, parent): …
quazi_moto
  • 449
  • 1
  • 3
  • 14
1
vote
1 answer

Treap Data Structure

The height of Treap is said to be logarithmic in order. But while performing an online insertion for given key (1,2),(1,3),(3,4),(4,5) in order, the height of the treap is of the order of input. So the worst case complexity is turning out to be…
The Matoder
  • 51
  • 5
1
vote
1 answer

What is the utility of treap data structure?

I am currently studying advanced data structures and I came across a weird data structure called Treap. I understand what Treap is but I can't seem to find it's utility in a valid use case scenario. Why should you use such a data structure and in…
Vlad
  • 35
  • 7
1
vote
0 answers

segment fault in some special unknown cases, driving me CRAZY

I've been debugging for a whole day and I really am completely lost. Help! I tested tons of cases locally in Visual Studio. It works fine. But on our school's online judge system, there are several cases reporting RE(exitcode 6) which means a…
laplacecrame
  • 23
  • 1
  • 4
1
vote
0 answers

How this code generates random number?

I am learning treap nowadays and I came to an implementation in which the guy used some weird way to generate random numbers for priority.I am not able to get it.Would anybody mind explaining me how does it work. struct xor_128 { …
thoughtful me
  • 115
  • 8
1
2