Hacker News new | ask | show | jobs
by detrino 4005 days ago
Because when you split the root, it can only have 2 children.
1 comments

I didn't understand your answer even after rereading about tree operations but I think I found out the actual reason why the root can have less than d children:

it is because of rebalancing after deletion. Underflows can go all the way up to the root so its children can borrow its indices. And when root has only one index (and two children) and another underflow occurs then its children combined with its index can form a new root decreasing the tree height by one.