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:

Algorithm to insert a key 'k' into a tree T

Algorithm for the sub-procedure Insert-Nonfull(x,k) in B-Tree-Insert

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:

  1. 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?


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.