Computer Algorithms II Lecture Notes

23 October 2008 • M-way Trees

The pseudo-code for MWST delete is

root delete(root, v)

  i = scan-keys(root, v)

  if root.k[i] = v

    if root.c[i] ≠ nil
      root.c[i], root.k[i] = pull-max-key(root.c[i])

    else if root.c[i + 1] ≠ nil
      root.[c + 1], root.k[i] = pull-min-key(root.c[i + 1])

    else
      remove-key(root, i)
      if root.k.empty()
        root = nil

    return root

  else // root.k[i] ≠ v

    if root.c[i + 1] = nil
      return root

    return delete(root.c[i + 1], v)

The definitions of pull-max-key(), pull-min-key(), and remove-key() are left as an exercise (and this time I mean it).

This page last modified on 24 January 2006.