• NAME
• SYNOPSIS
• DESCRIPTION
• AUTHOR

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