3 ms·
Why does the root have only two children and not d, like every other non-leaf node?
by rizzin 11y ago
Why does the root have only two children and not d, like every other non-leaf node?
- deleted 11y ago[deleted]
- detrino 11y agoBecause when you split the root, it can only have 2 children.
- rizzin 11y agoI 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.