Tree::Binary::Search 0.07

Tree::Binary::Search is a binary search tree for Perl.

SYNOPSIS

use Tree::Binary::Search;

my $btree = Tree::Binary::Search->new();

$btree->useNumericComparison();

$btree->insert(5 => "Five");
$btree->insert(2 => "Two");
$btree->insert(1 => "One");
$btree->insert(3 => "Three");
$btree->insert(4 => "Four");
$btree->insert(9 => "Nine");
$btree->insert(8 => "Eight");
$btree->insert(6 => "Six");
$btree->insert(7 => "Seven");

# this creates the following tree:
#
# +-------(5)----------+
# | |
# +-(2)-+ +-(9)
# | | |
# (1) (3)-+ +----(8)
# | |
# (4) (6)-+
# |
# (7)
#

$btree->exists(7); # return true

$btree->update(7 => "Seven (updated)");

$btree->select(9); # return Nine

$btree->min_key(); # returns 1

$btree->min(); # returns One

$btree->max_key(); # return 9

$btree->max(); # return Nine

$btree->delete(5);

# this results in the following tree:
#
# +-------(6)-------+
# | |
# +-(2)-+ +-(9)
# | | |
# (1) (3)-+ +-(8)
# | |
# (4) (7)
#

This module implements a binary search tree, which is a specialized usage of a binary tree. The basic principle is that all elements to the left are less than the root, all elements to the right are greater than the root. This reduces the search time for elements in the tree, by halving the number of nodes that need to be searched each time a node is examined.

Binary search trees are a very well understood data-structure and there is a wealth of information on the web about them.

Trees are a naturally recursive data-structure, and therefore, tend to lend themselves well to recursive traversal functions. I however, have chosen to implement the tree traversal in this module without using recursive subroutines. This is partially a performance descision, even though perl can handle theoreticaly unlimited recursion, subroutine calls to have some overhead. My algorithm is still recursive, I have just chosen to keep it within a single subroutine.