DEV Community

Discussion on: Investigating tree height of a red black tree

vorahsa profile image
Jaakko Kangasharju

I'm guessing here, but the stability of the height might happen because 85 is a bit far from powers of 2, which are where the height of an optimal binary tree changes. If I'm right about that, you should see more variation if you test with, say, 125 or 130 elements.

Using random numbers as elements probably contributes something too. Usually, to get deviating behavior out of data structures, especially when the size increases, you need to craft the input specially a bit. Random inputs tend to show the "standard" behavior. To check this, it would be interesting to save the insertion sequences for when you got height 6 and study how the insertion order there differs from a more typical case.

Random insertion order will also make a regular binary search tree, without any balancing, perform well enough. It will have a larger height than a red-black tree, but not by much. It could be interesting to repeat your height test by inserting without balancing and comparing how the heights differ.

I don't know how deep you want to go in studying this specific phenomenon, though, so maybe I'm overthinking this. :-)

ekand profile image
Erik Anderson Author

You aren’t overthinking this. :-)
I’ve actually looked into some of what you mentioned and I’ll be writing some more about it shortly.