I wrote a program to discover how height of the tree is relative to the number of elements in the tree (nodes).

On first test I filled array with 10-50-100-200...-1000 elements of random numbers from 0 to 32k~~ and checked their height and then second array with the same number of elements, however this time keys were picked randomly from 0-9, instead of 0-rand().

And I wonder if I have this right, is this possible height or im just getting some semi-random numbers. Would be grateful for checking that out. For now I don't know how to compare these scores and charts. The scores are very close, but the first array seems to have height slightly lower than second array.



closed as unclear what you're asking by David Richerby, Evil, Raphael Feb 13 '18 at 10:37

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ But what's your question? $\endgroup$ – David Richerby Feb 12 '18 at 22:09

As a rule of thumb, your red-black tree depth can't be less than log(n) and it shouldn't be more than 2*log(n+1). Your numbers look correct. (log(1000)=10 and your 1000 sample tests are between 10 and 20).

Ref: http://lcm.csa.iisc.ernet.in/dsa/node115.html


Not the answer you're looking for? Browse other questions tagged or ask your own question.