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.


  • 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.