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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.