Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Contact Us
Online Help
Domain Status
Man Pages

Virtual Servers

Topology Map

Server Agreement
Year 2038

USA Flag



Man Pages

Manual Reference Pages  -  TREE::REDBLACK (3)

.ds Aq ’


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;


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.


Benjamin Holzman <>


Search for    or go to Top of page |  Section 3 |  Main Index

perl v5.20.3 REDBLACK (3) 2008-07-31

Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with manServer 1.07.