データ構造におけるBツリーの削除

if x is leaf, then
   delete object with key ‘key’ from x
else if x does not contain the object with key ‘key’, then
   locate the child x->child[i] whose key range is holding ‘key’
   y := x->child[i]
   if y has m/2 elements, then
      If the sibling node z immediate to the left or right of y, has at least one more
      object than m/2, add one more object by moving x->key[i] from x to y, and
      move that last or first object from z to x. If y is non-leaf node, then last or first
      child pointer in z is also moved to y
   else
      any immediate sibling of y has m/2 elements, merge y with immediate sibling
   end if
   BTreeDelete(y, key)
else
   if y that precedes ‘key’ in x, has at-least m/2 + 1 objects, then
      find predecessor k of ‘key’, in the sub-tree rooted by y. then recursively delete k
      from the sub-tree and replace key with k in x
   else if ys has m/2 elements, then
      check the child z, which is immediately follows ‘key’ in x
      if z has at least m/2+1 elements, then
         find successor k of ‘key’, in the sub-tree rooted by z. recursively delete k
         from sub-tree, and replace key with k in x
   else
      both y and z has m/2 elements, then merge then into one node, and push ‘key’
      down to the new node as well. Recursively delete ‘key’ from this new node
   end if
end if