CODEWITHSUNDEEP
c++calgorithmtreeb-tree
user3717821
user3717821

Reputation: 83

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.

Upvotes: 3

Views: 758

Answers (1)

yd1
yd1

Reputation: 277

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.

Upvotes: 4

Related Questions