# Case distinction in B-tree deletion

Here is how deletion in B-trees is described:

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 k0 of k in the sub-tree rooted at y. Recursively delete k0, and replace k by k0 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 k0 of k in the subtree rooted at z. Recursively delete k0, and replace k by k0 in x. (We can find k0 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.c(i) of the appropriate subtree that must contain k, if k is in the tree at all. If x.c(i) 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.

What is the actual difference between case 1 case 3? Both seem to be directing to a leaf node.

• From the description, I think this is about B-trees, not binary (search) trees. – Raphael Jan 8 '14 at 17:05
• Incidentally, you can probably tell that there's a good reason why undergraduate textbooks never give a B-tree delete algorithm. If you're actually trying to implement B-trees, there's an alternative which is much simpler to understand. Ask Google about relaxed balance B-trees. – Pseudonym Jan 9 '14 at 0:13

In simple terms, "case 1" dictates what happens when we reach the appropriate leaf node.

"case 3" tells us what we do when we're still higher up in the tree.

Small example: suppose we have {x, y, z} in a tree like so:

  y
/ \
x   z


and we delete x. We start out at y and hit case 3, determining that "x" must be in the left subtree.

  y <-- we are here, and hit case 3
/ \
x   z


Thus, we recurse on the left subtree. We then reach x, and execute case 1.

                                  y
/ \
we are here, and hit case 1 --> x   z