0
$\begingroup$

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?

$\endgroup$

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.