Deletion in B-TreeFor deletion in b tree we wish to remove from a leaf. There are three possible case for deletion in b tree.
Let k be the key to be deleted, x the node containing the key. Then the cases are:
Case-IIf the key is already in a leaf node, and removing it doesn’t cause that leaf node to have too few keys, then simply remove the key to be deleted. key k is in node x and x is a leaf, simply delete k from x.
Case-IIIf key k is in node x and x is an internal node, there are three cases to consider:
Case-II-aIf the child y that precedes k in node x has at least t keys (more than the minimum), then find the predecessor key k' in the subtree rooted at y. Recursively delete k' and replace k with k' in x
Case-II-bSymmetrically, if the child z that follows k in node x has at least t keys, find the successor k' and delete and replace as before. Note that finding k' and deleting it can be performed in a single downward pass.
Case-II-cOtherwise, if both y and z have only t−1 (minimum number) keys, merge k and all of z into y, so that both k and the pointer to z are removed from x. y now contains 2t − 1 keys, and subsequently k is deleted.
Case-IIIIf key k is not present in an internal node x, determine the root of the appropriate subtree that must contain k. If the root has only t − 1 keys, execute either of the following two cases to ensure that we descend to a node containing at least t keys. Finally, recurse to the appropriate child of x.
Case-III-aIf the root has only t−1 keys but has a sibling with t keys, give the root an extra key by moving a key from x to the root, moving a key from the roots immediate left or right sibling up into x, and moving the appropriate child from the sibling to x.
Case-III-bIf the root and all of its siblings have t−1 keys, merge the root with one sibling. This involves moving a key down from x into the new merged node to become the median key for that node.
Algorithm For deletion in b tree
1. B-Tree-Delete-Key(x, k) 2. if not leaf[x] then 3. y ← Preceding-Child(x) 4. z ← Successor-Child(x) 5. if n[y] > t − 1 then 6. k' ← Find-Predecessor-Key(k, x) 7. Move-Key(k', y, x) 8. Move-Key(k, x, z) 9. B-Tree-Delete-Key(k, z) 10. else if n[z] > t − 1 then 11. k' ← Find-Successor-Key(k, x) 12. Move-Key(k', z, x) 13. Move-Key(k, x, y) 14. B-Tree-Delete-Key(k, y) 15. else 16. Move-Key(k, x, y) 17. Merge-Nodes(y, z) 18. B-Tree-Delete-Key(k, y) 19. else (leaf node) 20. y ← Preceding-Child(x) 21. z ← Successor-Child(x) 22. w ← root(x) 23. v ← RootKey(x) 24. if n[x] > t − 1 then Remove-Key(k, x) 25. else if n[y] > t − 1 then 26. k' ← Find-Predecessor-Key(w, v) 27. Move-Key(k', y,w) 28. k' ← Find-Successor-Key(w, v) 29. Move-Key(k',w, x) 30. B-Tree-Delete-Key(k, x) 31. else if n[w] > t − 1 then 32. k' ← Find-Successor-Key(w, v) 33. Move-Key(k', z,w) 34. k' ← Find-Predecessor-Key(w, v) 35. Move-Key(k',w, x) 36. B-Tree-Delete-Key(k, x) 37. else 38. s ← Find-Sibling(w) 39. w' ← root(w) 40. if n[w'] = t − 1 then 41. Merge-Nodes(w',w) 42. Merge-Nodes(w, s) 43. B-Tree-Delete-Key(k, x) 44. else 45. Move-Key(v,w, x) 46. B-Tree-Delete-Key(k, x)