0
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ I honestly have no idea what you're asking. Could be more specific about the 'several ways' of rearrangement and the 'certain set of rules'? $\endgroup$ – Discrete lizard Mar 1 '18 at 17:54
  • 1
    $\begingroup$ Every implementation of the B-tree data structure will contain an implementation of the delete operation. This is a fixed algorithm ("set of rules") that the implementation always executes when deleting an element. Presumably this algorithm attempts to be reasonably efficient, and to keep the tree reasonably balanced, so that future operations will also be reasonably efficient. $\endgroup$ – Yuval Filmus Mar 1 '18 at 19:52
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.