/ 
Tree-Binary-1.09
River stage one • 2 direct dependents • 2 total dependents
/ Tree::Binary::Search

NAME

Tree::Binary::Search - A Binary Search Tree for perl

SYNOPSIS

The program ships as scripts/search.1.pl:

#!/usr/bin/env perl

use strict;
use warnings;

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 (showing keys only):
#
#     +-------(5)----------+
#     |                    |
#  +-(2)-+              +-(9)
#  |     |              |
# (1)   (3)-+     +----(8)
#           |     |
#          (4)   (6)-+
#                    |
#                   (7)
#
# There is no method which will display the above,
# but a crude tree-printer follows.

my($parent_depth);

$btree -> getTree -> traverse
(
	sub
	{
		my($tree) = @_;

		print "\t" x $tree -> getDepth, $tree -> getNodeKey, ': ', $tree -> getNodeValue, "\n";
	}
);

$btree -> exists(7); # Returns a true value (1 actually).

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

$btree -> select(9); # Returns 'Nine'.

$btree -> min_key(); # Returns 1.

$btree -> min(); # Returns 'One'.

$btree -> max_key(); # Return 9.

$btree -> max(); # Returns 'Nine'.

$btree -> delete(5);

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

$btree -> getTree -> traverse
(
	sub
	{
		my($tree) = @_;

		print "\t" x $tree -> getDepth, $tree -> getNodeKey, ': ', $tree -> getNodeValue, "\n";
	}
);

If printing the tree is important, you are better off using Tree::DAG_Node.

DESCRIPTION

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.

METHODS

new

The constructor will take an optional argument ($root) which a class (or a class name) which is derived from Tree::Binary::Search::Node. It will then use that class to create all its new nodes.

Accessors

getTree

This will return the underlying binary tree object. It is a Tree::Binary::Search::Node hierarchy, but can be something else if you use the optional $root argument in the constructor.

Informational

isEmpty

Returns true (1) if the tree is empty, and false (0) otherwise.

size

Return the number of nodes in the tree.

height

Return the length of the longest path from the root to the furthest leaf node.

Tree Methods

accept ($visitor)

This will pass the $visitor object to the underlying Tree::Binary::Search::Node accept method.

DESTROY

This will clean up the underlying Tree::Binary object by calling DESTROY on its root node. This is necessary to properly clean up circular references. See the documentation for Tree::Binary, specifically the "CIRCULAR REFERENCES" section for more details.

Comparison Functions

useNumericComparison

A comparison function needs to be set for a Tree::Binary::Search object to work. This implementes numeric key comparisons.

useStringComparison

A comparison function needs to be set for a Tree::Binary::Search object to work. This implementes string key comparisons.

setComparisonFunction ($CODE)

A comparison function needs to be set for a Tree::Binary::Search object to work. You can set your own here. The comparison function must return one of three values; -1 for less than, 0 for equal to, and 1 for greater than. The constants EQUAL_TO, GREATER_THAN and LESS_THAN are implemented in the Tree::Binary::Search package to help this.

Search Methods

insert ($key, $value)

Inserts the $value at the location for $key in the tree. An exception will be thrown if either $key or $value is undefined. Upon insertion of the first element, we check to be sure a comparison function has been assigned. If one has not been assigned, an exception will be thrown.

update ($key, $value)

Updates the $value at the location for $key in the tree. If the key is not found, and exception will be thrown. An exception will also be thrown if either $key or $value is undefined, or if no keys have been inserted yet.

exists ($key)

Returns true (1) if the $key specified is found, returns false (0) othewise. An exception will be thrown if $key is undefined, and it will return false (0) if no keys have been inserted yet.

select ($key)

Finds and returns the $key specified. If the key is not found, and exception will be thrown. An exception will also be thrown if $key is undefined, or if no keys have yet been inserted.

delete ($key)

Deletes the node at $key in the tree, and restructures the tree appropriately. If the key is not found, and exception will be thrown. An exception will also be thrown if $key is undefined, or if no keys have been inserted yet.

Deletion in binary search trees is difficult, but as with most things about binary search trees, it has been well studied. After a few attempts on my own, I decided it was best to look for a real implementation and use that as my basis. I found C code for the GNU libavl (http://www.msu.edu/~pfaffben/avl/libavl.html/Deleting-from-a-BST.html) online along with an excellent description of the code, so I pretty much copied this implementation directly from the code in this library.

max_key

Returns the maximum key stored in the tree (basically the right most node).

max

Returns the maximum value stored in the tree (basically the right most node).

min_key

Returns the minimum key stored in the tree (basically the left most node).

min

Returns the minimum value stored in the tree (basically the left most node).

OTHER TREE MODULES

There are a number of advanced binary search tree-ish modules on CPAN, they are listed below for your reference. Tree::Binary::Search is not a balanced tree, which may not fit your needs, most of the trees below are balanced in one way or another.

Tree::RedBlack

This is an implementation of a red-black tree which is a type of balanced binary tree (to the best of my knowledge that is, I am sure I am simplifying it). Tree::Binary::Search does not attempt to balance the tree, so if you are looking for a balanced tree, you might try this.

Tree::BPTree

This module implements a B+ tree, rather than a binary search tree. In the authors own words, "B+ trees are balanced trees which provide an ordered map from keys to values. They are useful for indexing large bodies of data. They are similar to 2-3-4 Trees and Red-Black Trees. This implementation supports B+ trees using an arbitrary n value." I am not quite sure exactly how a B+ Tree works, but I am intrigued but this module. It seems to me to be well tested module as well. If you are looking for a B+ Tree, I suggest giving it a look.

Tree::M

In its own words, this module "implement M-trees for efficient 'metric/multimedia-searches". From what I can tell, this module is not a b-tree (binary search tree), but an m-tree, which is a tree optimized to handle multi-dimensional (spatial) data, such as latitude and longitude. It is a wrapper around a C++ library.

Tree::FP

In the authors own words, "Tree:FP is a Perl implmentation of the FP-Tree based association rule mining algorithm (association rules == market basket analysis)". For a detailed explanation, see "Mining Frequent Patterns without Candidate Generation" by Jiawei Han, Jian Pei, and Yiwen Yin, 2000. Contrarywise, most books on data mining will have information on this algorithm. " While it sounds like a very cool thing, it is not a binary search tree". =item Tree::Ternary

This is a ternary search trees, as opposed to a binary search tree. Similar, but different. If two nodes are not enough for you, I suggest taking a look at this. These is also an XS based implementation Tree::Ternary_XS.

Tree

This is actually the only module I found on CPAN which seems to implement a Binary Search Tree. However, this module was uploaded in October 1999 and as far as I can tell, it has ever been updated (the file modification dates are 05-Jan-1999). There is no actual file called Tree.pm, so CPAN can find no version number. It has no MANIFEST, README of Makefile.PL, so installation is entirely manual. Its documentation is scarce at best, some of it even appears to have been written by Mark Jason Dominus, as far back as 1997 (possibly the source code from an old TPJ article on B-Trees by him).

SEE ALSO

This module is part of a larger group, which are listed below.

Tree::Binary
Tree::Binary::VisitorFactory
Tree::Binary::Visitor::BreadthFirstTraversal
Tree::Binary::Visitor::PreOrderTraversal
Tree::Binary::Visitor::PostOrderTraversal
Tree::Binary::Visitor::InOrderTraversal

SUPPORT

Bugs should be reported via the CPAN bug tracker at

https://github.com/ronsavage/Tree-Binary/issues

CODE COVERAGE

See the CODE COVERAGE section of Tree::Binary for details.

SEE ALSO

The algorithm for delete was taken from the GNU libavl 2.0.1, with modifications made to accomidate the OO-style of this module.

http://www.msu.edu/~pfaffben/avl/libavl.html/Deleting-from-a-BST.html

ACKNOWLEDGEMENTS

Thanks to Jan Kratochvil for the min_key() and max_key() methods.

Repository

https://github.com/ronsavage/Tree-Binary

AUTHOR

stevan little, <stevan@iinteractive.com>

COPYRIGHT AND LICENSE

Copyright 2004, 2005 by Infinity Interactive, Inc.

http://www.iinteractive.com

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.