I'm a generalist developer, preferring to have some skills in a variety of areas to being really good at only a few. I need to see how a technology solves real problems to really understand it.
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. :-)
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. :-)
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.