Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Why does the root have only two children and not d, like every other non-leaf node?


Because when you split the root, it can only have 2 children.


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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: