---
name: "Tree::RedBlack"
section: "3pm"
platform: "linux"
package: "libtree-redblack-perl"
version: "0.5-4"
release: "Debian 13 (Trixie)"
platforms: ["linux"]
url: "https://new.carta.tech/Tree::RedBlack"
---

# Tree::RedBlack(3pm)

Perl implementation of Red/Black tree, a type of balanced tree.

## 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