Carrano (1st edition), pp. 561-62     Back to the Balanced Multi-Way Tree web page

deleteItem ( in ttTree:TwoThreeTree, in searchKey:KeyType)
// Deletes from the 2-3 tree the item whose search
// key equals searchKey.  If the deletion is
// successful, the method returns tree.
// If no such item exists, the operation fails and
// returns false.
.
.  Attempt to locate item theItem whose search key equals searchKey
.
.  if ( theItem is present )
.  {  if ( theItem is not in a leaf )
.  .     Swap item theItem with its inorder successor, which will
.  .                       be in a leaf leafNode
.  .
.  .  // the deletion always begins at a leaf
.  .  Delete item theItem from leaf leafNode
.  .
.  .  if ( leafnode now has no items )
.  .     fix ( leafNode )
.  .  return true
.  }
.  else
.     return false


fix ( n )
// Completes the deletion when node n is empty by either
// removing the root, redistributing values, or merging
// nodes.  Note: if n is internal, it has one child.
.
.  if ( n is the root )
.     Remove the root
.
.  else
.  {  let p be the parent of n
.  .
.  .   if ( some sibling of n has two items )
.  .   {  Distribute items appropriately among n, the sibling, 
.  .   .                     and p
.  .   .
.  .   .  if ( n is internal )
.  .   .     Move the appropriate child from sibling to n
.  .   }
.  .   else  // merge the node
.  .   {  Choose an adjacent sibling s of n
.  .   .   Bring the appropriate item down from p into s
.  .   .
.  .   .   if ( n is internal )
.  .   .      Move n's child to s
.  .   .
.  .   .   Remove node n
.  .   .
.  .   .   if ( p is now empty )
.  .   .      fix ( p )
.    }  // END if
.  }  // END if