View on
MetaCPAN is shutting down
For details read Perl NOC. After June 25th this page will redirect to
Greg Banks > Tree-Interval > Tree::Interval



Annotate this POD

View/Report Bugs
Module Version: 0.3.2   Source  


Tree::Interval - Perl implementation of an interval tree


 use Tree::Interval;
 my $t = Tree::Interval->new();
 $t->insert(3, 5, 'cat');
 $t->insert(7, 15, 'dog');
 my $v = $t->find(4);
 my $min = $t->min();
 my $max = $t->max();


This is a perl implementation of an interval tree for non-overlapping intervals, based on Tree::RedBlack by Benjamin Holzman <>. An interval tree is a binary tree which remains "balanced" i.e. 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(log(N)) time.

A Tree::Interval object supports the following methods:


Creates a new Interval 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::Interval::Node object.


Use this method to set a comparator subroutine. The tree defaults to builtin Perl numerical 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. For example,

 sub example_comparator
    my ($ka, $kb) = @_;
    return $ka <=> $kb;
insert(low, high, value)

Adds a new node to the tree. The first two arguments are an interval which forms the key of the node, the third is its value and may not be undef. Overlapping or duplicate keys are an error. Errors are handled using die. Nothing is returned.


Returns the node with the minimal key.


Returns the node with the maximal key.


Searches the tree to find the node whose interval contains the given key. Returns the value of that node, or undef if a node with that key isn't found.


Returns a list of all the node values.


Greg Banks <>, heavily based on Tree::RedBlack by Benjamin Holzman <>

syntax highlighting: