NAME

Btrees - Binary trees using the AVL balancing method.

SYNOPSIS

# yes, do USE the package ...
use Btrees;

# no constructors

# traverse a tree and invoke a function
traverse( $tree, $func );

# find a node in a balanced tree
$node = bal_tree_find( $tree, $val $cmp );

# add a node in a balanced tree, rebalancing if required 
($tree, $node) = bal_tree_add( $tree, $val, $cmp )

# delete a node in a balanced tree, rebalancing if required 
($tree, $node) = bal_tree_del( $tree, $val , $cmp )

DESCRIPTION

Btrees uses the AVL balancing method, by G. M. Adelson-Velskii
and E.M. Landis. Bit scavenging, as done in low level languages like
C, is not used for height balancing since this is too expensive for
an interpreter. Instead the actual height of each subtree is stored
at each node. A null pointer has a height of zero. A leaf a height of
1. A nonleaf a height of 1 greater than the height of its two children.

AUTHOR

Ron Squiers (ron@broadcom.com). Adapted from "Mastering Algorithms with
Perl" by Jon Orwant, Jarkko Hietaniemi & John Macdonald. Copyright
1999 O'Reilly and Associates, Inc. All right reserved. ISBN: 1-56592-398-7