Tree::Binary::Search - A Binary Search Tree for perl |
Tree::Binary::Search - A Binary Search Tree for perl
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.
$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.
$root
argument in the constructor.
1
) if the tree is empty, and false (0
) otherwise.
$visitor
object to the underlying Tree::Binary::Search::Node object's accept
method.
$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.
$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.
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.
$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.
$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.
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.
This module is part of a larger group, which are listed below.
None that I am aware of. Of course, if you find a bug, let me know, and I will be sure to fix it.
See the CODE COVERAGE section of the Tree::Binary manpage for details.
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
min_key()
and max_key()
methods.
stevan little, <stevan@iinteractive.com>
Copyright 2004, 2005 by Infinity Interactive, Inc.
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.
Tree::Binary::Search - A Binary Search Tree for perl |