To delete a key in a B-tree: Step 1. If the key k is in node x and x is a leaf, delete the key k from x. Step 2. If the key k is in node x and x is an internal node, do the following: 2a) If the child y that precedes k in node x has at least t keys, then find the predecessor k’ of k in the sub-tree 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.) 2b) If y has fewer than t keys, then, symmetrically, examine the 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.) 2c) 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 Write pseudo code for Step (2a) for function B-Tree-Delete-Key(x, k). Make sure your pseudo code is detailed with respect to the actual deletion that takes place in the internal node. Here, specify details with what takes place in the algorithm with regards to finding the predecessor, recursively deleting k', and replacing k by k' in x, don't just say what this step states in the problem statement). This is what I have so far... // Function B-Tree-Delete-Key(x, k) // Input: Node x and key k // Output: None // Step 2a // If the child y that precedes k in node x has at least t keys, then find the predecessor k’ of k in the sub-tree rooted at y. // Find the predecessor k' pred = find_predecessor(x, k); // Recursively delete k' B-Tree-Delete-Key(x, pred); // Replace k by k' in x x.keys[k] = pred; // Delete k delete x.keys[k]; Define the find_predecessor method please.
To delete a key in a B-tree:
Step 1. If the key k is in node x and x is a leaf, delete the key k from x.
Step 2. If the key k is in node x and x is an internal node, do the following:
2a) If the child y that precedes k in node x has at least t keys, then find the predecessor k’ of k in the sub-tree 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.)
2b) If y has fewer than t keys, then, symmetrically, examine the 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.)
2c) 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
Write pseudo code for Step (2a) for function B-Tree-Delete-Key(x, k). Make sure your pseudo code is detailed with respect to the actual deletion that takes place in the internal node. Here, specify details with what takes place in the
This is what I have so far...
// Function B-Tree-Delete-Key(x, k)
// Input: Node x and key k
// Output: None
// Step 2a
// If the child y that precedes k in node x has at least t keys, then find the predecessor k’ of k in the sub-tree rooted at y.
// Find the predecessor k'
pred = find_predecessor(x, k);
// Recursively delete k'
B-Tree-Delete-Key(x, pred);
// Replace k by k' in x
x.keys[k] = pred;
// Delete k
delete x.keys[k];
Define the find_predecessor method please.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
