Ron Squiers > Btrees-1.00 > Btrees

Download:
Btrees-1.00.tar.gz

Dependencies

Annotate this POD (1)

View/Report Bugs
Module Version: 1   Source  

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
syntax highlighting: