user3717821 user3717821 - 1 month ago 7
C Question

Deleting a node from B tree

min no of keys = 2
max no of keys = 5

P

CL TX
AB DEJK NO QRS UV YZ


Deleting key D:

CLPTX
AB EJK NO QRS UV YZ


this Answer is as per
Introduction to Algorithms by thomas H . Cormen

pg. no 501

it says: this is case 3b: the recursion cannot descend to node CL because it has only 2 keys so we need to push P down and merge it with CL and TX to form CLPTX the n we delete D from leaf (case1)

but I Think this answer is also fine:

P

CL TX
AB EJK NO QRS UV YZ


because leaf node EJK still have 3 keys satisfying min key constrainsts.

Please explain it.

yd1 yd1
Answer

the deleting algorithm goes from top to bottom, and therefore it cannot know if the leaves have enough or not. to make sure the algorithm works every time, it was decided that cells that have minimum keys (but legal) along the way from the top, will be merged. that's because if the leaves will need a "donation" from their parents, their parent will be able to provide them.

note: i said "leaves" to simplify things, but it also apply to every cell along the way.

note2: that's why in insert you do the opposite even if in a specific cases you may not have to.

Comments