Deletion of the leaf node from B-tree

Question

What are the rules of deleting nodes from a leaf nodes in a B tree. I have given an example below. I need to delete keys, J,K,U from leaf nodes. the 't' of the B tree is 3. so the minimum number of keys in a node should be 2.

J can be deleted without any issue.

But when J is deleted, the remaining would be K,L. Next when deleting K, since the node contains 2 nodes, K cannot be deleted directly.

Since its sibling node, which is N,O also contains its minimum nodes what should I perform here? Is it a merge?

How can I delete K and also U.

Please help.

Answer 1

I referred this book Introduction-to-algorithms-3rd-edition by Thomas H Cormen and he explained it very well. Here are the 3 steps that include all the cases.Hope it helps.

1. If the key k is in node x and x is a leaf, delete the key k from x.

2. If the key k is in node x and x is an internal node, do the following:

   a. If the child y that precedes k in node x has at least t keys, then find the predecessor k' of k in the subtree rooted at y. Recursively delete k0,and replace k by k' in x. (We can find k0 and delete it in a single downward pass.)

   b. If y has fewer than t keys, then, symmetrically, examine the child z that follows k in node x. If z has at least t keys, then find the successor k' of k in the subtree rooted at z. Recursively delete k' ,and replace k by k' in x. (We can find k' and delete it in a single downward pass.)

   c. Otherwise, if both y and z have only t-1 keys, merge k and all of z into y, so that x loses both k and the pointer to z, and y now contains 2t-1 keys. Then free z and recursively delete k from y.

3. If the key k is not present in internal node x, determine the root x.ci of the appropriate subtree that must contain k, if k is in the tree at all. If x.ci has only t-1 keys, execute step 3a or 3b as necessary to guarantee that we descend to a node containing at least t keys. Then finish by recursing on the appropriate child of x.

   a. If x.ci has only t-1 keys but has an immediate sibling with at least t keys, give x.ci an extra key by moving a key from x down into x.ci, moving a key from x.ci’s immediate left or right sibling up into x, and moving the appropriate child pointer from the sibling into x.ci.

   b. If x.ci and both of x.ci’s immediate siblings have t-1 keys, merge x.ci with one sibling, which involves moving a key from x down into the new merged node to become the median key for that node.