Pseudocode from Aho, Hopcroft, and Ullman for searching and building in a 2-3 tree

Note: This is pseudocode, so that the notation "r.Left" does not reflect any implementation details regarding value or pointer fields in a C++/C– style struct/class.

SEARCH(a, r)
   if children of r are leaves
      return r
   else
      if      a <= r.L  return Search(a, r.Left)
      else if a <= r.M  return Search(a, r.Middle)
      else              return Search(a, r.Right)

Insertion into a non-empty tree T with root r of new a
   if T consists of a single leaf l labeled b [that is, if l is the root]
      create a new root r' (interior node)
      create a new leaf v labeled a
      make l and v children of r' in proper order
      update L and M for r'
   else
      Set f to SEARCH(a, r)
      create a new leaf l labeled a
      if f has 2 children
         insert l into proper position
         update L and M
      else
         create a transitory 4-node tree at f (l in proper position)
         ADDCHILD (f)

ADDCHILD(v)
   create new interior node v'
   move 2 rightmost children of v to v'
   if v has no parent [that is, if v is the root]
      make new root r'
      make v the left child and v' the right child
      update L and M
   else
      let f be the parent of v
      make v' the child of f immediately to the right of v
      if f now has 4 children
         ADDCHILD(f)
      else
         update L and M