How to delete in a B-Tree when all nodes are singletons

Question

I'm working though the B-Tree example given on the ever wonderful wikipedia on this page. (I'm using wikipedia, because Stackoverflow tells me to... How do you remove an element from a b-tree?

I'm happy with the construction of this tree.

..and I find the algorithm elegant.

My issue is that the descriptions on Wikipedia for deleting a node appear to be missing a case. The three cases given for 're-balancing after deletion' are:

• If the deficient node's right sibling exists and has more than the minimum number of elements, then rotate left
• Otherwise, if the deficient node's left sibling exists and has more than the minimum number of elements, then rotate right
• Otherwise, if both immediate siblings have only the minimum number of elements, then merge with a sibling sandwiching their separator taken off from their parent.

None of which turn out to be helpful if the deficient node has no siblings (for example in the tree above, delete '1', '3' is now deficient and has no siblings).

My question is, what is the case/cases that are missing (presuming I've understood correctly), and what should the Wikipedia page say?

Answer 1

for example in the tree above, delete '1', '2' is now deficient and has no siblings

Yes, it has a sibling: The node (6,_). If you have no siblings, you are the root.

So in this case, we apply option 3 and end up with a two-level tree.