NAME
Tree::AVL - An AVL (balanced binary) tree for time-efficient storage and retrieval of comparable objects
SYNOPSIS
use Tree::AVL;EXAMPLE 1
# This example shows usage with default constructor.
#
# By default, the tree works with strings. The
# constructor can also be passed a comparison function
# and accessor methods to use, so that you can store any
# type of object you've defined in the tree. (see Example 2).
# create a tree with default constructor
my $avltree = Tree::AVL->new();
# can insert strings by default
$avltree->insert("arizona");
$avltree->insert("arkansas");
$avltree->insert("massachusetts");
$avltree->insert("maryland");
$avltree->insert("montana");
$avltree->insert("madagascar"); # just seeing if you're paying attention..
print $avltree->get_height() . "\n"; # output: 2 (height is zero-based)
$avltree->print("*"); # output:
#
# *maryland: maryland: height: 2: balance: 0
# **massachusetts: massachusetts: height: 1: balance: 0
# ***montana: montana: height: 0: balance: 0
# **arkansas: arkansas: height: 1: balance: 0
# ***madagascar: madagascar: height: 0: balance: 0
# ***arizona: arizona: height: 0: balance: 0
my $obj = $avltree->remove("maryland");
print "found: $obj\n"; # output: found: maryland
my $obj = $avltree->remove("maryland");
if(!$obj){
print "object was not in tree.\n";
}
$avltree->print("*"); # output:
#
# *madagascar: madagascar: height: 2: balance: 0
# **massachusetts: massachusetts: height: 1: balance: 0
# ***montana: montana: height: 0: balance: 0
# **arkansas: arkansas: height: 1: balance: 1
# ***arizona: arizona: height: 0: balance: 0
# retreive an iterator over the objects in the tree.
my $iterator = $avltree->iterator();
while(my $obj = $iterator->()){
print $obj . "\n"; # outputs objects in order low-to-high
}
# retreive a reverse-order iterator over the objects in the tree.
my $iterator = $avltree->iterator(">");
while(my $obj = $iterator->()){
print $obj . "\n"; # outputs objects in order high-to-low
}
# retrieve all objects from tree at once
my @list = $avltree->get_list();
foreach my $obj (@list){
print $obj . "\n"; # outputs objects in order low-to-high
}
my $obj = $avltree->pop_smallest(); # retrieves arizona
print "$obj\n";
my $obj = $avltree->pop_largest(); # retrieves montana
print "$obj\n";
undef $avltree;
EXAMPLE 2
# Shows how to instantiate tree and specify key, data and
# comparison functions, so you can store any object
# you want. Here a basic hash is used, but
# any object of your creation will do when you
# supply an appropriate comparison function.
#
# Note: in this example, anonymous subroutines are
# passed in to the constructor, but you can just as well supply
# your own object's comparison methods by name- i.e.,
#
# $avltree = Tree::AVL->new(
# fcompare => \&MyObj::compare,
#
# . . .
#
# etc...
my $elt1 = { _name => "Bob",
_phone => "444-4444",};
my $elt2 = { _name => "Amy",
_phone => "555-5555",};
my $elt3 = { _name => "Sara",
_phone => "666-6666",};
$avltree = Tree::AVL->new(
fcompare => sub{ my ($o1, $o2) = @_;
if($o1->{_name} gt $o2->{_name}){ return -1}
elsif($o1->{_name} lt $o2->{_name}){ return -1}
return 0;},
fget_key => sub{ my($obj) = @_;
return $obj->{_name};},
fget_data => sub{ my($obj) = @_;
return $obj->{_phone};},
);
$avltree->insert($elt1);
$avltree->insert($elt2);
$avltree->insert($elt3);
$avltree->print("-"); # output:
#
# -Bob: 444-4444: height: 1: balance: 1
# --Amy: 555-5555: height: 0: balance: 0
# --Sara: 666-6666: height: 0: balance: 0
$avltree->insert($elt4); # output: "Error: inserted uninitialized object.."
exit;
DESCRIPTION
AVL Trees are balanced binary trees, first introduced in "An Algorithm for the Organization of Information" by Adelson-Velskii and Landis in 1962.
Balance is kept in an AVL tree during insertion and deletion by maintaining a 'balance' factor in each node.
If the subtree rooted at any node in the tree is evenly balanced, the balance factor for that node will be 0.
When the right-subtree below a node is taller than the left-subtree, the balance factor will be 1. For the opposite case, the balance factor will be -1.
If the either subtree below a node is heavier (taller by more than 2 levels) than the other, the balance factor within the node will be set to (+-)2, and the subtree rooted at that node will be rebalanced.
Re-balancing is done via 'single' or 'double' rotations, each of which takes constant time.
Insertion into an AVL tree will require at most 1 single or double rotation.
Deletion from an AVL tree may take as much as log(n) rotations in order to restore balance.
Balanced trees can save huge amounts of time in your programs when used over regular flat data-structures. For example, if you are processing as much as 1,125,899,906,842,624 ordered objects on some super awesome mega workstation, the worst-case time (comparisons) required to access one of those objects will be on the order of ~1,125,899,906,842,624 (one quadrillion, one hundred twenty-five trillion, eight hundred eighty-nine billion, nine hundred six million, eight hundred forty-two thousand, six hundred twenty-four) if you keep them in a flat data structure. However, using a balanced tree such as a 2-3 tree, a Red-Black tree or an AVL tree, the worst-case time (comparisons) required will be on the order of 50.
METHODS
new()
my $avltree = Tree::AVL->new(); # optionally pass in comparison, key accessor, and data accessor functionsCreates a new AVL tree object. Without any arguments, the constructor returns a tree that works with strings and uses lexical comparison. If you pass it an appropriate comparison function, the returned tree will work with any object of your creation. Also, you can pass in functions to get the 'key' and 'data' of any object as well (this is useful for printing the contents of the tree).
insert()
$avltree->insert($thing);Places an object or thing in the tree. Note: This function and most others have been implemented using iterative methods, rather than recursive calls, in order to reduce subroutine-call overhead and slightly enhance efficiency.
remove()
my $deleted_thing = $avltree->remove($thing);Removes items from the tree.
lookup()
my $found_key = $avltree->lookup($thing);Looks for $key in the tree, returns $key if found, or nil if not found.
lookup_obj()
my $found_thing = $avltree->lookup($thing);Looks for $thing in the tree, returns reference to $thing if found, or nil if not found.
lookup_node()
my $node = $avltree->lookup_node($thing);Looks for node in the tree, returns reference to node (a hash containing object and child-node pointers) if found, or nil if not found.
acc_lookup()
my @found_things = $avltree->acc_lookup($thing, $partial_cmp_func, $precise_cmp_func);Accumulative lookup; returns a list of all items whose keys satisfy the match function for the key for $object. For example, suppose you have a "relaxed" comparison function such as:
$string->superstring_compare($arg_string);which returns 0 (match) if the argument $arg_string is a proper 'superstring' of $string (meaning that it contains $string followed by one or more characters).
If you call acc_lookup() with this function as a parameter, acc_lookup() will return a list of all the strings in the tree that are superstrings of $string. acc_lookup() uses the tree property to do this in O(log(n)) time.
largest()
my $largest_thing = $avltree->largest();Returns the largest-valued item in the tree.
smallest()
my $smallest_thing = $avltree->smallest();Returns the smallest-valued item in the tree.
pop_largest()
my $largest_thing = $avltree->pop_largest();Removes and returns the largest-valued item in the tree.
pop_smallest()
my $smallest_thing = $avltree->pop_smallest();Removes and returns the smallest-valued item in the tree.
iterator()
my $it = $avltree->iterator();Returns an iterator over the items in the tree. By default the iterator is in-order from lowest to highest. If you pass in the parameter ">", the order of the items returned by the iterator will be from highest to lowest.
get_root()
my $root_obj = get_root();Returns a reference to the object stored at the root of the tree.
print()
$avltree->print();Dumps the contents of the tree to STDOUT. If passed an additional string parameter, it will be used to visually distinguish objects by their respective heights in the tree (by prepending the string passed-in to the object's printed value).
DEPENDENCIES
This module requires these other modules and libraries:
Test::More (required for installation test)
CHANGES
Version 1.074 Sat Nov 7 12:33:11 EST 2009
- Fixed a bug where strings or objects that evaluate to boolean 'false' (such as the string "0") could not be inserted into the tree.
Version 1.05 Sat Jul 11 12:57:00 2009
- Fixed a bug in largest() function, where recursive invocation was implemented incorrectly.
- Modified get_list() and get_list_recursive() so that they behave consistently, returning an array of 0 length if there are no objects in the tree.
EXPORT
None by default.
SEE ALSO
"An Algorithm for the Organization of Information", G.M. Adelson-Velsky and E.M. Landis.
AUTHOR
Matthias Beebe, <matthiasbeebe@gmail.com>
ACKNOWLEDGEMENTS
Thanks to Robert Lehr for discovering defects and inconsistent behavior, and for providing patches where necessary.
Thanks to CPAN user N.Cleaton, for reporting a bug related to using boolean 'false' values in the tree.
COPYRIGHT AND LICENSE
Copyright (C) 2009, 2010 by Matthias Beebe
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.8.8 or, at your option, any later version of Perl 5 you may have available.