Carrano (1st edition), pp. 554-555   Next Slide

insert (ttTree, newItem)
// Inserts newItem into the 2-3 tree ttTree whose items have
// distinct search keys that differ from newItem's search key.
.
.  Let sKey be the search key of newItem
.  Locate the leaf leafNode in which sKey belongs
.  Add newItem to leafNode
.
.  if ( leafNode how has three items )
.     split ( leafNode )

split (n)
// Splits node n, which contains 3 items.  Note: if n is
// not a leaf, it has 4 children
.
.  if ( n is the root )
.     Create a new node p
.  else
.     Let p be the parent of n
.
.  Replace node n with two nodes, n1 and n2, so that p is their parent

.  Give n1 the item in n with the smallest search-key value
.  Give n2 the item in n with the largest search-key value
.
.  if ( n is not a leaf )
.  {
.  .   n1 becomes the parent of n's two leftmost children
.  .   n2 becomes the parent of n's two rightmost children
.  }
.
.  Move the item in n that has the middle search-key value up to p
.
.  if ( p now has three items )
.     split ( p )