Page 182 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 8: B-trees

Notes
M

D G Q T

A C E F H K L N P R S W G Y Z

8.6 B-tree-Deleting an Item

Deletion of a key from a b-tree is possible; however, special care must be taken to ensure that the
properties of a b-tree are maintained. Several cases must be considered. If the deletion reduces
the number of keys in a node below the minimum degree of the tree, this violation must be
corrected by combining several nodes and possibly reducing the height of the tree. If the key has
children, the children must be rearranged.

In the B-tree as we left it at the end of the last section, delete H. Of course, we first do a lookup to

find H. Since H is in a leaf and the leaf has more than the minimum number of keys, this is easy.
We move the K over where the H had been and the L over where the K had been.
This gives:

.

Next, delete the T. Since T is not in a leaf, we find its successor (the next item in ascending order),
which happens to be W, and move W up to replace the T. That way, what we really have to do
is to delete W from the leaf, which we already know how to do, since this leaf has extra keys. In
ALL cases we reduce deletion to a deletion in a leaf, by using this method.

LOVELY PROFESSIONAL UNIVERSITY 177