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$ Jun 23 '17 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.
    Jun 23 '17 at 16:06
  • $\begingroup$ @D.W. Better now? $\endgroup$
    – Raphael
    Jul 5 '17 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
    Jul 5 '17 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
    Jul 5 '17 at 22:57

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.