Answer:
Deleting a record on a B-tree consists of three main events:
- Searching the node where the key to be deleted exists
- Deleting the key
- Balancing the tree if required
Explanation:
q = NULL;
p = tree;
while (p) {
i = nodesearch(p, key);
q = p;
if (i < used(p) -1 && key == k(p,i)) {
found = TRUE;
position = i;
break;
}
p = son(p,i);
}
if (!found)
else if (subtree(p)) {
if (used(p) > ((n-1)/2)+1)
delkey (p, position, key);
else {
replace (p, position, fsucc(p));
p0 r1 p1 r2 p2 r3 ……. pn-1 rn-1 pn
q = &fsucc(p);
qpos = index of fsucc;
if (used(rbrother(p)) > ((n-1)/2)+1)
replace (q, qpos, sonsucc(q));
else
while (q && used(q) < (n-1)/2) {
concatenate(q, brother(q));
q = father(q);
}
}
}
else
delkey(p, position, key);
}
