CLRS explains B tree key deletion as follows:
- If the key $k$ is in node $x$ and $x$ is a leaf, delete the key $k$ from $x$.
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$.
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?