Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
After deleting an element from a B-tree,I could rearrange the tree in several ways,that would still complies to the rules of B-trees.But,we are supposed to follow a certain set of rules for rearranging the tree after deleting an element.
Why is that ?
Because it keeps the B-tree balanced?
In essence, what you are asking is why the algorithm is the way it is. The algorithm we use has been around long enough that if there was a better way to do it, people would have suggested that by now. I believe that the reason why this is the case is that the current algorithm is the simplest way possible to solve the B-tree problem. i.e. there's no useful further reduction of the problem to find.
That said, you have to be consistent but you are free to decide whether you want a tree that for example has either left or right bias but never both.
When deleting you also have a choice in whether to borrow from left or right first, or whether to merge with left or right first. You need to do both but you can attempt either left or right first.
The B-tree algorithm has some ambiguity or arbitrary things about it. Some aspects of it can be done in any number of ways, the end result will be the same. This can be confusing if you are not used to dealing with such arbitrary and/or ambiguous things.
