Tree::rb is a pure-perl implementation of the red/black tree, a type of balanced binary search tree.

a tied hash interface is also provided to allow ordered hashes to be used.

see the wikipedia article at http://en.wikipedia.org/wiki/red-black_tree for more on red/black trees.