2-3 Trees in ruby

# insert "new" into 2-3 tree "root".  "new" is expected to understand "<".
# "root" can be nil, signifying an empty tree.
# or, root is assumed to be a hash, with elements:
#    tree0      possibly nil; first child 2-3 tree
#    data1      first data value; not nil, understands "<" method
#    tree2      possibly nil; second child 2-3 tree
#    data3      second data value; possibly nil.  if not, understands "<"
#    tree4      possibly nil (must be nil if data3 is nil); third child 2-3 tree.
#
# all tree0 elements <= data1 <= all tree2 elements <= data3 <= all tree4 elements
#
# all leaf nodes are the same depth.
#
# usage:
#    # copy and paste this page into insert23.rb
#    irb -I. -rinsert23
#    t = nil; (0..9).each {|n| t = insert23(n, t)}
#
def insert23(new, root)

  if root == nil
    return {:data1 => new}
  end

  # walk down the tree recursively looking for the leaf node to start at

  if root[:tree0] != nil # not at leaf node
    result = insert23(new,
                      new < root[:data1]                        ? root[:tree0] :
                      root[:data3] == nil || new < root[:data3] ? root[:tree2] :
                                                                  root[:tree4])
  else
    result = {:data1 => new, :fix => true}
  end

  # back up the tree unwinding the recursion..

  return root if result[:fix] == nil # all done signal from down the tree..

  result.delete(:fix)

  # if we have room to park the new node in the current tree node, we're done.

  if root[:data3] == nil
    if result[:data1] < root[:data1]
      root[:tree0]  , root[:data1],   root[:tree2],   root[:data3], root[:tree4] =
      result[:tree0], result[:data1], result[:tree2], root[:data1], root[:tree2]
    else
      root[:tree2],   root[:data3],   root[:tree4] =
      result[:tree0], result[:data1], result[:tree2]
    end

    return root

  else
    if new < root[:data1]
      d1 = root[:data1]
      t0 = result
      t2 = {:tree0 => root[:tree2], :data1 => root[:data3], :tree2 => root[:tree4]}

    elsif new < root[:data3]
      d1 = result[:data1]
      t0 = {:tree0 => root[:tree0],   :data1 => root[:data1], :tree2 => result[:tree0]}
      t2 = {:tree0 => result[:tree2], :data1 => root[:data3], :tree2 => root[:tree4]}

    else
      d1 = root[:data3]
      t0 = {:tree0 => root[:tree0], :data1 => root[:data1], :tree2 => root[:tree2]}
      t2 = result
    end

    return {:tree0 => t0, :data1 => d1, :tree2 => t2, :fix => true}
  end
end