sorted_hash.rb

# assumes your keys aren't nil, and are sortable by <=>
class SortedHash  
  def initialize
    @bst, @hsh = BST.new, {}
  end
  
  def [](key)
    @hsh[key]
  end
  
  def []=(key, value)
    @hsh[key] = value
    @bst.add key
  end
  
  def each(&block)
    @bst.each do |key|
      block.call @hsh[key]
    end
  end
end

class SortedHash
  class BST
    def initialize
      @left = @right = @data = nil
    end
    
    def add(data)
      if !@data
        @data = data
      elsif data <= @data
        @left ||= BST.new
        @left.add data
      else
        @right ||= BST.new
        @right.add data
      end
    end
    
    def each(&block)
      @left && @left.each(&block)
      block.call @data
      @right && @right.each(&block)
    end
  end
end

a = SortedHash.new
a[2] = "two"
a[1] = "one"
a[5] = "five"
a[0] = "zero"
a[3] = "three"
a[4] = "four"
a.each do |string|
  string # => "zero", "one", "two", "three", "four", "five"
end