

 
Manual Reference Pages  TREE::REDBLACK (3)
.ds Aq ’
NAME
Tree::RedBlack  Perl implementation of Red/Black tree, a type of balanced tree.
CONTENTS
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
perl v5.20.3  REDBLACK (3)  20080731 
Visit the GSP FreeBSD Man Page Interface. Output converted with manServer 1.07. 