I am reading the chapter on B-Trees in Introduction to Algorithms (3rd edition) by Cormen and found the deletion procedure very confusing. I could understand the algorithm for insertion because it provided the pseudocode along with a few examples, like this:
But for deletion, it just says... "We sketch how deletion works instead of presenting the pseudocode" followed by steps which are very confusing. The very first step says:
- If the key k is in node x and x is a leaf, delete the key k from x.
But if I delete a key from the leaf, won't it violate the B-tree property if the number of keys is less than the minimum required?