Page 551 Exercise 18

/* delete element with key x */
Search the B-tree for the node p that contains the element whose key is x;
if there is no such p return; /* no element to delete */
Let p be of the form n, A0 , (E1,A1), . . . , (En,An) and Ei.K = x;
if p is not a leaf {
Replace Ei with the element with the smallest key in subtree Ai;
Let p be the leaf of Ai from which this smallest element was taken;
Let p be of the form n, A0, (E1,A1), . . . , (En ,An);
i = 1;
}

Remove x from p;
p→n = p→n-1;
q← p's left sibling;
r← p's right sibling;
if (q→n + p→n + r→n + 2 <= 2m-1) then begin
/*collapse the nodes*/
    Insert K_i into the array Key;
    Insert p's remaining keys into the array Key ;
    Insert K_i+1 into the array Key;
    j =1;
    Diff = MaxSize - q→n + 1;
    For l = q→n to MaxSize do begin
    /*fill q with the first set of keys*/
         Insert Key[j] into q[k];
         j++;
    end;
    q→n = MaxSize;
    K_i = Key[j];
    j++;
   o = r→n;
    for l ← j to Size of Key do begin
    /*transfer remaining keys to r*/
       insert Key[l] into r[o];
    r→n = r→n + (Size of Key - j + 1);
    dispose(p);

if ( n) write p: (n, A0, . . . , (En,An ))
else root = A0 ; /* new root */