Page 183 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes

Next, delete R. Although R is in a leaf, this leaf does not have an extra key; the deletion results
in a node with only one key, which is not acceptable for a B-tree of order 5. If the sibling node to
the immediate left or right has an extra key, we can then borrow a key from the parent and move
a key up from this sibling. In our specifi c case, the sibling to the right has an extra key. So, the
successor W of S (the last key in the node where the deletion occurred), is moved down from the
parent, and the X is moved up. (Of course, the S is moved over so that the W can be inserted in
its proper place.)

Finally, let’s delete E. This one causes lots of problems. Although E is in a leaf, the leaf has no
extra keys, nor do the siblings to the immediate right or left. In such a case the leaf has to be
combined with one of these two siblings. This includes moving down the parent’s key that was
between those of these two leaves. In our example, let’s combine the leaf containing F with the
leaf containing A C. We also move down the D.

178 LOVELY PROFESSIONAL UNIVERSITY