Treap Data Structure

Question

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 linear. Any suggestions.

Answer 1

Two things are given:

• The priority of your node ist independent of your data (it is a random number)
• The chance of the worst case you described is 2/(n!) (ascending/descending occurance of random numbers)

So the runtime can be considered (amortized) Log(n) (average runtime with the same (worst case) data).