I have been playing with the very cool btree applet at slady.net. I'm having trouble understanding a particular behavior. Take a look at this starting state:
This particular state was arrived at by inserting the following sequence: 10, 15, 30, 16, 70, 1, 9, 27, 45, 50, 55.
My question is regarding what happens to the [45, ] node when I insert the next value in the sequence, 65.
The [55,70] node will be split by the 65, and being the middle value, the 65 will travel back up and then split the [30,50] node as well. My question is: Why does the [45, ] node end up a child of the [30, ] node? It's parent originally had 3 children, the left most and the right most became new seperate nodes. The 45 was between those values and it seems like it could have ended up under the [65, ] node just as well... Why?