NAME

       Tree::RedBlack - Perl implementation of Red/Black tree, a type of balanced tree.

SYNOPSIS

         use Tree::RedBlack;

         my $t = new Tree::RedBlack;
         $t->insert(3, 'cat');
         $t->insert(4, 'dog');
         my $v = $t->find(4);
         my $min = $t->min;
         my $max = $t->max;
         $t->delete(3);
         $t->print;

DESCRIPTION

       This is a perl implementation of the Red/Black tree algorithm found in the book
       "Algorithms", by Cormen, Leiserson & Rivest (more commonly known as "CLR" or "The White
       Book").  A Red/Black tree is a binary tree which remains "balanced"- that is, the longest
       length from root to a node is at most one more than the shortest such length.  It is
       fairly efficient; no operation takes more than O(lg(n)) time.

       A Tree::RedBlack object supports the following methods:

       new ()
           Creates a new RedBlack tree object.

       root ()
           Returns the root node of the tree.  Note that this will either be undef if no nodes
           have been added to the tree, or a Tree::RedBlack::Node object.  See the
           Tree::RedBlack::Node manual page for details on the Node object.

       cmp (&)
           Use this method to set a comparator subroutine.  The tree defaults to lexical
           comparisons.  This subroutine should be just like a comparator subroutine to sort,
           except that it doesn't do the $a, $b trick; the two elements to compare will just be
           the first two items on the stack.

       insert ($;$)
           Adds a new node to the tree.  The first argument is the key of the node, the second is
           its value.  If a node with that key already exists, its value is replaced with the
           given value and the old value is returned.  Otherwise, undef is returned.

       delete ($)
           The argument should be either a node object to delete or the key of a node object to
           delete. WARNING!!! THIS STILL HAS BUGS!!!

       find ($)
           Searches the tree to find the node with the given key.  Returns the value of that
           node, or undef if a node with that key isn't found.  Note, in particular, that you
           can't tell the difference between finding a node with value undef and not finding a
           node at all.  If you want to determine if a node with a given key exists, use the node
           method, below.

       node ($)
           Searches the tree to find the node with the given key.  Returns that node object if it
           is found, undef otherwise.  The node object is a Tree::RedBlack::Node object.

       min ()
           Returns the node with the minimal key.

       max ()
           Returns the node with the maximal key.

AUTHOR

       Benjamin Holzman <bholzman@earthlink.net>

SEE ALSO

       Tree::RedBlack::Node