Understanding B tree key deletion step from CLRS algorithm

Question

CLRS explains B tree key deletion as follows:

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 $k'$, and replace $k$ by $k'$ in x. (We can find $k'$ 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.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$.

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

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

---

I have a doubt in step 2c. In this step, $y$ is a node containing the predecessor of the key and $z$ is a node containing the successor of the key, both of which has minimum number of keys ($t-1$) and hence authors say we need to merge both of nodes. The authors give following example:

First tree is before deleting $G$, second is after deleting $G$, which utilized step 2c.

Here, $y=[D,E]$ is a predecessor node of $G$, with predecessor $E$ and $z=[J,K]$ is a successor node of $G$, with successor $J$. So we merge both $[D,E]$ and $[J,K]$ forming $[D,E,J,K]$.

My doubt is do we always end up successor and predecessor node if they contain minimum number of nodes ($t-1$)? This is what authors must mean to say when they say "merge $k$ and all of $z$ into $y$" in step 2c. But I feel they might not be the predecessor and successor nodes, they are just immediate next children of key $k$, as can be seen in this example I tried out:

Here we have not merged nodes of predecessor (node $[N,O]$) and successor (node $[R,S]$), but have merged immediate children of $Q$, i.e. node $[C,G,L]$ and node $[T,X]$.

So am I right with "we need to merge immediate next children of key $k$ but not predecessor and successor node"? If yes, is book have mistake? Or book does indeed tries to say the same and I am misinterpreting? Or I got it all wrong? Or am unnecessarily overthinking?

Answer 1

You are probably overthinking it by thinking in terms of predecessor/successor nodes.

The rule just says, if the key to be deleted has both children at least capacity, you cannot take a predecessor(or successor) from its left(or right) child without violating the B-Tree property. So, we decide that we will merge it with both its children and push the decision to delete one level downward. That's it.

An intermediate step in 2c. would be where G is pushed downward and merged with [DE] and [JK] to give

[[AB] , [C], [DEGJK], [L], [NO]]

Now we can apply the algorithm to this node [DEGJK], and since it's a leaf node, step 1 will apply here and we can simply delete G from it.