B-trees deletion Flashcards
(1) k in x && x (is leaf) then…what do we do
delete the key k from x
Describe an optimisation made for deletion
- Want to guarantee that whenever deletion calls itself recursively on a node x, #Keys(x) >= t (rather than >= t-1)
- So sometimes a key may have to be moved into a child before recursion descends to that child.
- Allows deletion in one downward pass without having to “back up” (one exception).
What happens if a root node x ever becomes an internal node with no keys
delete the empty node x,
x’s only child x.c becomes the new root of the tree
decreases tree height by one
preserves property that root of tree contains at least one key (unless tree is empty).
Case 1: key k is in node x and x is a leaf
delete key k from x
State condition for case 2
Case 2: Key k is in node x, and x is an internal node
Describe case 2a of deletion
Case 2: Key k is in node x, and x is an internal node
2a if child y preceding k in node x has >= t keys
Describe what to do in case 2a of deletion
2a if child y preceding k in node x has >= t keys, find predecessor k’ of k in subtree rooted at y, recursively delete k’ and replace k by k’ in x (we can find k’ and delete it in a single downward pass.)
Describe case 2b of deletion
Case 2: Key k is in node x, and x is an internal node
2b If y has fewer than t keys, then (symmetric to 2a)
What do we do in case 2b of deletion
2b If y has fewer than t keys, then (symmetric to 2a) examine child z that follows k in node x,
if z 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 (We can find k’ and delete it in a single downward pass).
State case 2c of deletion
2c If both y and z have only (t - 1) keys,
State what to do in case 2c of deletion
2c If both y and z have only (t - 1) keys, merge k and all of z into y $ x loses both k and the pointer to z, and y now contains 2t-1 keys. Then free the page allocated to node z, and recursively delete k from y.
State what to do in case 3 generally,
if k is not present in the internal node x,
then find the root of the appropriate subtree that must contain k, (if k is in the tree at all).
if the child has only t-1 keys execute step 3a or 3b as necessary to guarantee that we descend to a node containing at least t keys.
Then finish by recursing on the appropriate child of x.
Condition for case 3a
if the child x.c where k could possibly exist has only t-1 keys, but has an immediate sibling with at least t keys, give x.c an extra key by moving a key from x down int x.c, moving a key from x.c’s immediate left or right sibling up into x, and moving the appropriate child pointer from the sibling into x.c.
Condition for case 3b
if x.c and both of x.c’s immediate siblings have t-1 keys
What to do in case 3a
give x.c an extra key by moving a key from x down int x.c, moving a key from x.c’s immediate left or right sibling up into x, and moving the appropriate child pointer from the sibling into x.c.
