In a previous question there was a definition of weight-balanced and a question regarding red-black trees.

This question is to ask the similar question, but for treaps.

The question is:

Is there some $ \mu > 0 $ such that the expectation of $ \frac{|N_L| + 1}{|N| + 1} $ not less than $ \mu $ and not greater than $ 1 - \mu $ in treaps that the number of nodes is big enough?

Sorry for my poor English.

  • $\begingroup$ What do you think? What have you tried, and where did you get stuck? $\endgroup$ Commented Jun 23, 2017 at 13:36
  • $\begingroup$ Can you edit the question to make it self-contained? Also expectation over what random process, exactly? Do you want that to hold for all nodes of all big enough treaps? What does it mean to say "all treaps" when you're taking an expectation over treaps? The previous question didn't have any notion of randomness so I think you're going to need to set up that aspect of the problem carefully. $\endgroup$
    – D.W.
    Commented Jun 23, 2017 at 16:06
  • $\begingroup$ @D.W. Better now? $\endgroup$
    – Raphael
    Commented Jul 5, 2017 at 22:51
  • $\begingroup$ Interesting question, but: What have you tried? Where did you get stuck? Have you worked through the analysis of the expected height of treaps in detail? $\endgroup$
    – Raphael
    Commented Jul 5, 2017 at 22:55
  • $\begingroup$ @D.W. I would assume the same model that is used for expected height? That is, permutations with i.i.d. uniform "priorities"; it's straight-forward to show that the permutation is irrelevant for the resulting tree (there is exactly one treap for every key-priority sequence, assuming unique keys). $\endgroup$
    – Raphael
    Commented Jul 5, 2017 at 22:57


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.