Tree::RedBlack - Perl implementation of Red/Black tree, a type of balanced tree.
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;
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:
Creates a new RedBlack tree object.
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.
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.
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.
The argument should be either a node object to delete or the key of a node object to delete. WARNING!!! THIS STILL HAS BUGS!!!
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.
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.
Returns the node with the minimal key.
Returns the node with the maximal key.
Benjamin Holzman <bholzman@earthlink.net>