CODEWITHSUNDEEP
data-structurestreeb-tree
Mariam Mohamad
Mariam Mohamad

Reputation: 1

B-tree: delete a non-leaf node?

Im studying B tree and in the book they said that:

  1. If the key k is in node x and x is a leaf, delete the key k from x.

  2. If the key k is in node x and x is an internal node, do the following.

a. If the child y that precedes k in node x has at least t keys, then find the predecessor k' of k in the subtree rooted at y. Recursively delete k', and replace k by k' in x. (Finding k' and deleting it can be performed in a single downward pass.)

b. Symmetrically, if the child z that follows k in node x has at least t keys, then find the successor k' of k in the subtree rooted at z. Recursively delete k', and replace k by k' in x. (Finding k' and deleting it can be performed in a single downward pass.)

c. Otherwise, if both y and z have only t- 1 keys, merge k and all of z into y, so that x loses both k and the pointer to z, and y now contains 2t - 1 keys. Then, free z and recursively delete k from y.

My question is this: In case 2.a. Can someone explain me with example: Recursively delete k', and replace k by k' in x.

Regards.

Upvotes: 0

Views: 779

Answers (1)

karastojko
karastojko

Reputation: 1181

Suppose you have b tree with the degree t = 4:

   26,      49,      60
27,31,34,36     51,55,56,58

Suppose y = [27,31,34,36], x = [51,55,56,58] are not leaf nodes and you want to delete key k = 51. Let K = 49 be the key in the parent node which splits x and y.

Find the predecessor of k which is the rightmost key k' in the subtree y (which could contain integers between 37 and 48 in this example, say k' = 40). Set k = K = 49 and K = k' = 40 and delete k' recursively (which is actually the first case of the deletion procedure when the node is leaf). The resulting b tree looks like

   26,      40,      60
27,31,34,36     49,55,56,58

Upvotes: 1

Related Questions