3
$\begingroup$

If we have $n$ elements $s_1, \dots, s_n$ and build a kind of treap (tree-heap) out of it. Each $s_k$ has a priority, which is an integer in $\{ 1, 2, 3 \dots, \lceil \log n \rceil\}$. Since the priorities will have duplicates, I just want the treap the verify that for each node $s_k$, all the nodes in its right and left subtrees have smaller priority.

Is there a way to find the expected depth of this tree?

$\endgroup$
  • $\begingroup$ Is there any randomisation left? What is your input model? Why do you think performance differs from regular treaps? $\endgroup$ – Raphael Sep 18 '13 at 9:07
  • $\begingroup$ I don't think the problem is well formed yet. If two nodes have the highest priority then which one is the root? Maybe the heap invariant is "smaller or equal" rather than "smaller?" Once you've solved that problem, then I think the distribution on the priorities needs to be geometric (1/2 the nodes have the lowest priority $\lceil \log n \rceil$, and only about $1/n$ of the nodes have highest priority $1$.) At that point you may be able to prove that the priority of each node is approximately its depth in the tree. $\endgroup$ – Wandering Logic Sep 18 '13 at 12:30
  • $\begingroup$ I think that either Martinez and Roura's Randomized Binary Search Tree paper or more likely Pugh's Skip Lists paper discusses assigning priorities based on such a geometric distribution. $\endgroup$ – Wandering Logic Sep 18 '13 at 12:38
  • $\begingroup$ I just know that the proofs you can find in books often suppose priorities are all different. This is no different from a regular treap but it's a treap that accepts equal priorities. So for each $s_i$, all elements $s_j$ in the subtrees verify $priority(s_j) \leq priority(s_i)$ instead of the former convenient $priority(s_j) < priority(s_i)$ $\endgroup$ – helena treder Sep 20 '13 at 9:13
  • $\begingroup$ to answer @WanderingLogic: the problem as it is leaves the possiblity of having multiple configurations for the same set of priorities & keys. But the thing is: the order of the keys is not random, so if the order happen to be very bad, and the priorities keep being redundant, we end up with a very unbalanced tree. $\endgroup$ – helena treder Sep 23 '13 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.