Tree::RedBlack - Perl implementation of Red/Black tree, a type of balanced tree.
my $t = new Tree::RedBlack;
my $v = $t->find(4);
my $min = $t->min;
my $max = $t->max;
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
- 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
- min ()
- Returns the node with the minimal key.
- max ()
- Returns the node with the maximal key.
Benjamin Holzman <email@example.com>